给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
int ans = 0;
while (ans == 0)
{
for (int i=0; i<3; i++)
{
while ((r = rand5()) == 3){};
ans += (r < 3) >> i
}
}
其他回答
这里允许作业题吗?
这个函数进行粗略的“以5为基数”的数学运算,生成0到6之间的数字。
function rnd7() {
do {
r1 = rnd5() - 1;
do {
r2=rnd5() - 1;
} while (r2 > 1);
result = r2 * 5 + r1;
} while (result > 6);
return result + 1;
}
首先,我在1点上移动ramdom5() 6次,得到7个随机数。 其次,将7个数相加得到公和。 第三,除法的余数是7。 最后加1,得到从1到7的结果。 这个方法给出了在1到7的范围内获得数字的相等概率,除了1。1的概率略高。
public int random7(){
Random random = new Random();
//function (1 + random.nextInt(5)) is given
int random1_5 = 1 + random.nextInt(5); // 1,2,3,4,5
int random2_6 = 2 + random.nextInt(5); // 2,3,4,5,6
int random3_7 = 3 + random.nextInt(5); // 3,4,5,6,7
int random4_8 = 4 + random.nextInt(5); // 4,5,6,7,8
int random5_9 = 5 + random.nextInt(5); // 5,6,7,8,9
int random6_10 = 6 + random.nextInt(5); //6,7,8,9,10
int random7_11 = 7 + random.nextInt(5); //7,8,9,10,11
//sumOfRandoms is between 28 and 56
int sumOfRandoms = random1_5 + random2_6 + random3_7 +
random4_8 + random5_9 + random6_10 + random7_11;
//result is number between 0 and 6, and
//equals 0 if sumOfRandoms = 28 or 35 or 42 or 49 or 56 , 5 options
//equals 1 if sumOfRandoms = 29 or 36 or 43 or 50, 4 options
//equals 2 if sumOfRandoms = 30 or 37 or 44 or 51, 4 options
//equals 3 if sumOfRandoms = 31 or 38 or 45 or 52, 4 options
//equals 4 if sumOfRandoms = 32 or 39 or 46 or 53, 4 options
//equals 5 if sumOfRandoms = 33 or 40 or 47 or 54, 4 options
//equals 6 if sumOfRandoms = 34 or 41 or 48 or 55, 4 options
//It means that the probabilities of getting numbers between 0 and 6 are almost equal.
int result = sumOfRandoms % 7;
//we should add 1 to move the interval [0,6] to the interval [1,7]
return 1 + result;
}
你需要的函数是rand1_7(),我写了rand1_5(),这样你就可以测试它并绘制它。
import numpy
def rand1_5():
return numpy.random.randint(5)+1
def rand1_7():
q = 0
for i in xrange(7): q+= rand1_5()
return q%7 + 1
因为1/7是一个以5为底的无限小数,所以没有(完全正确的)解可以在常数时间内运行。一个简单的解决方案是使用拒绝抽样,例如:
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7
这个循环的预期运行时间为25/21 = 1.19次迭代,但是永远循环的概率非常小。
function Rand7
put 200 into x
repeat while x > 118
put ((random(5)-1) * 25) + ((random(5)-1) * 5) + (random(5)-1) into x
end repeat
return (x mod 7) + 1
end Rand7
3次调用Rand5,平均125次中只重复6次。
把它想象成一个5x5x5的3D数组,一遍又一遍地填满1到7,还有6个空格。重新滚动空白。rand5调用在该数组中创建一个以5为基数的三位索引。
4D或更高的n维数组的重复次数会更少,但这意味着对rand5函数的更多调用将成为标准。你会在更高维度上得到递减的效率回报。在我看来,三个似乎是一个很好的折衷方案,但我还没有对它们进行测试。它是特定于rand5实现的。