腾讯面试高频题。
定理：若rand_n()能等概率生成1到n的随机整数，则有(rand_n() - 1) * n + rand_n()能等概率生成1到n * n的随机整数。
解释：rand()7能等概率生成1~7,
* * * rand7() - 1能等概率生成0~6,
* * * (rand7() - 1) * 7能等概率生成{0, 7, 14, 21, 28, 35, 42},
* * * (rand7() - 1) * 7 + rand7()能等概率生成1~49。

class Solution {
public:
    int rand10() {
        while (true)
        {
            int x = rand7();
            int num = (x - 1) * 7 + rand7();        //rand7()每次调用的值都不同，故不要用变量来存
            if (num <= 40) return num % 10 + 1;     //大于 40 拒绝采样，

            x = num - 40;                           //此时 x = rand9()
            num = (x - 1) * 7 + rand7();            // 8 * 7 + 7 = 63
            if (num <= 60) return num % 10 + 1;     //大于 60 拒绝采样

            x = num - 60;                           //此时 x = rand3()
            num = (x - 1) * 7 + rand7();            // 2 * 7 + 7 = 21
            if (num <= 20) return num % 10 + 1;     //大于 20 拒绝采样
        }   
    }
};

当然到最后一步还可以继续写下去，但是没必要了，最后一步在 21 中能取到 21 的概率太低，不值得为这个概率再去调用一次rand7()做计算了。此时rand7()的调用次数可以说已经达到了极小值点，再继续下去反而会增加rand7()的调用次数。