已知一个函数f可以得到1-5间的随机数，问怎么得到1-7的随机数

glq2000

在 http://blog.csdn.net/DKarthas/archive/2007/11/05/1868212.aspx看到一个面试题，博主只是提出了问题，没有给出解答，所以在这发一下，希望知道解的tx解答下  ：）

问题：

已知一个函数f可以等概率的得到1-5间的随机数，问怎么等概率的得到1-7的随机数，

这个问题是有解的么？ 若无解，说明原因，若有解，那解是什么？

(该问题已解决，剧透一下，正解在17楼~~~~~~~~)

evaspring

占着沙发这样好的位置当然要作点贡献，公布下比较接近标准的答案：

算法思路是：
1. 通过 rand5()*5+rand5() 产生 6 7 8 9 10 11 …… 26，27 28 29 30 这25个数，每个数的出现机率相等
2. 只需要前面 3*7 个数，所以舍弃后面的4个数
3. 将 6 7 8 转化为 1，9 10 11 转化为 2，……，24 25 26 转化为 7。公式是 (a-3)/3

1. int rand7()
   
2. {
   
3. int a;
   
4. while( (a=rand5()*5+rand5()) > 26 );
   
5. return (a-3)/3;
   
6. }
   

复制代码

或者

1. int rand7()
   
2. {
   
3.         int sum = 0;
   
4.         for(int i=0; i<7; i++)
   
5.         {
   
6.                   sum += ( rand5() - 1 ) * pow(5,i) ;
   
7.         }
   
8.         return (sum%7+1);
   
9. }

复制代码

iamxmz

运行7次f()加起来除5

写完之后想了一下,7只会出现一次,前边的数都会出现很多次,这个不对.

glq2000

回复 2# evaspring


    f()+f()%2 的取值范围是 1到6啊
   
后来我改为    f()+f()%3， 这样取值范围倒是1到7了，但取七的概率是

前面需要为5， 后面需要为2或者5， 所以 1/5 * 2/5 = 2/25, 也不是1/7， 满足不了等概率的条件。。。。。。。。。

egmkang

f() + f() % 2
evaspring 发表于 2010-07-06 18:41

这个好像不是平均分布的把

glq2000

回复 2# evaspring


    f()随机返回1-5， 那f()运行7次相加的话，再除以7的话，最大也就是 5*7/7 = 5, 根本取不到6和7啊。
   如果你的意思是对7取余，即使先不考虑等概率，取余的结果中包含0，而要求是对1-7返回等概率，不包括0。

   我感觉这个题是个数学题。。。。。。

glq2000

对，有两点要特别注意，  一是等概率等返回1-7中的某个数，而是f()的取值是1-5，他可以等概率的返回一到五，现在要等概率的返回1-7，不包括0，

这个题目是有解的么？ 解是什么？ 无解的话，原因是？

churchmice

回复 6# glq2000


仔细看，人家是除以5

iamxmz

我改了,写错了,先写的除7.不过除5也不对,这样7只会出现1次.

egmkang

3楼是正解