470. Implement Rand10() Using Rand7()

解題思路

方法：拒絕采樣
已知Rand7()生成[1，7]的隨機(jī)數(shù)的概率為1/7，如果取到7，我們拒絕再重新進(jìn)行采樣，即我們放棄取到7的所有結(jié)果，這種情況下，我們就得到了Rand6()。
同理，我們拒絕取到6，7的采樣，則得到Rand5()。

• 在Rand6()中，有1/2為奇數(shù)，1/2為偶數(shù)，則以此概率為基準(zhǔn)，取first=0或5。
• 而Rand5()則取到[1,5]概率為1/5，取second=Rand5()。
• Rand10()=first+second。

代碼（c++）

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:

    int rand6() {
        int r;
        while(1){
            r = rand7();
            if(r <= 6) return r;
        }
    }

    int rand5() {
        int r;
        while(1){
            r = rand7();
            if(r <= 5) return r;
        }
    }

    int rand10() {
        int r1 = rand6(), r2 = rand5();
        if(r1 & 1) return r2;
        else return r2+5;
    }
};