問(wèn)題簡(jiǎn)述
給一個(gè)2面的硬幣敢辩，要求設(shè)計(jì)一個(gè)算法來(lái)模擬6面骰子理逊。
Follow Up：如何模擬任意[a, b]的均勻隨機(jī)情況？其中a<b且ab為正整數(shù)捶惜。
思路闡述
首先明白一點(diǎn)田藐，[a,b]的隨機(jī)就等價(jià)于[0,b-a]的隨機(jī)。
2面硬幣只能產(chǎn)生0和1兩種結(jié)果吱七，N次之后可以產(chǎn)生一個(gè)N位的二進(jìn)制數(shù)汽久。例如3次之后可以隨機(jī)出[0,7]的均勻隨機(jī)情況。也就是說(shuō)踊餐，如果b-a=2^N-1景醇，那么拋N次硬幣即可。
那么當(dāng)b-a≠2^N-1呢吝岭？
考慮6面骰子三痰，3次之后可能會(huì)有2個(gè)不符合的結(jié)果，因?yàn)?面骰子對(duì)應(yīng)范圍是[0,5]窜管，也就是說(shuō)6和7這兩個(gè)結(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í)說(shuō)穿了就很簡(jiǎn)單，但如果沒(méi)遇到過(guò)早芭，不一定一下子能想出來(lái)彼城。
