给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
Here's a solution that fits entirely within integers and is within about 4% of optimal (i.e. uses 1.26 random numbers in {0..4} for every one in {0..6}). The code's in Scala, but the math should be reasonably clear in any language: you take advantage of the fact that 7^9 + 7^8 is very close to 5^11. So you pick an 11 digit number in base 5, and then interpret it as a 9 digit number in base 7 if it's in range (giving 9 base 7 numbers), or as an 8 digit number if it's over the 9 digit number, etc.:
abstract class RNG {
def apply(): Int
}
class Random5 extends RNG {
val rng = new scala.util.Random
var count = 0
def apply() = { count += 1 ; rng.nextInt(5) }
}
class FiveSevener(five: RNG) {
val sevens = new Array[Int](9)
var nsevens = 0
val to9 = 40353607;
val to8 = 5764801;
val to7 = 823543;
def loadSevens(value: Int, count: Int) {
nsevens = 0;
var remaining = value;
while (nsevens < count) {
sevens(nsevens) = remaining % 7
remaining /= 7
nsevens += 1
}
}
def loadSevens {
var fivepow11 = 0;
var i=0
while (i<11) { i+=1 ; fivepow11 = five() + fivepow11*5 }
if (fivepow11 < to9) { loadSevens(fivepow11 , 9) ; return }
fivepow11 -= to9
if (fivepow11 < to8) { loadSevens(fivepow11 , 8) ; return }
fivepow11 -= to8
if (fivepow11 < 3*to7) loadSevens(fivepow11 % to7 , 7)
else loadSevens
}
def apply() = {
if (nsevens==0) loadSevens
nsevens -= 1
sevens(nsevens)
}
}
如果你将一个测试粘贴到解释器中(实际上是REPL),你会得到:
scala> val five = new Random5
five: Random5 = Random5@e9c592
scala> val seven = new FiveSevener(five)
seven: FiveSevener = FiveSevener@143c423
scala> val counts = new Array[Int](7)
counts: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0)
scala> var i=0 ; while (i < 100000000) { counts( seven() ) += 1 ; i += 1 }
i: Int = 100000000
scala> counts
res0: Array[Int] = Array(14280662, 14293012, 14281286, 14284836, 14287188,
14289332, 14283684)
scala> five.count
res1: Int = 125902876
分布很好,很平坦(在每个箱子中,10^8的1/7大约在10k范围内,就像预期的近似高斯分布一样)。
其他回答
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();
?>
这里是我的一般实现,在给定一个范围为[0,B-1]的均匀发生器的情况下,生成范围为[0,N-1]的均匀。
public class RandomUnif {
public static final int BASE_NUMBER = 5;
private static Random rand = new Random();
/** given generator, returns uniform integer in the range 0.. BASE_NUMBER-1
public static int randomBASE() {
return rand.nextInt(BASE_NUMBER);
}
/** returns uniform integer in the range 0..n-1 using randomBASE() */
public static int randomUnif(int n) {
int rand, factor;
if( n <= 1 ) return 0;
else if( n == BASE_NUMBER ) return randomBASE();
if( n < BASE_NUMBER ) {
factor = BASE_NUMBER / n;
do
rand = randomBASE() / factor;
while(rand >= n);
return rand;
} else {
factor = (n - 1) / BASE_NUMBER + 1;
do {
rand = factor * randomBASE() + randomUnif(factor);
} while(rand >= n);
return rand;
}
}
}
不是特别高效,但一般和紧凑。对基生成器的均值调用:
n calls
2 1.250
3 1.644
4 1.252
5 1.000
6 3.763
7 3.185
8 2.821
9 2.495
10 2.250
11 3.646
12 3.316
13 3.060
14 2.853
15 2.650
16 2.814
17 2.644
18 2.502
19 2.361
20 2.248
21 2.382
22 2.277
23 2.175
24 2.082
25 2.000
26 5.472
27 5.280
28 5.119
29 4.899
int ans = 0;
while (ans == 0)
{
for (int i=0; i<3; i++)
{
while ((r = rand5()) == 3){};
ans += (r < 3) >> i
}
}
这个表达式足以得到1 - 7之间的随机整数
int j = ( rand5()*2 + 4 ) % 7 + 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小提琴