算法-一种rand表示另一种
题目: 给定一个函数rand5(),该函数可以随机生成1-5的整数,且生成概率一样。现要求使用该函数构造函数rand7(),使函数rand7()可以随机等概率的生成1-7的整数。
思路
正确的方法是利用rand5()函数生成1-25之间的数字,然后将其中的1-21映射成1-7,丢弃22-25。例如生成(1,1),(1,2),(1,3),则看成rand7()中的1,如果出现剩下的4种,则丢弃重新生成。
代码
public class Test {
public int rand7() {
int x = 22;
while(x > 21) {
x = rand5() + (rand5() - 1)*5;
}
return 1 + x%7;
}
}
备注
这种思想是基于,rand()产生[0,N-1],把rand()视为N进制的一位数产生器,那么可以使用rand()*N+rand()来产生2位的N进制数,以此类推,可以产生3位,4位,5位...的N进制数。这种按构造N进制数的方式生成的随机数,必定能保证随机,而相反,借助其他方式来使用rand()产生随机数(如 rand5() + rand()%3 )都是不能保证概率平均的。