从rand(5)生成rand(7),从r
我们先来看这样一个问题， 已知rand5能等概率产生1, 2, 3, 4, 5， 现要用rand5来实现rand7（rand7的意思是要等概率产生1, 2, 3, 4, 5, 6, 7）, 该怎么搞呢？ 我看了一下网上资料， 很多都是凑出来一个结果， 没有什么过程思路， 我觉得虽然结果正确， 但总感觉所用的技巧性太强。 所以， 在文本中， 我也来凑凑热闹， 看看该如何下手， 并给出程序的实际验证结果。
我们看看rand5 + rand5 行不行。 rand5 + rand5 的结果是2, 3, 4, 5, 6, 7, 8, 9, 10, 稍微思考一下， 就知道， 这些数肯定不是等概率的， 比如2的概率要低于5的概率。 所以， 不靠谱。 我们再来看看， 既然有了1, 2, 3, 4, 5, 那很容易就有10, 20, 30, 40, 50, 且是等概率的。 假设现在又有另外一个fun函数， 能等概率随机生成0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 那么， 我们不就很轻易地构造了等概率的10, 11, 12, 13, ....., 59么？ 没错， 思路就是这样的。
所以， 我们先要让rand5产生等概率的间距数组（比如上述的10, 20, 30, 40, 50,）， 然后让rand5产生连续的待插入数字（比如上述的0, 1, 2, ..., 9,）. 现在问题是， 要多大的间距才合适呢？ 其实也很简单， 要让0, 1, 2, 3, 4刚好能插入到间距数组中。
到这里， 就比较俗套了：
第一步： 用rand5产生等概率的0, 1, 2, 3, 4，准备插入到下一步的等间距数组中, 使得插入后， 刚好合适。
第二步： 用rand5产生等概率的0, 1, 2, 3, 4, 然后为了被插入， 将其散开成0, 5, 10, 15, 20.
第三步： 将第一步插入 到第二步中， 于是， 就形成了0， 1， 2， 3， 4， 5， 6， 7， 8， ...， 20， 21， 22， 23， 24. 然后就很容易等概率地生成1, 2, 3, 4, 5, 6, 7了。
#include <iOStream>
#include <ctime>
using namespace std;
// 随机生成1-n之间的整数
int myRandom(int n)
{
return rand() % n + 1;
}
// 随机生成1, 2, 3, 4, 5
int rand5()
{
return myRandom(5);
}
int main()
{
int i = 0;
int n = 5;
int a[100] = {0};
srand(time(NULL));
// 测试100万次
for(i = 0; i < 1000000; i++)
{
a[rand5() - 1]++;
}
// 结果
for(i = 0; i < n; i++)
{
cout << a[i] << endl;
}
return 0;
}结果为：
199771
200063
200057
200602
199507
我们看到， 每个数字接近 20万次， 还算均匀。 下面， 我们用上面的rand5来生成rand7, 我们已经给出了算法， 所以下面直接给出代码和测试结果：
#include <iostream>
#include <ctime>
using namespace std;
// 随机生成1-n之间的整数
int myRandom(int n)
{
return rand() % n + 1;
}
// 随机生成1, 2, 3, 4, 5
int rand5()
{
return myRandom(5);
}
// 仅由rand5来构造rand7
int rand7()
{
while(1)
{
// 构造等概率的0, 1, 2, 3, 4, 5, 6, 6, 7, 8, ..., 20, 21, 22, 23, 24
int x = (rand5() - 1) * 5 + (rand5() - 1);
if(x >= 21) // 剔除21, 22, 23, 24
{
continue;
}
else
{
return x % 7 + 1;
}
}
}
int main()
{
int i = 0;
int n = 7;
int a[100] = {0};
srand(time(NULL));
// 测试700万次
for(i = 0; i < 7000000; i++)
{
a[rand7() - 1]++;
}
// 结果
for(i = 0; i < n; i++)
{
cout << a[i] << endl;
}
return 0;
}结果：
1000030
999648
1000338
1000311
999814
1000323
999536
还算均匀吧， OK, 本文就到此为止了， 代码很简单， 思路才重要。 有兴趣的朋友可以看看《算法导论》第五章的内容。
原文：Http://blog.csdn.net/stpeace/article/details/46672035
其实上面的rand(7)也可以用来生成rand(3),下面是我修改的代码
int rand31()
{
while (1) {
int x =(rand5()-1)*5 + (rand5()-1);
if(x >= 24){
continue;
}else{
return x%3+1;
}
}
}选取0-23作为区间，大于24时继续
下面是结果
332754
333669
333577
还比较均匀。。。。
当然了，rand(3)应该有更简洁的方法，试试再说。。。。
相关链接:http://www.cnblogs.com/dwdxdy/arcHive/2012/07/28/2613135.html
相关文章