极客时间返利平台,你可以在上边通过山月的链接购买课程,并添加我的微信 (shanyue94) 领取返现。

# 如何根据 random5 随机生成 [0, 5],生成一个函数 random7?

更多描述

已知有一个函数 叫做 random5,执行这个函数会随机返回 0-5 之间任意一个数,概率相同。

根据这个 random5,实现一个 random7,要求执行这个函数后随机返回 0-7 之间任意一个数,概率相同。

这是一道群友分享的百度面经中的问题。

Issue

欢迎在 Gtihub Issue 中回答此问题: Issue 711 (opens new window)

https://www.growingwiththeweb.com/2014/03/given-random5-implement-random7.html 看到一题近似的,不过 random5 和 random7 是返回[0, 5]和[0, 7]

Author

回答者: Camliar (opens new window)

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;
    }
  }
}

Author

回答者: 3N26 (opens new window)

function rand5() {
  return (Math.random() * 6) | 0;
}

function rand7() {
  return (rand5() & 1) * 4 + (rand5() & 1) * 2 + (rand5() & 1);
}
Last Updated: 2/23/2022, 11:56:07 AM