Open shfshanyue opened 3 years ago
https://www.growingwiththeweb.com/2014/03/given-random5-implement-random7.html 看到一题近似的,不过random5和random7 是返回[0, 5]和[0, 7]
random5
生成 [0, 5]
每个数的概率是 $ \frac {1}{6} $, 使用两次 random
函数,相乘,找到等概率出现的 8个数就可以,不满足的数据排除掉0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 2 | 3 | 4 | 5 |
2 | 0 | 2 | 4 | 6 | 8 | 10 |
3 | 0 | 3 | 6 | 9 | 12 | 15 |
4 | 0 | 4 | 8 | 12 | 16 | 20 |
5 | 0 | 5 | 10 | 15 | 20 | 25 |
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
P | $\frac{11}{36}$ | $\frac{1}{36}$ | $\frac{2}{36}$ | $\frac{2}{36}$ | $\frac{3}{36}$ | $\frac{2}{36}$ |
6 | 8 | 9 | 10 | 12 | 15 | |
P | $\frac{2}{36}$ | $\frac{2}{36}$ | $\frac{1}{36}$ | $\frac{2}{36}$ | $\frac{2}{36}$ | $\frac{2}{36}$ |
16 | 20 | 25 | ||||
P | $\frac{1}{36}$ | $\frac{2}{36}$ | $\frac{1}{36}$ |
根据上图可知,我们只需要取 [1, 2, 3, 5, 6, 8, 9, 12, 15]
,这几个数,对8取余后可得到:
1 | 2 | 3 | 4 | 5 | 6 | 0 | 1 | 7 |
---|---|---|---|---|---|---|---|---|
$\frac{1}{36}$ | $\frac{2}{36}$ | $\frac{3}{36}$ | $\frac{2}{36}$ | $\frac{2}{36}$ | $\frac{2}{36}$ | $\frac{2}{36}$ | $\frac{1}{36}$ | $\frac{2}{36}$ |
至此,我们可以得到等概率的[0, 7] 之间的数,每个数出现的概率为 $\frac{2}{36}$
故,简单粗暴的方式可用以下方式实现:
def random5(self):
return randint(0, 5)
def random7(self):
picked = [1, 2, 3, 5, 6, 8, 9, 12, 15]
while True:
rd1 = self.random5()
rd2 = self.random5()
if (rd1 * rd2) in picked:
return (rd1 * rd2) % 8
rd1 = self.random5()
rd2 = self.random5()
如果要更进一步优化,减少random5
函数的调用,我们就需要优化,如果随机出现的值不在我们采样的范围中时,怎么去减少对函数 random5
的调用,具体操作可看到官方题解
function rand5 () {
return Math.random() * 6 | 0
}
function rand7 () {
while (true) {
let num = rand5() * 6 + rand5()
if (num < 32) {
return num % 8
}
}
};
function rand5 () {
return Math.random() * 6 | 0
}
function rand7 () {
return (rand5() & 1) * 4 + (rand5() & 1) * 2 + (rand5() & 1);
};
直接进行缩放是不是就行了? [0, 5] 1.4 rand7 = rand5() 1.4
已知有一个函数 叫做
random5
,执行这个函数会随机返回 0-5 之间任意一个数,概率相同。根据这个
random5
,实现一个random7
,要求执行这个函数后随机返回 0-7 之间任意一个数,概率相同。这是一道群友分享的百度面经中的问题。