给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
这里似乎没有提到的另一个答案:
int rand7() {
int r = 7 / 2;
for (int i = 0; i < 28; i++)
r = ((rand5() - 1) * 7 + r) / 5;
return r + 1;
}
在每次迭代中,r是一个0到6之间的随机值。它被追加(以7为基数)到一个0到4(包括4)之间的随机值,结果除以5,得到一个0到6(包括6)范围内的新随机值。R开始时有很大的偏差(R = 3是非常有偏差的!),但每次迭代都将偏差除以5。
这种方法不是完全均匀的;然而,偏差是微乎其微的。数量级为1/(2**64)这种方法的重要之处在于它具有恒定的执行时间(假设rand5()也具有恒定的执行时间)。理论上不需要担心一个不走运的调用可能永远迭代地选择坏值。
此外,还有一个讽刺的回答(有意无意,它已经被覆盖了):
1-5已经在1-7的范围内,因此下面是一个有效的实现:
int rand7() {
return rand5();
}
问题没有要求均匀分布。
其他回答
这里允许作业题吗?
这个函数进行粗略的“以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到5rand5()范围内随机整数的函数,编写一个生成1到7rand7()范围内随机整数的函数
在我建议的解决方案中,我只调用rand5一次
真正的解决方案
float rand7()
{
return (rand5() * 7.0) / 5.0 ;
}
这里的分布是缩放的,所以它直接取决于rand5的分布
整数解
int rand7()
{
static int prev = 1;
int cur = rand5();
int r = cur * prev; // 1-25
float f = r / 4.0; // 0.25-6.25
f = f - 0.25; // 0-6
f = f + 1.0; // 1-7
prev = cur;
return (int)f;
}
这里的分布取决于rand7(i) ~ rand5(i) * rand5(i-1)
rand7(0) ~ rand5(0) * 1
int getOneToSeven(){
int added = 0;
for(int i = 1; i<=7; i++){
added += getOneToFive();
}
return (added)%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次迭代,但是永远循环的概率非常小。
我知道它已经被回答了,但这似乎是可以工作的,但我不能告诉你它是否有偏见。我的“测试”表明,这至少是合理的。
也许亚当·罗森菲尔德会好心地评论一下?
我(天真?)的想法是这样的:
积累rand5,直到有足够的随机位形成rand7。这最多需要2兰特。为了得到rand7,我使用累计值mod 7。
为了避免累加器溢出,由于累加器是mod 7,那么我取累加器的mod 7:
(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7
rand7()函数如下:
(我让rand5的范围是0-4,rand7也是0-6。)
int rand7(){
static int a=0;
static int e=0;
int r;
a = a * 5 + rand5();
e = e + 5; // added 5/7ths of a rand7 number
if ( e<7 ){
a = a * 5 + rand5();
e = e + 5; // another 5/7ths
}
r = a % 7;
e = e - 7; // removed a rand7 number
a = a % 7;
return r;
}
编辑:增加了1亿次试验的结果。
'Real' rand函数mod 5或7
rand5 : 平均=1.999802 0:20003944 1:19999889 2:20003690 3:19996938 4:19995539 Rand7 : 平均=3.000111 0:14282851 1:14282879 2:14284554 3:14288546 4:14292388 5:14288736 6:14280046
我的边缘7
平均数看起来不错,数字分布也不错。
Randt : 平均=3.000080 0:14288793 1:14280135 2:14287848 3:14285277 4:14286341 5:14278663 6:14292943