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


当前回答

我玩了一下,我为这个Rand(7)算法写了“测试环境”。例如,如果你想尝试哪种分布给你的算法,或者需要多少次迭代才能生成所有不同的随机值(对于Rand(7) 1-7),你可以使用它。

我的核心算法是:

return (Rand5() + Rand5()) % 7 + 1;

和亚当·罗森菲尔德的分布一样均匀。(我将其包含在代码片段中)

private static int Rand7WithRand5()
{
    //PUT YOU FAVOURITE ALGORITHM HERE//

    //1. Stackoverflow winner
    int i;
    do
    {
        i = 5 * (Rand5() - 1) + Rand5(); // i is now uniformly random between 1 and 25
    } while (i > 21);
    // i is now uniformly random between 1 and 21
    return i % 7 + 1;

    //My 2 cents
    //return (Rand5() + Rand5()) % 7 + 1;
}

这个“测试环境”可以采用任何Rand(n)算法并测试和评估它(分布和速度)。只需将代码放入“Rand7WithRand5”方法并运行代码片段。

一些观察:

亚当·罗森菲尔德(Adam Rosenfield)的算法并不比我的算法分布得更好。不管怎样,两种算法的分布都很糟糕。 本机Rand7(随机的。Next(1,8))完成,因为它在大约200+迭代中生成了给定间隔内的所有成员,Rand7WithRand5算法的顺序为10k(约30-70k) 真正的挑战不是编写从Rand(5)生成Rand(7)的方法,而是生成几乎均匀分布的值。

其他回答

简单高效:

int rand7 ( void )
{
    return 4; // this number has been calculated using
              // rand5() and is in the range 1..7
}

(灵感来自你最喜欢的“程序员”卡通?)

只需要缩放第一个函数的输出

0) you have a number in range 1-5
1) subtract 1 to make it in range 0-4
2) multiply by (7-1)/(5-1) to make it in range 0-6
3) add 1 to increment the range: Now your result is in between 1-7
int getOneToSeven(){
    int added = 0;
    for(int i = 1; i<=7; i++){
        added += getOneToFive();
    }
    return (added)%7+1;
}

Here is a solution that tries to minimize the number of calls to rand5() while keeping the implementation simple and efficient; in particular, it does not require arbitrary large integers unlike Adam Rosenfield’s second answer. It exploits the fact that 23/19 = 1.21052... is a good rational approximation to log(7)/log(5) = 1.20906..., thus we can generate 19 random elements of {1,...,7} out of 23 random elements of {1,...,5} by rejection sampling with only a small rejection probability. On average, the algorithm below takes about 1.266 calls to rand5() for each call to rand7(). If the distribution of rand5() is uniform, so is rand7().

uint_fast64_t pool;

int capacity = 0;

void new_batch (void)
{
  uint_fast64_t r;
  int i;

  do {
    r = 0;
    for (i = 0; i < 23; i++)
      r = 5 * r + (rand5() - 1);
  } while (r >= 11398895185373143ULL);  /* 7**19, a bit less than 5**23 */

  pool = r;
  capacity = 19;
}

int rand7 (void)
{
  int r;

  if (capacity == 0)
    new_batch();

  r = pool % 7;
  pool /= 7;
  capacity--;

  return r + 1;
}

下面是Adam回答的Python实现。

import random

def rand5():
    return random.randint(1, 5)

def rand7():
    while True:
        r = 5 * (rand5() - 1) + rand5()
        #r is now uniformly random between 1 and 25
        if (r <= 21):
            break
    #result is now uniformly random between 1 and 7
    return r % 7 + 1

我喜欢把我正在研究的算法扔进Python,这样我就可以摆弄它们,我想我把它贴在这里,希望它对外面的人有用,而不是花很长时间来拼凑。