给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是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 random7() {
  return random5() + (random5() % 3);
}

由于取模,在这个解中得到1和7的几率较低,然而,如果你只是想要一个快速和可读的解,这是一种方法。

以下是我的发现:

Random5产生1~5的范围,随机分布 如果我们运行3次并将它们加在一起,我们将得到3~15个随机分布的范围 在3~15范围内执行算术 (3~15) - 1 = (2~14) (2~14)/2 = (1~7)

然后我们得到1~7的范围,这是我们正在寻找的Random7。

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 );
    }
}

这里允许作业题吗?

这个函数进行粗略的“以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;
}

PHP解决方案

<?php
function random_5(){
    return rand(1,5);
}


function random_7(){
 $total = 0;

    for($i=0;$i<7;$i++){
        $total += random_5();
    }

    return ($total%7)+1; 
}

echo random_7();
?>