題目：
已知一個(gè)函數(shù)rand7()能夠生成1-7的隨機(jī)數(shù)，請(qǐng)給出一個(gè)函數(shù)，該函數(shù)能夠生成1-10的隨機(jī)數(shù)。
思路：
假如已知一個(gè)函數(shù)能夠生成1-49的隨機(jī)數(shù)，那么如何以此生成1-10的隨機(jī)數(shù)呢？
解法：
該解法基于一種叫做拒絕采樣的方法。主要思想是只要產(chǎn)生一個(gè)目標(biāo)范圍內(nèi)的隨機(jī)數(shù)，則直接返回。如果產(chǎn)生的隨機(jī)數(shù)不在目標(biāo)范圍內(nèi)，則丟棄該值，重新取樣。由于目標(biāo)范圍內(nèi)的數(shù)字被選中的概率相等，這樣一個(gè)均勻的分布生成了。
顯然rand7至少需要執(zhí)行2次，否則產(chǎn)生不了1-10的數(shù)字。通過運(yùn)行rand7兩次，可以生成1-49的整數(shù)，
1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 2 8 9 10 1 2 3 4 3 5 6 7 8 9 10 1 4 2 3 4 5 6 7 8 5 9 10 1 2 3 4 5 6 6 7 8 9 10 * * 7 * * * * * * *
由于49不是10的倍數(shù)，所以我們需要丟棄一些值，我們想要的數(shù)字范圍為1-40，不在此范圍則丟棄并重新取樣。代碼：
- int rand10() {
- int row, col, idx;
- do {
- row = rand7();
- col = rand7();
- idx = col + (row-1)*7;
- } while (idx > 40);
- return 1 + (idx-1)%10;
- }
E(# calls to rand7) = 2 * (40/49) + 4 * (9/49) * (40/49) + 6 * (9/49)2 * (40/49) + ... ∞ = ∑ 2k * (9/49)k-1 * (40/49) k=1 = (80/49) / (1 - 9/49)2 = 2.45
優(yōu)化：上面的方法大概需要2.45次調(diào)用rand7函數(shù)才能得到1個(gè)1-10范圍的數(shù)，下面可以進(jìn)行再度優(yōu)化。
對(duì)于大于40的數(shù)，我們不必馬上丟棄，可以對(duì)41-49的數(shù)減去40可得到1-9的隨機(jī)數(shù)，而rand7可生成1-7的隨機(jī)數(shù)，這樣可以生成1-63的隨機(jī)數(shù)。對(duì)于1-60我們可以直接返回，而61-63則丟棄，這樣需要丟棄的數(shù)只有3個(gè)，相比前面的9個(gè)，效率有所提高。而對(duì)于61-63的數(shù)，減去60后為1-3，rand7產(chǎn)生1-7，這樣可以再度利用產(chǎn)生1-21的數(shù)，對(duì)于1-20我們則直接返回，對(duì)于21則丟棄。這時(shí)，丟棄的數(shù)就只有1個(gè)了，優(yōu)化又進(jìn)一步。當(dāng)然這里面對(duì)rand7的調(diào)用次數(shù)也是增加了的。代碼如下：
- int rand10Imp() {
- int a, b, idx;
- while (true) {
- a = rand7();
- b = rand7();
- idx = b + (a-1)*7;
- if (idx <= 40)
- return 1 + (idx-1)%10;
- a = idx-40;
- b = rand7();
- // get uniform dist from 1 - 63
- idx = b + (a-1)*7;
- if (idx <= 60)
- return 1 + (idx-1)%10;
- a = idx-60;
- b = rand7();
- // get uniform dist from 1-21
- idx = b + (a-1)*7;
- if (idx <= 20)
- return 1 + (idx-1)%10;
- }
- }
E(# calls to rand7) = 2 * (40/49) + 3 * (9/49) * (60/63) + 4 * (9/49) * (3/63) * (20/21) + (9/49) * (3/63) * (1/21) * [ 6 * (40/49) + 7 * (9/49) * (60/63) + 8 * (9/49) * (3/63) * (20/21) ] + ((9/49) * (3/63) * (1/21))2 * [ 10 * (40/49) + 11 * (9/49) * (60/63) + 12 * (9/49) * (3/63) * (20/21) ] + ... = 2.2123
這里期望次數(shù)為2.21，比起未優(yōu)化的2.45次減少了大概10%。