给定一个函数,它产生的是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 }