给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
假设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种可能性,就再画一个随机数,将可能性数乘以5。在Perl中:
$num = 0;
$possibilities = 1;
sub rand7
{
while( $possibilities < 7 )
{
$num = $num * 5 + int(rand(5));
$possibilities *= 5;
}
my $result = $num % 7;
$num = int( $num / 7 );
$possibilities /= 7;
return $result;
}
这个表达式足以得到1 - 7之间的随机整数
int j = ( rand5()*2 + 4 ) % 7 + 1;
简单的解决方案已经被很好地覆盖了:为一个random7结果取两个random5样本,如果结果超出了产生均匀分布的范围,就重新做一次。如果你的目标是减少对random5的调用次数,这是非常浪费的——对于每个random7输出,对random5的平均调用次数是2.38,而不是2,这是由于丢弃样本的数量。
你可以通过使用更多的random5输入一次生成多个random7输出来做得更好。对于使用31位整数计算的结果,最优结果是使用12次调用random5生成9个random7输出,平均每个输出调用1.34次。它是高效的,因为244140625个结果中只有2018983个需要废弃,或者不到1%。
Python演示:
def random5():
return random.randint(1, 5)
def random7gen(n):
count = 0
while n > 0:
samples = 6 * 7**9
while samples >= 6 * 7**9:
samples = 0
for i in range(12):
samples = samples * 5 + random5() - 1
count += 1
samples //= 6
for outputs in range(9):
yield samples % 7 + 1, count
samples //= 7
count = 0
n -= 1
if n == 0: break
>>> from collections import Counter
>>> Counter(x for x,i in random7gen(10000000))
Counter({2: 1430293, 4: 1429298, 1: 1428832, 7: 1428571, 3: 1428204, 5: 1428134, 6: 1426668})
>>> sum(i for x,i in random7gen(10000000)) / 10000000.0
1.344606
产生近似均匀分布的常数时间解。诀窍是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;
}
简单高效:
int rand7 ( void )
{
return 4; // this number has been calculated using
// rand5() and is in the range 1..7
}
(灵感来自你最喜欢的“程序员”卡通?)