PHP-请教一个随机数相关的算法问题

Question

已知有个rand7()的函数，返回1到7随机自然数，如何利用这个rand7()函数构造出rand10()？即可以随机1到10的自然数。

Answer 1

rand7()的离散集合为{1,2,3,4,5,6,7}，每个数的几率为1/7
rand7()-1的离散集合为{0,1,2,3,4,5,6}，每个数的几率也为1/7
(rand7()-1)*7的离散集合为{0,7,14,21,28,35,42}，每个数的几率也为1/7
(rand7()-1)*7+rand7()的离散集合为{1,...,48,49}，每个数的几率为1/49
因此，让{10,20,30,40}=1，{1,11,21,31}=2，...，{9,19,29,39}=10就可以使1-10的出现几率为4/40，即1/10。

function rand10() {
var rand = 0;
do {
rand = (rand7() - 1) * 7 + rand7();
}while(rand > 40);
return (rand % 10) + 1;
}

Answer 2

个人认为，这个构造方法，没办法满足均匀分布。"1-7" -> "1-10"的映射范围比较大，证明比较吃力。举个"1-2" -> "1-3"的映射例子。无论经过什么变换，"加、减、乘、除、开方、乘方..."运算，两个数只能对应两个数或两种映射关系。
"1-2" -> "1-3"会有3种映射关系：
12,12,12
12,31,23
采用1、2随机数，只能选择两种映射关系，第三种映射关系无法选取。
例如:若你说随机到1，先选取12->12为一组，12->23、12->31为另一组。若随机到2，先选取12->12、12->31为一组，12->23为另一组。再次对由两个映射关系组成的组，使用随机数，为1则选择第一个映射，为2则选择第二个映射。这样会得到1/2、1/4、1/4或者1/4、1/4、1/2的概率分布，不是均匀分布。

所以无法构造均匀分布。"1-7" -> "1-10"同理。

若不需要满足均匀分布，可以参考：
【Killua面试题整理】由随机函数rand7构造rand10

一道腾讯的面试题：已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10

Answer 3

要完全均匀的几乎无解，回去复习概率论去，又写了一个，记录一下吧

function rand7(){
    return rand(1,7);
}

function rand10(){
    do{
        $a = rand7();
    }while($a==7);
    return rand7() + $a%3;
}

Answer 4

确实是要精确的无解
相当于在 [1,7^n] 与[1、10]间建立双射
可以用线性映射近似双射
当n越大的时候误差越小