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


当前回答

下面是一个利用c++ 11特性的答案

#include <functional>
#include <iostream>
#include <ostream>
#include <random>

int main()
{
    std::random_device rd;
    unsigned long seed = rd();
    std::cout << "seed = " << seed << std::endl;

    std::mt19937 engine(seed);

    std::uniform_int_distribution<> dist(1, 5);
    auto rand5 = std::bind(dist, engine);

    const int n = 20;
    for (int i = 0; i != n; ++i)
    {
        std::cout << rand5() << " ";
    }
    std::cout << std::endl;

    // Use a lambda expression to define rand7
    auto rand7 = [&rand5]()->int
    {
        for (int result = 0; ; result = 0)
        {
            // Take advantage of the fact that
            // 5**6 = 15625 = 15624 + 1 = 7 * (2232) + 1.
            // So we only have to discard one out of every 15625 numbers generated.

            // Generate a 6-digit number in base 5
            for (int i = 0; i != 6; ++i)
            {
                result = 5 * result + (rand5() - 1);
            }

            // result is in the range [0, 15625)
            if (result == 15625 - 1)
            {
                // Discard this number
                continue;
            }

            // We now know that result is in the range [0, 15624), a range that can
            // be divided evenly into 7 buckets guaranteeing uniformity
            result /= 2232;
            return 1 + result;
        }
    };

    for (int i = 0; i != n; ++i)
    {
        std::cout << rand7() << " ";
    }
    std::cout << std::endl;

    return 0;
}

其他回答

这个问题的主要概念是关于正态分布的,这里提供了一个简单的递归解决这个问题的方法

假设我们已经在我们的作用域中有rand5():

def rand7():
    # twoway = 0 or 1 in the same probability
    twoway = None
    while not twoway in (1, 2):
        twoway = rand5()
    twoway -= 1

    ans = rand5() + twoway * 5

    return ans if ans in range(1,8) else rand7()

解释

我们可以把这个程序分成两个部分:

循环rand5()直到我们找到1或2,这意味着我们有1/2的概率在变量中有1或2 复合ans by rand5() + twoway * 5,这正是rand10()的结果,如果这不符合我们的需要(1~7),然后我们再次运行rand7。

附注:我们不能在第二部分直接运行while循环,因为双向的每个概率都需要是单独的。

但是有一个权衡,因为第一部分中的while循环和return语句中的递归,这个函数不能保证执行时间,它实际上是无效的。

结果

我做了一个简单的测试来观察我的答案的分布。

result = [ rand7() for x in xrange(777777) ]

ans = {
    1: 0,
    2: 0,
    3: 0,
    4: 0,
    5: 0,
    6: 0,
    7: 0,
}

for i in result:
    ans[i] += 1

print ans

它给了

{1: 111170, 2: 110693, 3: 110651, 4: 111260, 5: 111197, 6: 111502, 7: 111304}

因此,我们可以知道这个答案是正态分布。

简单的答案

如果你不关心这个函数的执行时间,下面是一个基于我上面给出的答案的简化答案:

def rand7():
    ans = rand5() + (rand5()-1) * 5
    return ans if ans < 8 else rand7()

这增加了大于8的值的概率,但这可能是这个问题的最短答案。

这是我的,它试图从多个rand5()函数调用中重新创建Math.random(),通过使用“加权分数”(?)重新构造一个单位间隔(Math.random()的输出范围)。然后使用这个随机单位间隔产生一个1到7之间的随机整数:

function rand5(){
  return Math.floor(Math.random()*5)+1;
}
function rand7(){
  var uiRandom=0;
  var div=1;
  for(var i=0; i<7; i++){
    div*=5;
    var term=(rand5()-1)/div;
    uiRandom+=term;
  }
  //return uiRandom;
  return Math.floor(uiRandom*7)+1; 
}

解释一下:我们取一个0-4之间的随机整数(只是rand5()-1),然后将每个结果乘以1/ 5,1 / 25,1 /125,…然后把它们加起来。这类似于二元加权分数的工作原理;相反,我认为我们将其称为五(以5为底)加权分数:产生一个从0 - 0.999999作为一系列(1/5)^n项的数字。

修改函数以获取任何输入/输出随机整数范围应该是简单的。上面的代码可以在重写为闭包时进行优化。


或者,我们也可以这样做:

function rand5(){
  return Math.floor(Math.random()*5)+1;
}
function rand7(){
  var buffer=[];
  var div=1;
  for (var i=0; i<7; i++){
    buffer.push((rand5()-1).toString(5));
    div*=5;
  }
  var n=parseInt(buffer.join(""),5);
  var uiRandom=n/div;
  //return uiRandom;
  return Math.floor(uiRandom*7)+1; 
}

我们不需要费力地构造一个五进制(以5为基数)加权分数,而是实际地构造一个五进制数,并将其转化为一个分数(0—0.9999…和前面一样),然后从那里计算随机的1- 7位数字。

上面的结果(代码片段#2:运行3次,每次100,000次调用):

1: 14263; 2: 14414; 3: 14249; 4: 14109; 5: 14217; 6: 14361; 7: 14387 1: 14205; 2: 14394; 3: 14238; 4: 14187; 5: 14384; 6: 14224; 7: 14368 1: 14425; 2: 14236; 3: 14334; 4: 14232; 5: 14160; 6: 14320; 7: 14293

亚当·罗森菲尔德正确答案的前提是:

X = 5^n(在他的例子中,n=2) 操作n个rand5次调用以获得范围[1,x]内的数字y Z = ((int)(x / 7)) * 7 如果y > z,再试一次。否则返回y % 7 + 1

当n = 2时,有4种可能:y ={22,23,24,25}。如果你使用n = 6,你只有1个扔掉的东西:y ={15625}。

5^6 is 15625 7 times 2232 is 15624

你又给rand5个电话。但是,您获得一个丢弃值(或无限循环)的机会要低得多。如果有办法让y没有可能的一次性值,我还没有找到它。

产生近似均匀分布的常数时间解。诀窍是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的调用次数减少到理论最小值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 }