http://www.cnblogs.com/dwdxdy/archive/2012/07/28/2613135.html
利用rand5()产生rand7().rand5()产生1到5的整数,rand7()产生1到7的整数.
解决思路与上述的练习题是一样的.利用rand5()产生的一个整数空间,然后将其映射到[1,7]的整数空间上,映射时保证概率相等,且等于1/7.
下面介绍几个有意思的实现.
1.利用预置数组
该方法简单,易理解,但是不具扩展性,需要额外存储空间.
int rand7()
{
int vals[5][5] = {
{1,2,3,4,5},
{6,7,1,2,3},
{4,5,6,7,1},
{2,3,4,5,6},
{7,0,0,0,0}
};
int result = 0;
while(result == 0)
{
int i = rand5();
int j = rand5();
result = vals[i - 1][j - 1];
}
return result;
}
2.常规实现方法
可扩展,主要分为三步,构造大的整数区间,限制整数区间,最后映射整数区间.
int rand7()
{
int i;
do{
i = 5 * (rand5() - 1) + rand5(); //产生[1,25]的整数区间
}while(i > 21); //将[1,25]整数区间控制于[1,21]
return i%7 + 1; //将[1,21]映射到[1,7]
}
3.看似正确的方法 其实错误的方法
int rand7()
{
int i;
i = rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5();
return i%7 + 1;
}
与方法2的思路一样,构造新的整数区间,但是方法3中构造的整数区间并不是等概率的.
第4代码中,将会产生5^7种可能的计算,但最终这些可能映射到[7,35]的整数区间中,但是[7,35]区间内整数的产生的概率并不相等.
例如,通过累加区间[0,1]三次,可以得到[0,3]的区间,但是[0,3]每个整数的概率并不相等,分别为1/8,3/8,3/8,1/8.
另一方法:rand7 = ((rand5() & 1) | ((rand5() & 1) << 1) | ((rand5() & 1) << 2));