给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
什么是简单的解决方案?(rand5() + rand5()) % 7 + 1 减少内存使用或在较慢的CPU上运行的有效解决方案是什么?是的,这是有效的,因为它只调用rand5()两次,空间复杂度为O(1)
考虑rand5()给出从1到5(包括)的随机数。 (1 + 1) % 7 + 1 = 3 (1 + 2) % 7 + 1 = 4 (1 + 3) % 7 + 1 = 5 (1 + 4) % 7 + 1 = 6 (1 + 5) % 7 + 1 = 7
(2 + 1) % 7 + 1 = 4 (2 + 2) % 7 + 1 = 5 (2 + 3) % 7 + 1 = 6 (2 + 4) % 7 + 1 = 7 (2 + 5) % 7 + 1 = 1 .
(5 + 1) % 7 + 1 = 7 (5 + 2) % 7 + 1 = 1 (5 + 3) % 7 + 1 = 2 (5 + 4) % 7 + 1 = 3 (5 + 5) % 7 + 1 = 4 .
等等
其他回答
首先,我在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;
}
产生近似均匀分布的常数时间解。诀窍是625恰好能被7整除当你增加到这个范围时,你可以得到均匀的分布。
编辑:我的错,我算错了,但我不会把它拉下来,以防有人觉得它有用/有趣。毕竟它确实有效……:)
int rand5()
{
return (rand() % 5) + 1;
}
int rand25()
{
return (5 * (rand5() - 1) + rand5());
}
int rand625()
{
return (25 * (rand25() - 1) + rand25());
}
int rand7()
{
return ((625 * (rand625() - 1) + rand625()) - 1) % 7 + 1;
}
亚当·罗森菲尔德正确答案的前提是:
X = 5^n(在他的例子中,n=2) 操作n个rand5次调用以获得范围[1,x]内的数字y Z = ((int)(x / 7)) * 7 如果y > z,再试一次。否则返回y % 7 + 1
当n = 2时,有4种可能:y ={22,23,24,25}。如果你使用n = 6,你只有1个扔掉的东西:y ={15625}。
5^6 is 15625 7 times 2232 is 15624
你又给rand5个电话。但是,您获得一个丢弃值(或无限循环)的机会要低得多。如果有办法让y没有可能的一次性值,我还没有找到它。
这是我在看过别人的答案后得出的最简单的答案:
def r5tor7():
while True:
cand = (5 * r5()) + r5()
if cand < 27:
return cand
Cand在[6,27]范围内,如果r5()的可能结果是均匀分布的,则可能结果是均匀分布的。你可以用下面的代码来测试我的答案:
from collections import defaultdict
def r5_outcome(n):
if not n:
yield []
else:
for i in range(1, 6):
for j in r5_outcome(n-1):
yield [i] + j
def test_r7():
d = defaultdict(int)
for x in r5_outcome(2):
s = sum([x[i] * 5**i for i in range(len(x))])
if s < 27:
d[s] += 1
print len(d), d
R5_outcome(2)生成r5()结果的所有可能组合。我使用与解决方案代码中相同的筛选器进行测试。你可以看到所有的结果都是相等的,因为它们有相同的值。
int ans = 0;
while (ans == 0)
{
for (int i=0; i<3; i++)
{
while ((r = rand5()) == 3){};
ans += (r < 3) >> i
}
}