Leetcode 470 Implement Rand10() Using Rand7()

发表于 | 分类于

https://leetcode.com/problems/implement-rand10-using-rand7/

随机数的产生关键是等概率，这里有一个概念是拒绝采样，例如rand7()，等概率产生1～7的随机数，如果想要等概率得到1～5的数字，
就不断rand7()，如果产生6,7就拒绝，如果是1～5范围内就接受。这样产生的数字在1到5范围内也是等概率的。

一些例子：

1
2
3
rand4()： (rand2() - 1) × 2 + rand2()
rand2(): rand4() % 2 + 1
         rand6() % 2 + 1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int val5, val6;
        while((val6 = rand7()) > 6);
        while((val5 = rand7()) > 5);
        return (val6 % 2) * 5 + val5;
    }
};

0%