给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
简单高效:
int rand7 ( void )
{
return 4; // this number has been calculated using
// rand5() and is in the range 1..7
}
(灵感来自你最喜欢的“程序员”卡通?)
其他回答
上面引用了一些优雅的算法,但这里有一种方法可以接近它,尽管它可能是迂回的。我假设的值是从0开始的。
R2 =给出小于2的随机数生成器(样本空间= {0,1}) R8 =给出小于8的随机数生成器(样本空间= {0,1,2,3,4,5,6,7})
为了从R2生成R8,您将运行R2三次,并将所有3次运行的组合结果作为3位二进制数使用。下面是R2运行三次时的值范围:
0, 0, 0 --> 0 . . 1, 1, 1 --> 7
现在要从R8生成R7,我们只需再次运行R7,如果它返回7:
int R7() {
do {
x = R8();
} while (x > 6)
return x;
}
迂回的解决方案是从R5生成R2(就像我们从R8生成R7一样),然后从R2生成R8,然后从R8生成R7。
面对这么复杂的答案,我觉得自己很蠢。
为什么不能:
int random1_to_7()
{
return (random1_to_5() * 7) / 5;
}
?
对于0-7的值,你有以下内容:
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
从左到右,Rand5()有p(1) ={2/ 5,2 / 5,3 /5}。因此,如果我们补这些概率分布(~Rand5()),我们应该能够使用它来生成我们的数字。我稍后会给出解决方案。有人有什么想法吗?
R
rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1
编辑:这并不奏效。误差约为千分之二(假设是完美的rand5)。桶得到:
value Count Error%
1 11158 -0.0035
2 11144 -0.0214
3 11144 -0.0214
4 11158 -0.0035
5 11172 +0.0144
6 11177 +0.0208
7 11172 +0.0144
通过转换到的和
n Error%
10 +/- 1e-3,
12 +/- 1e-4,
14 +/- 1e-5,
16 +/- 1e-6,
...
28 +/- 3e-11
似乎每增加2就增加一个数量级
BTW:上面的误差表不是通过采样产生的,而是通过以下递归关系产生的:
P [x,n]是给定n次调用rand5,输出=x可能发生的次数。
p[1,1] ... p[5,1] = 1
p[6,1] ... p[7,1] = 0
p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1]
p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1]
p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1]
p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1]
p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1]
p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1]
p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1]
为什么这行不通?除了对rand5()的额外调用之外?
i = rand5() + rand5() + (rand5() - 1) //Random number between 1 and 14
i = i % 7 + 1;