给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
简单高效:
int rand7 ( void )
{
return 4; // this number has been calculated using
// rand5() and is in the range 1..7
}
(灵感来自你最喜欢的“程序员”卡通?)
其他回答
这里我们使用约定的rand(n) -> [0, n - 1]
从我读到的许多答案中,它们要么提供了一致性,要么提供了暂停保证,但不能同时提供(adam rosenfeld的第二个答案可能)。
然而,这样做是可能的。我们基本上有这样的分布:
这给[0-6]上的分布留下了一个漏洞:5和6没有 发生的概率。想象一下,现在我们试图通过移动 概率分布和求和。
事实上,我们可以把初始分布平移1,然后 重复将得到的分布与移位的初始分布相加 2,然后3,以此类推,直到7,不包括在内(我们涵盖了整个范围)。 如下图所示。颜色的顺序,对应 步骤,是蓝色->绿色->青色->白色->品红->黄色->红色。
因为每个插槽由7个移位分布中的5个覆盖(移位从 0到6),因为我们假设随机数是独立于1的 Ran5()呼叫另一个,我们获得
p(x) = 5 / 35 = 1 / 7 for all x in [0, 6]
这意味着,给定来自ran5()的7个独立随机数,我们可以 计算一个在[0-6]范围内具有均匀概率的随机数。 实际上是ran5()概率 分布甚至不需要均匀,只要样本是均匀的 独立(所以每次试验的分布保持不变) 同样,这也适用于5和7之外的其他数字。
这为我们提供了以下python函数:
def rand_range_transform(rands):
"""
returns a uniform random number in [0, len(rands) - 1]
if all r in rands are independent random numbers from the same uniform distribution
"""
return sum((x + i) for i, x in enumerate(rands)) % len(rands) # a single modulo outside the sum is enough in modulo arithmetic
可以这样使用:
rand5 = lambda : random.randrange(5)
def rand7():
return rand_range_transform([rand5() for _ in range(7)])
如果我们调用rand7() 70000次,我们可以得到:
max: 6 min: 0 mean: 2.99711428571 std: 2.00194697049
0: 10019
1: 10016
2: 10071
3: 10044
4: 9775
5: 10042
6: 10033
这很好,尽管远非完美。事实上,我们的一个假设是 在这个实现中很可能是false:我们使用一个PRNG,因此,结果 的值依赖于上一个结果。
也就是说,使用一个真正随机的数字来源,输出也应该是 真正随机的。这个算法在任何情况下都终止。
但这是有代价的:我们需要为一个rand7()调用7次rand5() 调用。
int ans = 0;
while (ans == 0)
{
for (int i=0; i<3; i++)
{
while ((r = rand5()) == 3){};
ans += (r < 3) >> i
}
}
int rand7()
{
int zero_one_or_two = ( rand5() + rand5() - 1 ) % 3 ;
return rand5() + zero_one_or_two ;
}
int randbit( void )
{
while( 1 )
{
int r = rand5();
if( r <= 4 ) return(r & 1);
}
}
int randint( int nbits )
{
int result = 0;
while( nbits-- )
{
result = (result<<1) | randbit();
}
return( result );
}
int rand7( void )
{
while( 1 )
{
int r = randint( 3 ) + 1;
if( r <= 7 ) return( r );
}
}
产生近似均匀分布的常数时间解。诀窍是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;
}