Cracking Coding Interview - 16.23 Rand7 From Rand5

Rand7 from Rand5: Implement a method rand7() given rand5(). That is, given a method that generates a random number between 0 and 4 (inclusive), write a method that generates a random number between 0 and 6 (inclusive).

Hints: #505, #574, #637, #668, #697, #720

解法

rand5()的范围是[0, 4]，先看看那么两个rand5()相加是否能够等价rand10()即[0, 9]。

可以每个结果的概率并不相同，所以不能成立。其实同理，相乘也不能成立。

如果对结果取模，那么分布就变成了：

回发现概率分布还是不均匀。

得想一个办法将各种结果出现的概率弄成一致，如果这样 5 * rand5() + rand5()：

可以发现，结果出现的次数都是一次，也就是概率相同。那么，我们可以抛弃掉[21, 24]这4个结果，在[0, 20]之间 % 7，代码：

1
2
3
4
5
6
7
8

public int rand7() {
  while (true) {
    int num = rand5() * 5 + rand5();
    if (num < 21) {
      return num % 7;
    }
  }
}

为什么这样做概率是均匀的？我们可以把代码做一个转换，因为已知rand5(5) + rand(5)能够得到一个均匀分布的[0, 24]的区间，那么就等价于rand25()，然后我们把 % 7 这个操作去掉，把代码变成这样：

1
2
3
4
5
6
7
8

public int rand21() {
  while (true) {
    int num = rand(25);
    if (num < 21) {
      return num;
    }
  }
}

假设每次调用rand25()的返回结果是0, 1, 2, 3, ..., 24, 0, 1, 2, ..., 24，那么调用rand21()的记录就是：

可以看到rand21()的结果的分布都是均匀的，所以解法提到的方法是可行的。