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


当前回答

为什么不除以5再乘以7,然后四舍五入呢?(当然,你必须使用浮点数no.)

它比其他解决方案更简单、更可靠(真的吗?)例如,在Python中:

def ranndomNo7():
    import random
    rand5 = random.randint(4)    # Produces range: [0, 4]
    rand7 = int(rand5 / 5 * 7)   # /5, *7, +0.5 and floor()
    return rand7

这不是很容易吗?

其他回答

function rand7() {
    while (true) { //lowest base 5 random number > 7 reduces memory
        int num = (rand5()-1)*5 + rand5()-1;
    if (num < 21)  // improves performance
        return 1 + num%7;
    }
}

Python代码:

from random import randint
def rand7():
    while(True):
        num = (randint(1, 5)-1)*5 + randint(1, 5)-1
        if num < 21:
                return 1 + num%7

100000次运行的测试分布:

>>> rnums = []
>>> for _ in range(100000):
    rnums.append(rand7())
>>> {n:rnums.count(n) for n in set(rnums)}
{1: 15648, 2: 15741, 3: 15681, 4: 15847, 5: 15642, 6: 15806, 7: 15635}
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 );
    }
}

我玩了一下,我为这个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)的方法,而是生成几乎均匀分布的值。

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

这个答案更像是一个从Rand5函数中获得最大熵的实验。因此,T有点不清楚,几乎可以肯定比其他实现慢得多。

假设0-4为均匀分布,0-6为均匀分布:

public class SevenFromFive
{
  public SevenFromFive()
  {
    // this outputs a uniform ditribution but for some reason including it 
    // screws up the output distribution
    // open question Why?
    this.fifth = new ProbabilityCondensor(5, b => {});
    this.eigth = new ProbabilityCondensor(8, AddEntropy);
  } 

  private static Random r = new Random();
  private static uint Rand5()
  {
    return (uint)r.Next(0,5);
  }

  private class ProbabilityCondensor
  {
    private readonly int samples;
    private int counter;
    private int store;
    private readonly Action<bool> output;

    public ProbabilityCondensor(int chanceOfTrueReciprocal,
      Action<bool> output)
    {
      this.output = output;
      this.samples = chanceOfTrueReciprocal - 1;  
    }

    public void Add(bool bit)
    {
      this.counter++;
      if (bit)
        this.store++;   
      if (counter == samples)
      {
        bool? e;
        if (store == 0)
          e = false;
        else if (store == 1)
          e = true;
        else
          e = null;// discard for now       
        counter = 0;
        store = 0;
        if (e.HasValue)
          output(e.Value);
      }
    }
  }

  ulong buffer = 0;
  const ulong Mask = 7UL;
  int bitsAvail = 0;
  private readonly ProbabilityCondensor fifth;
  private readonly ProbabilityCondensor eigth;

  private void AddEntropy(bool bit)
  {
    buffer <<= 1;
    if (bit)
      buffer |= 1;      
    bitsAvail++;
  }

  private void AddTwoBitsEntropy(uint u)
  {
    buffer <<= 2;
    buffer |= (u & 3UL);    
    bitsAvail += 2;
  }

  public uint Rand7()
  {
    uint selection;   
    do
    {
      while (bitsAvail < 3)
      {
        var x = Rand5();
        if (x < 4)
        {
          // put the two low order bits straight in
          AddTwoBitsEntropy(x);
          fifth.Add(false);
        }
        else
        { 
          fifth.Add(true);
        }
      }
      // read 3 bits
      selection = (uint)((buffer & Mask));
      bitsAvail -= 3;     
      buffer >>= 3;
      if (selection == 7)
        eigth.Add(true);
      else
        eigth.Add(false);
    }
    while (selection == 7);   
    return selection;
  }
}

每次调用Rand5添加到缓冲区的比特数目前是4/5 * 2,所以是1.6。 如果包括1/5的概率值,则增加0.05,因此增加1.65,但请参阅代码中的注释,我不得不禁用它。

调用Rand7消耗的比特数= 3 + 1/8 *(3 + 1/8 *(3 + 1/8 *(… 这是3 + 3/8 + 3/64 + 3/512…大约是3.42

通过从7中提取信息,我每次调用回收1/8*1/7位,大约0.018

这使得每次调用的净消耗为3.4比特,这意味着每一次Rand7调用到Rand5的比率为2.125。最优值应该是2.1。

我可以想象这种方法比这里的许多其他方法都要慢得多,除非调用Rand5的代价非常昂贵(比如调用一些外部熵源)。