给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
对于范围[1,5]到[1,7],这相当于用一个5面骰子滚动一个7面骰子。
然而,如果不“浪费”随机性(或者在最坏的情况下永远运行),就无法做到这一点,因为7的所有质因数(即7)都不能整除5。因此,最好的方法是使用拒绝抽样来获得任意接近于不“浪费”随机性的结果(例如,将多个5面骰子摇到5^n“足够接近”7的幂)。这个问题的解决方案已经在其他答案中给出了。
更一般地说,用p面骰子掷k面骰子的算法将不可避免地“浪费”随机性(并且在最坏的情况下永远运行),除非“每个质数能除k也能除p”,根据B. Kloeckner的“用骰子模拟骰子”中的引理3。例如,举一个更实际的例子,p是2的幂,k是任意的。在这种情况下,这种“浪费”和无限的运行时间是不可避免的,除非k也是2的幂。
其他回答
int rand7()
{
int zero_one_or_two = ( rand5() + rand5() - 1 ) % 3 ;
return rand5() + zero_one_or_two ;
}
这是我的,它试图从多个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
def rand5():
return random.randint(1,5) #return random integers from 1 to 5
def rand7():
rand = rand5()+rand5()-1
if rand > 7: #if numbers > 7, call rand7() again
return rand7()
print rand%7 + 1
我想这将是最简单的解决方案,但到处都有人建议5*rand5() + rand5() - 5,如http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/。 有人能解释一下rand5()+rand5()-1有什么问题吗
这个解决方案受到了Rob McAfee的启发。 然而,它不需要循环,结果是一个均匀分布:
// Returns 1-5
var rnd5 = function(){
return parseInt(Math.random() * 5, 10) + 1;
}
// Helper
var lastEdge = 0;
// Returns 1-7
var rnd7 = function () {
var map = [
[ 1, 2, 3, 4, 5 ],
[ 6, 7, 1, 2, 3 ],
[ 4, 5, 6, 7, 1 ],
[ 2, 3, 4, 5, 6 ],
[ 7, 0, 0, 0, 0 ]
];
var result = map[rnd5() - 1][rnd5() - 1];
if (result > 0) {
return result;
}
lastEdge++;
if (lastEdge > 7 ) {
lastEdge = 1;
}
return lastEdge;
};
// Test the a uniform distribution
results = {}; for(i=0; i < 700000;i++) { var rand = rnd7(); results[rand] = results[rand] ? results[rand] + 1 : 1;}
console.log(results)
结果:[1:99560,2:99932,3:100355,4:100262,5:99603,6:100062,7:100226]
js小提琴
我想到了一个解决这个问题的有趣方法,想和大家分享一下。
function rand7() {
var returnVal = 4;
for (var n=0; n<3; n++) {
var rand = rand5();
if (rand==1||rand==2){
returnVal+=1;
}
else if (rand==3||rand==4) {
returnVal-=1;
}
}
return returnVal;
}
我构建了一个测试函数,循环rand7() 10,000次,将所有返回值相加,然后除以10,000。如果rand7()工作正常,我们计算的平均值应该是4 -例如,(1+2+3+4+5+6+7 / 7)= 4。在做了多次测试后,平均值确实是4:)