给定一个函数,它产生的是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的幂。
其他回答
这里是我的一般实现,在给定一个范围为[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到5rand5()范围内随机整数的函数,编写一个生成1到7rand7()范围内随机整数的函数
在我建议的解决方案中,我只调用rand5一次
真正的解决方案
float rand7()
{
return (rand5() * 7.0) / 5.0 ;
}
这里的分布是缩放的,所以它直接取决于rand5的分布
整数解
int rand7()
{
static int prev = 1;
int cur = rand5();
int r = cur * prev; // 1-25
float f = r / 4.0; // 0.25-6.25
f = f - 0.25; // 0-6
f = f + 1.0; // 1-7
prev = cur;
return (int)f;
}
这里的分布取决于rand7(i) ~ rand5(i) * rand5(i-1)
rand7(0) ~ rand5(0) * 1
function rand7() {
while (true) { //lowest base 5 random number > 7 reduces memory
int num = (rand5()-1)*5 + rand5()-1;
if (num < 21) // improves performance
return 1 + num%7;
}
}
Python代码:
from random import randint
def rand7():
while(True):
num = (randint(1, 5)-1)*5 + randint(1, 5)-1
if num < 21:
return 1 + num%7
100000次运行的测试分布:
>>> rnums = []
>>> for _ in range(100000):
rnums.append(rand7())
>>> {n:rnums.count(n) for n in set(rnums)}
{1: 15648, 2: 15741, 3: 15681, 4: 15847, 5: 15642, 6: 15806, 7: 15635}
为什么不除以5再乘以7,然后四舍五入呢?(当然,你必须使用浮点数no.)
它比其他解决方案更简单、更可靠(真的吗?)例如,在Python中:
def ranndomNo7():
import random
rand5 = random.randint(4) # Produces range: [0, 4]
rand7 = int(rand5 / 5 * 7) # /5, *7, +0.5 and floor()
return rand7
这不是很容易吗?
这是我想到的答案,但这些复杂的答案让我认为这是完全错误的/:))
import random
def rand5():
return float(random.randint(0,5))
def rand7():
random_val = rand5()
return float(random.randint((random_val-random_val),7))
print rand7()