問題簡述

給一個2面的硬幣，要求設(shè)計(jì)一個算法來模擬6面骰子。
Follow Up：如何模擬任意[a, b]的均勻隨機(jī)情況？其中a<b且ab為正整數(shù)。

思路闡述

首先明白一點(diǎn)，[a,b]的隨機(jī)就等價于[0,b-a]的隨機(jī)。
2面硬幣只能產(chǎn)生0和1兩種結(jié)果，N次之后可以產(chǎn)生一個N位的二進(jìn)制數(shù)。例如3次之后可以隨機(jī)出[0,7]的均勻隨機(jī)情況。也就是說，如果b-a=2^N-1，那么拋N次硬幣即可。
那么當(dāng)b-a≠2^N-1呢？
考慮6面骰子，3次之后可能會有2個不符合的結(jié)果，因?yàn)?面骰子對應(yīng)范圍是[0,5]，也就是說6和7這兩個結(jié)果是不能用的。因此，采取策略如下：

• 拋3次硬幣，假如結(jié)果在[0,5]內(nèi)，直接使用結(jié)果；
• 假如結(jié)果是6或者7，則再拋3次硬幣，直至產(chǎn)生有效結(jié)果。

推廣至[0, b-a]，也很類似。代碼：

public static int uniformRandom(int lowerBound, int upperBound) {
    int numberOfOutcomes = upperBound - lowerBound + 1, result;
    do {
        result = 0;
        for (int i = 0; (1 << i) < numberOfOutcomes; ++i) {
            // zeroOneRandom() is the provided random number generator.
            result = (result << 1)|zeroOneRandom();
        }
    } while (result >= numberOfOutcomes);
    return result + lowerBound;
}

總結(jié)

其實(shí)說穿了就很簡單，但如果沒遇到過，不一定一下子能想出來。