给你一个能生成1到5随机数的函数，用它写一个函数生成1到7的随机数
文章目录
- 给你一个能生成1到5随机数的函数，用它写一个函数生成1到7的随机数
- 一、问题
- 二、分析
- 三、错解
- 四、正解一
- 五、正解二
- 六、拓展
一、问题
已知rand5()产生1-5的随机整数，利用该函数生成函数rand7()产生1-7的随机整数。
二、分析
- rand5可以随机生成1 ~ 5；目标生产rand7，使其可以随机生成1 ~ 7。 rand5并不能直接产生6，7。我们可能想到 + 2，但是+ 2生产的是3 ~ 7，不满足题意。
- 所以直接用rand5去实现函数rand7似乎不太好入手，那么我们反向思考一下，如果给你rand7，让你实现rand5，这个好实现吗？
- 其实反过来是可以的，因为
rand7的生成随机数范围多了6和7，生成1 ~ 5的随机数的概率仍然是随机的，所以我们就需要对6和7下手。 - 怎样操作6和7才可以使rand7生成随机数的范围为0 ~ 5并且忽略6和7呢？答案就是
如果rand7生成的随机数大于5，就继续调用rand7，这样rand7既满足了生成随机数的范围为1 ~ 5并且保证了随机
#include <iostream>
#include <ctime>
#include <unistd.h>
#include <limits.h>
using namespace std;
int Rand7()
{
return rand() % 7 + 1;
}
//使用Rand7等概率生成1 ～ 5的随机数
int Rand5()
{
int num = INT_MAX;
while(num > 5)
{
num = Rand7();
}
return num;
}
int main()
{
srand((unsigned)time(NULL));
while(1)
{
cout<<Rand5()<<endl;
sleep(1);
}
return 0;
}
- 那么Rand5这个函数可以等概率地产生1到5的数吗？
- 首先，它确确实实只会返回1到5这几个数， 其次，对于这些数，
都是由Rand7等概率产生的(1/7)，没有对任何一个数有偏袒（如果生成的随机数大于5，就会继续调用该函数）， 直觉告诉我们，Rand5就是等概率地产生1到5的。 - 事实呢？让我们来计算一下，
产生1到5中的数的概率是不是1/5就OK了。 - 比如说，让我们来计算一下Rand5生成1 的概率是多少。上面的函数中有个while循环，只要没生成1到5间的数就会一直执行下去。
- 因此，我们要的1可能是第一次调用Rand7时产生，也可能是第二次，第三次，…第n次。 第1次就生成1，概率是1/7；第2次生成1，说明第1次没生成1到5间的数而生成了6，7， 所以概率是(2/7)*(1/7)，依次类推。生成1的概率计算如下：
P(x=1)=1/7+(2/7)*1/7+(2/7)^2*1/7+(2/7)^3*1/7+...
=1/7*(1+2/7+(2/7)^2+...)// 等比数列
=1/7*1/(1-2/7)
=1/7*7/5
=1/5
- 上述
计算说明Rand5函数是等概率地生成1,2,3,4,5的(1/5的概率)。从上面的分析中， 我们可以得到一个一般的结论，如果a > b，那么一定可以用Randa去实现Randb。其中， Randa表示等概率生成1到a的函数，Randb表示等概率生成1到b的函数。代码如下：
// a > b
int RandA(){};
int RandAtoB()
{
int num = INT_MAX;
while(num > b)
num = RandA();
return num;
}
三、错解
- 回到正题，现在
题目要求我们要用Rand5来实现Rand7，只要我们将Rand5 映射到一个能产生更大随机数的Randa，其中a > 7，就可以套用上面的模板了。 这里要注意一点的是，你映射后的Randa一定是要满足等概率生成1到a的。比如，
Rand5() + Rand5() - 1;
- 上述代码可以生成1到9的数，但
它们是等概率生成的吗？不是。生成1只有一种组合： 两个Rand5()都生成1时：(1, 1)；而生成2有两种：(1, 2)和(2, 1)；生成6更多。 - 它们的生成是不等概率的。那要怎样找到一个等概率生成数的组合呢？
四、正解一
我们先给出一个组合，再来进行分析。组合如下：
5 * (Rand5() - 1) + Rand5();
- 第一个Rand5产生1到5的随机数，减1就产生0到4的随机数，乘以5后可以产生的随机数是：0,5,10,15,20。
- 第二个Rand5()产生的随机数是1,2,3,4,5。那么
我们可以得到1到25的随机数， 而且每个数都只由一种组合得到，即上述代码可以等概率地生成1到25。 - OK， 到这基本上也就解决了.
套用上面的模板，我们可以得到如下代码：
int Rand5(){};
int Rand7()
{
int num = INT_MAX;
while(num > 7)
num = 5 * (Rand5() - 1) + Rand5();
return num;
}
五、正解二
- 上面的代码有什么问题呢？可能while循环要进行很多次才能返回。
- 因为Rand25会产生1到25的数，而只有1到7时才跳出while循环， 生成大部分的数都舍弃掉了。这样的实现明显不好，我们应该让舍弃的数尽量少。
-
于是我们可以修改while中的判断条件，让x与(最接近25)且(小于25)的(7的倍数)相比。 - 于是
判断条件可改为x > 21，于是x的取值就是1到21。 我们再通过取模运算把它映射到1-7即可。代码如下：
int Rand5(){};
int Rand7()
{
int num = INT_MAX;
while(num > 21)
num = 5 * (Rand5() - 1) + Rand5();
return num % 7 + 1;
}
- 这个实现就比上面的实现要好，并且可以保证等概率生成1到7的数。
六、拓展
- 让我们把这个问题泛化一下，从特殊到一般。现在我给你
两个生成随机数的函数Randa，Randb。Randa和Randb分别产生1到a的随机数和1到b的随机数，a，b不相等(相等就没必要做转换了)。现在让你用Randa实现Randb。 - 通过上文分析，我们可以得到步骤如下：
- 步骤1:如果a > b，进入步骤2；
-
否则构造Randa2 = a * (Randa – 1) + Randa， 表示生成1到a2 随机数的函数。如果a2 仍小于b，继教构造 Randa3 = a * (Randa2 - 1) + Randa…直到ak > b，这时我们得到Randak , 我们记为RandA。 - 步骤2:
步骤1中我们得到了RandA(可能是Randa或Randak )，其中A > b， 我们用下述代码构造Randb：
int RandA(){};
// A > b
int Randb()
{
int num = INT_MAX:
// b * (A / b)表示最接近A且小于A的b的倍数
while(num > b * (A / b))
//这里的RandA()代表着经过n（0，1，2...n）次计算过后的RandA；详情请
//见步骤2；
num = RandA();
return num % b + 1;
}
- 从上面一系列的分析可以发现，如果
给你两个生成随机数的函数Randa和Randb， 你可以通过以下方式轻松构造Randab，生成1到a*b的随机数。
Randab = b * (Randa - 1) + Randb
Randab = a * (Randb - 1) + Randa
