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


当前回答

该算法将rand5的调用次数减少到理论最小值7/5。通过产生接下来的5个rand7数字来调用它7次。

没有任何随机位的拒绝,也不可能一直等待结果。

#!/usr/bin/env ruby

# random integer from 1 to 5
def rand5
    STDERR.putc '.'
    1 + rand( 5 )
end

@bucket = 0
@bucket_size = 0

# random integer from 1 to 7
def rand7
    if @bucket_size == 0
        @bucket = 7.times.collect{ |d| rand5 * 5**d }.reduce( &:+ )
        @bucket_size = 5
    end

    next_rand7 = @bucket%7 + 1

    @bucket      /= 7
    @bucket_size -= 1

    return next_rand7
end

35.times.each{ putc rand7.to_s }

其他回答

首先,我在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;
}

与Martin的答案相似,但却很少抛弃熵:

int rand7(void) {
  static int m = 1;
  static int r = 0;

  for (;;) {
    while (m <= INT_MAX / 5) {
      r = r + m * (rand5() - 1);
      m = m * 5;
    }
    int q = m / 7;
    if (r < q * 7) {
      int i = r % 7;
      r = r / 7;
      m = q;
      return i + 1;
    }
    r = r - q * 7;
    m = m - q * 7;
  }
}

在这里,我们在0到m-1之间建立一个随机值,并尝试通过添加尽可能多的状态来最大化m,而不会溢出(INT_MAX是C中适合int的最大值,或者您可以将其替换为任何在您的语言和体系结构中有意义的大值)。

然后;如果r落在能被7整除的最大可能区间内,那么它包含一个可行的结果,我们可以将这个区间除以7,取余数作为我们的结果,并将剩余的值返回到熵池。否则r在另一个不均匀的区间内我们就必须抛弃这个不拟合区间重新启动熵池。

与这里的流行答案相比,它调用rand5()的频率平均减少了一半。

为了提高性能,可以将除法分解为琐碎的比特旋转和lut。

为什么不简单一点呢?

int random7() {
  return random5() + (random5() % 3);
}

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

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();
?>

我想到了一个解决这个问题的有趣方法,想和大家分享一下。

function rand7() {

    var returnVal = 4;

    for (var n=0; n<3; n++) {
        var rand = rand5();

        if (rand==1||rand==2){
            returnVal+=1;
        }
        else if (rand==3||rand==4) {
            returnVal-=1;
        }
    }

    return returnVal;
}

我构建了一个测试函数,循环rand7() 10,000次,将所有返回值相加,然后除以10,000。如果rand7()工作正常,我们计算的平均值应该是4 -例如,(1+2+3+4+5+6+7 / 7)= 4。在做了多次测试后,平均值确实是4:)