首页 > 代码库 > 已知一个函数rand5()能够生成1-5的随机数,请给出一个函数,该函数能够生成1-7的随机数。

已知一个函数rand5()能够生成1-5的随机数,请给出一个函数,该函数能够生成1-7的随机数。

这是朋友去笔试的一道题,有点考智商,当时我还很自信的说 random5+random5/2  不就可以了 他说不行,然后我就在网上搜了一下 有一道类似的题目

题目:

已知一个函数rand7()能够生成1-7的随机数,请给出一个函数,该函数能够生成1-10的随机数。

 

思路:

假如已知一个函数能够生成1-49的随机数,那么如何以此生成1-10的随机数呢?

 

解法:

该解法基于一种叫做拒绝采样的方法。主要思想是只要产生一个目标范围内的随机数,则直接返回。如果产生的随机数不在目标范围内,则丢弃该值,重新取样。由于目标范围内的数字被选中的概率相等,这样一个均匀的分布生成了。

显然rand7至少需要执行2次,否则产生不了1-10的数字。通过运行rand7两次,可以生成1-49的整数,

 

   1  2  3  4  5  6  7 1  1  2  3  4  5  6  7 2  8  9 10  1  2  3  4 3  5  6  7  8  9 10  1 4  2  3  4  5  6  7  8 5  9 10  1  2  3  4  5 6  6  7  8  9 10  *  * 7  *  *  *  *  *  *  *

由于49不是10的倍数,所以我们需要丢弃一些值,我们想要的数字范围为1-40,不在此范围则丢弃并重新取样。

 

代码:

 

[cpp] view plaincopy
 
  1. int rand10() {  
  2.   int row, col, idx;  
  3.   do {  
  4.     row = rand7();  
  5.     col = rand7();  
  6.     idx = col + (row-1)*7;  
  7.   } while (idx > 40);  
  8.   return 1 + (idx-1)%10;  
  9. }  


由于row范围为1-7,col范围为1-7,这样idx值范围为1-49。大于40的值被丢弃,这样剩下1-40范围内的数字,通过取模返回。下面计算一下得到一个满足1-40范围的数需要进行取样的次数的期望值:

 

 

E(# calls to rand7) = 2 * (40/49) +                       4 * (9/49) * (40/49) +                       6 * (9/49)

2

 * (40/49) +                       ...                                             =  2k * (9/49)

k-1

 * (40/49)                       k=1                      = (80/49) / (1 - 9/49)

2

                     = 2.45

优化:

 

上面的方法大概需要2.45次调用rand7函数才能得到1个1-10范围的数,下面可以进行再度优化。

对于大于40的数,我们不必马上丢弃,可以对41-49的数减去40可得到1-9的随机数,而rand7可生成1-7的随机数,这样可以生成1-63的随机数。对于1-60我们可以直接返回,而61-63则丢弃,这样需要丢弃的数只有3个,相比前面的9个,效率有所提高。而对于61-63的数,减去60后为1-3,rand7产生1-7,这样可以再度利用产生1-21的数,对于1-20我们则直接返回,对于21则丢弃。这时,丢弃的数就只有1个了,优化又进一步。当然这里面对rand7的调用次数也是增加了的。代码如下:

 

[cpp] view plaincopy
 
  1. int rand10Imp() {  
  2.   int a, b, idx;  
  3.   while (true) {  
  4.     a = rand7();  
  5.     b = rand7();  
  6.     idx = b + (a-1)*7;  
  7.     if (idx <= 40)  
  8.       return 1 + (idx-1)%10;  
  9.     a = idx-40;  
  10.     b = rand7();  
  11.     // get uniform dist from 1 - 63  
  12.     idx = b + (a-1)*7;  
  13.     if (idx <= 60)  
  14.       return 1 + (idx-1)%10;  
  15.     a = idx-60;  
  16.     b = rand7();  
  17.     // get uniform dist from 1-21  
  18.     idx = b + (a-1)*7;  
  19.     if (idx <= 20)  
  20.       return 1 + (idx-1)%10;  
  21.   }  
  22. }  

下面计算下优化后方法的调用rand7函数的期望次数:

 

 

E(# calls to rand7) = 2 * (40/49) +                       3 * (9/49) * (60/63) +                       4 * (9/49) * (3/63) * (20/21) +                         (9/49) * (3/63) * (1/21) *                       [ 6 * (40/49) +                         7 * (9/49) * (60/63) +                         8 * (9/49) * (3/63) * (20/21) ] +                        ((9/49) * (3/63) * (1/21))

2

 *                       [ 10 * (40/49) +                         11 * (9/49) * (60/63) +                         12 * (9/49) * (3/63) * (20/21) ] +                       ...                      = 2.2123

这里期望次数为2.21,比起未优化的2.45次减少了大概10%。

http://www.cppblog.com/mysileng/archive/2013/05/20/200426.html

看第一遍,我还是觉得都差不多,后来朋友指出,我这样算的概率不同,不能算作随机数,于是我又看了一遍,恍然大悟