给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
假设rand给予所有位相同的权重,然后用上界进行掩码。
int i = rand(5) ^ (rand(5) & 2);
Rand(5)只能返回:1b, 10b, 11b, 100b, 101b。有时候你只需要考虑设置2位。
其他回答
下面是Adam回答的Python实现。
import random
def rand5():
return random.randint(1, 5)
def rand7():
while True:
r = 5 * (rand5() - 1) + rand5()
#r is now uniformly random between 1 and 25
if (r <= 21):
break
#result is now uniformly random between 1 and 7
return r % 7 + 1
我喜欢把我正在研究的算法扔进Python,这样我就可以摆弄它们,我想我把它贴在这里,希望它对外面的人有用,而不是花很长时间来拼凑。
假设rand(n)在这里表示“从0到n-1均匀分布的随机整数”,下面是使用Python的randint的代码示例,它具有这种效果。它只使用randint(5)和常量来产生randint(7)的效果。其实有点傻
from random import randint
sum = 7
while sum >= 7:
first = randint(0,5)
toadd = 9999
while toadd>1:
toadd = randint(0,5)
if toadd:
sum = first+5
else:
sum = first
assert 7>sum>=0
print sum
(我剽窃了亚当·罗森菲尔德的答案,使其运行速度提高了7%左右。)
假设rand5()返回分布相等的{0,1,2,3,4}中的一个,目标是返回分布相等的{0,1,2,3,4,5,6}。
int rand7() {
i = 5 * rand5() + rand5();
max = 25;
//i is uniform among {0 ... max-1}
while(i < max%7) {
//i is uniform among {0 ... (max%7 - 1)}
i *= 5;
i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
max %= 7;
max *= 5; //once again, i is uniform among {0 ... max-1}
}
return(i%7);
}
我们在跟踪这个循环在变量max中所能产生的最大值。如果到目前为止的结果在max%7和max-1之间,那么结果将均匀分布在该范围内。如果不是,则使用余数,余数是0到max%7-1之间的随机数,然后再次调用rand()来生成一个新的数字和一个新的max。然后我们重新开始。
编辑:在这个方程中,期望调用rand5()的次数是x:
x = 2 * 21/25
+ 3 * 4/25 * 14/20
+ 4 * 4/25 * 6/20 * 28/30
+ 5 * 4/25 * 6/20 * 2/30 * 7/10
+ 6 * 4/25 * 6/20 * 2/30 * 3/10 * 14/15
+ (6+x) * 4/25 * 6/20 * 2/30 * 3/10 * 1/15
x = about 2.21 calls to rand5()
我首先想到的是这个。但我不知道它是否均匀分布。 在python中实现
进口随机 def rand5 (): 返回random.randint(1、5) def rand7 (): 返回((rand5() -1) * rand5()) %7)+1
这是我想到的答案,但这些复杂的答案让我认为这是完全错误的/:))
import random
def rand5():
return float(random.randint(0,5))
def rand7():
random_val = rand5()
return float(random.randint((random_val-random_val),7))
print rand7()