给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。


当前回答

int rand7() {
    int value = rand5()
              + rand5() * 2
              + rand5() * 3
              + rand5() * 4
              + rand5() * 5
              + rand5() * 6;
    return value%7;
}

与选定的解决方案不同,该算法将在常数时间内运行。然而,它对rand5的调用比所选解决方案的平均运行时间多2次。

请注意,这个生成器并不完美(数字0比任何其他数字都有0.0064%的可能性),但对于大多数实际目的,保证恒定的时间可能比这种不准确性更重要。

解释

这个解源于数字15624能被7整除的事实,因此,如果我们可以随机且均匀地生成从0到15624的数字,然后对7取余,我们就可以得到一个近乎均匀的rand7生成器。将rand5滚动6次,将0到15624之间的数字统一生成,并使用这些数字组成以5为基数的数字,如下所示:

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

mod 7的属性允许我们稍微简化一下方程:

5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7

So

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

就变成了

rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5

理论

15624这个数字不是随机选择的,而是可以用费马小定理来发现的,该定理指出,如果p是质数,那么

a^(p-1) = 1 mod p

这就得到,

(5^6)-1 = 0 mod 7

(5^6)-1等于

4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4

这是一个以5为底的数,因此我们可以看到,这种方法可以用于从任何随机数发生器到任何其他随机数发生器。尽管在使用指数p-1时总是会引入对0的小偏差。

为了更准确地推广这种方法,我们可以有这样一个函数:

def getRandomconverted(frm, to):
    s = 0
    for i in range(to):
        s += getRandomUniform(frm)*frm**i
    mx = 0
    for i in range(to):
        mx = (to-1)*frm**i 
    mx = int(mx/to)*to # maximum value till which we can take mod
    if s < mx:
        return s%to
    else:
        return getRandomconverted(frm, to)

其他回答

这个怎么样

rand5 () % + rand5 (2) + 2 (2) % + rand5 rand5 () (2) % + rand5 % + rand5 (2) 2

不确定这是均匀分布的。有什么建议吗?

int ans = 0;
while (ans == 0) 
{
     for (int i=0; i<3; i++) 
     {
          while ((r = rand5()) == 3){};
          ans += (r < 3) >> i
     }
}

产生近似均匀分布的常数时间解。诀窍是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;
}

我知道它已经被回答了,但这似乎是可以工作的,但我不能告诉你它是否有偏见。我的“测试”表明,这至少是合理的。

也许亚当·罗森菲尔德会好心地评论一下?

我(天真?)的想法是这样的:

积累rand5,直到有足够的随机位形成rand7。这最多需要2兰特。为了得到rand7,我使用累计值mod 7。

为了避免累加器溢出,由于累加器是mod 7,那么我取累加器的mod 7:

(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7

rand7()函数如下:

(我让rand5的范围是0-4,rand7也是0-6。)

int rand7(){
  static int    a=0;
  static int    e=0;
  int       r;
  a = a * 5 + rand5();
  e = e + 5;        // added 5/7ths of a rand7 number
  if ( e<7 ){
    a = a * 5 + rand5();
    e = e + 5;  // another 5/7ths
  }
  r = a % 7;
  e = e - 7;        // removed a rand7 number
  a = a % 7;
  return r;
}

编辑:增加了1亿次试验的结果。

'Real' rand函数mod 5或7

rand5 : 平均=1.999802 0:20003944 1:19999889 2:20003690 3:19996938 4:19995539 Rand7 : 平均=3.000111 0:14282851 1:14282879 2:14284554 3:14288546 4:14292388 5:14288736 6:14280046

我的边缘7

平均数看起来不错,数字分布也不错。

Randt : 平均=3.000080 0:14288793 1:14280135 2:14287848 3:14285277 4:14286341 5:14278663 6:14292943

面对这么复杂的答案,我觉得自己很蠢。

为什么不能:

int random1_to_7()
{
  return (random1_to_5() * 7) / 5;  
}

?