给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
亚当·罗森菲尔德正确答案的前提是:
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没有可能的一次性值,我还没有找到它。
其他回答
这里是我的一般实现,在给定一个范围为[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
首先,我在1点上移动ramdom5() 6次,得到7个随机数。 其次,将7个数相加得到公和。 第三,除法的余数是7。 最后加1,得到从1到7的结果。 这个方法给出了在1到7的范围内获得数字的相等概率,除了1。1的概率略高。
public int random7(){
Random random = new Random();
//function (1 + random.nextInt(5)) is given
int random1_5 = 1 + random.nextInt(5); // 1,2,3,4,5
int random2_6 = 2 + random.nextInt(5); // 2,3,4,5,6
int random3_7 = 3 + random.nextInt(5); // 3,4,5,6,7
int random4_8 = 4 + random.nextInt(5); // 4,5,6,7,8
int random5_9 = 5 + random.nextInt(5); // 5,6,7,8,9
int random6_10 = 6 + random.nextInt(5); //6,7,8,9,10
int random7_11 = 7 + random.nextInt(5); //7,8,9,10,11
//sumOfRandoms is between 28 and 56
int sumOfRandoms = random1_5 + random2_6 + random3_7 +
random4_8 + random5_9 + random6_10 + random7_11;
//result is number between 0 and 6, and
//equals 0 if sumOfRandoms = 28 or 35 or 42 or 49 or 56 , 5 options
//equals 1 if sumOfRandoms = 29 or 36 or 43 or 50, 4 options
//equals 2 if sumOfRandoms = 30 or 37 or 44 or 51, 4 options
//equals 3 if sumOfRandoms = 31 or 38 or 45 or 52, 4 options
//equals 4 if sumOfRandoms = 32 or 39 or 46 or 53, 4 options
//equals 5 if sumOfRandoms = 33 or 40 or 47 or 54, 4 options
//equals 6 if sumOfRandoms = 34 or 41 or 48 or 55, 4 options
//It means that the probabilities of getting numbers between 0 and 6 are almost equal.
int result = sumOfRandoms % 7;
//we should add 1 to move the interval [0,6] to the interval [1,7]
return 1 + result;
}
我想到了一个解决这个问题的有趣方法,想和大家分享一下。
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:)
这个表达式足以得到1 - 7之间的随机整数
int j = ( rand5()*2 + 4 ) % 7 + 1;
以下是我的发现:
Random5产生1~5的范围,随机分布 如果我们运行3次并将它们加在一起,我们将得到3~15个随机分布的范围 在3~15范围内执行算术 (3~15) - 1 = (2~14) (2~14)/2 = (1~7)
然后我们得到1~7的范围,这是我们正在寻找的Random7。