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


当前回答

只要没有剩下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;
}

其他回答

从一个扩大浮动范围的链接来到这里。这个更有趣。而不是我是如何得出结论的,我突然想到,对于一个给定的随机整数生成函数f,以“基数”b(在这种情况下是4,我会告诉为什么),它可以展开如下:

(b^0 * f() + b^1 * f() + b^2 * f() .... b^p * f()) / (b^(p+1) - 1) * (b-1)

这将把随机生成器转换为FLOAT生成器。我将在这里定义2个参数b和p。虽然这里的“基数”是4,但b实际上可以是任何东西,它也可以是无理数等p,我称之为精度是你想要的浮点生成器的良好粒度的程度。可以把这看作是对rand7的每次调用对rand5的调用数。

但我意识到,如果你把b设为底数+1(在这种情况下是4+1 = 5),这是一个最佳点,你会得到均匀的分布。首先摆脱这个1-5生成器,它实际上是rand4() + 1:

function rand4(){
    return Math.random() * 5 | 0;
}

为了达到这个目的,你可以用rand5()-1替换rand4

接下来是将rand4从整数生成器转换为浮点生成器

function toFloat(f,b,p){
    b = b || 2;
    p = p || 3;
    return (Array.apply(null,Array(p))
    .map(function(d,i){return f()})
    .map(function(d,i){return Math.pow(b,i)*d})
    .reduce(function(ac,d,i){return ac += d;}))
    /
    (
        (Math.pow(b,p) - 1)
        /(b-1)
    )
}

这将把我写的第一个函数应用到一个给定的rand函数。试一试:

toFloat(rand4) //1.4285714285714286 base = 2, precision = 3
toFloat(rand4,3,4) //0.75 base = 3, precision = 4
toFloat(rand4,4,5) //3.7507331378299122 base = 4, precision = 5
toFloat(rand4,5,6) //0.2012288786482335 base = 5, precision =6
...

现在,您可以将这个浮动范围(0-4 include)转换为任何其他浮动范围,然后将其降级为整数。这里我们的底是4,因为我们处理的是rand4,因此b=5的值会给你一个均匀分布。当b增长超过4时,你将开始在分布中引入周期性间隙。我测试了从2到8的b值,每个值都有3000分,并与原生数学进行了比较。随机的javascript,在我看来甚至比本机本身更好:

http://jsfiddle.net/ibowankenobi/r57v432t/

对于上面的链接,单击分布顶部的“bin”按钮以减小分箱大小。最后一个图表是原生数学。随机的,第四个d=5是均匀的。

在你得到浮动范围后,要么与7相乘并抛出小数部分,要么与7相乘,减去0.5并四舍五入:

((toFloat(rand4,5,6)/4 * 7) | 0) + 1   ---> occasionally you'll get 8 with 1/4^6 probability.
Math.round((toFloat(rand4,5,6)/4 * 7) - 0.5) + 1 --> between 1 and 7
function Rand7
   put 200 into x
   repeat while x > 118
      put ((random(5)-1) * 25) + ((random(5)-1) * 5) + (random(5)-1) into x
   end repeat
   return (x mod 7) + 1
end Rand7

3次调用Rand5,平均125次中只重复6次。

把它想象成一个5x5x5的3D数组,一遍又一遍地填满1到7,还有6个空格。重新滚动空白。rand5调用在该数组中创建一个以5为基数的三位索引。

4D或更高的n维数组的重复次数会更少,但这意味着对rand5函数的更多调用将成为标准。你会在更高维度上得到递减的效率回报。在我看来,三个似乎是一个很好的折衷方案,但我还没有对它们进行测试。它是特定于rand5实现的。

rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1

编辑:这并不奏效。误差约为千分之二(假设是完美的rand5)。桶得到:

value   Count  Error%
1       11158  -0.0035
2       11144  -0.0214
3       11144  -0.0214
4       11158  -0.0035
5       11172  +0.0144
6       11177  +0.0208
7       11172  +0.0144

通过转换到的和

n   Error%
10  +/- 1e-3,
12  +/- 1e-4,
14  +/- 1e-5,
16  +/- 1e-6,
...
28  +/- 3e-11

似乎每增加2就增加一个数量级

BTW:上面的误差表不是通过采样产生的,而是通过以下递归关系产生的:

P [x,n]是给定n次调用rand5,输出=x可能发生的次数。

  p[1,1] ... p[5,1] = 1
  p[6,1] ... p[7,1] = 0

  p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1]
  p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1]
  p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1]
  p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1]
  p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1]
  p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1]
  p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1]

这类似于@RobMcAfee,除了我使用魔术数字而不是2维数组。

int rand7() {
    int m = 1203068;
    int r = (m >> (rand5() - 1) * 5 + rand5() - 1) & 7;

    return (r > 0) ? r : rand7();
}

//返回0-5之间概率相等的随机数 函数rand5() { return Math.floor(Math.random() * 6); } //返回0-7之间概率相等的随机数 函数rand7() { If (rand5() % 2 == 0 && rand5() % 2 == 0) { 返回6 + rand5() % 2; }其他{ 返回rand5 (); } } console.log (rand7 ());