轉自http://www.code123.cc/959.html
先給出一個例子，後面會有擴充
題目
給你一個能生成1到5随機數的函數，用它寫一個函數生成1到7的随機數。 (即：使用函數rand5()來實作函數rand7())。
解答
rand5可以随機生成1,2,3,4,5；rand7可以随機生成1,2,3,4,5,6,7。 rand5并不能直接産生6，7，是以直接用rand5去實作函數rand7似乎不太好入手。 如果反過來呢？給你rand7，讓你實作rand5，這個好實作嗎？
一個非常直覺的想法就是不斷地調用rand7，直到它産生1到5之間的數，然後傳回。 代碼如下：
| 1 2 3 4 5 6 | int Rand5(){ int x = ~(1<<31); // max int while(x > 5) x = Rand7(); return x; } |
等等，這個函數可以等機率地産生1到5的數嗎？首先，它确确實實隻會傳回1到5這幾個數， 其次，對于這些數，都是由Rand7等機率産生的(1/7)，沒有對任何一個數有偏袒， 直覺告訴我們，Rand5就是等機率地産生1到5的。事實呢？讓我們來計算一下， 産生1到5中的數的機率是不是1/5就OK了。比如說，讓我們來計算一下Rand5生成1 的機率是多少。上面的函數中有個while循環，隻要沒生成1到5間的數就會一直執行下去。 是以，我們要的1可能是第一次調用Rand7時産生，也可能是第二次，第三次，…第n次。 第1次就生成1，機率是1/7；第2次生成1，說明第1次沒生成1到5間的數而生成了6，7， 是以機率是(2/7)*(1/7)，依次類推。生成1的機率計算如下：
| 1 2 3 4 5 6 | P(x=1)=1/7 + (2/7) * 1/7 + (2/7)^2 * 1/7 + (2/7)^3 * 1/7 + ... =1/7 * (1 + 2/7 + (2/7)^2 + ...) // 等比數列 =1/7 * 1 / (1 - 2/7) =1/7 * 7/5 =1/5 |
上述計算說明Rand5是等機率地生成1,2,3,4,5的(1/5的機率)。從上面的分析中， 我們可以得到一個一般的結論，如果a > b，那麼一定可以用Randa去實作Randb。其中， Randa表示等機率生成1到a的函數，Randb表示等機率生成1到b的函數。代碼如下：
| 1 2 3 4 5 6 7 | // a > b int Randb(){ int x = ~(1<<31); // max int while(x > b) x = Randa(); return x; } |
回到正題，現在題目要求我們要用Rand5來實作Rand7，隻要我們将Rand5 映射到一個能産生更大随機數的Randa，其中a > 7，就可以套用上面的模闆了。 這裡要注意一點的是，你映射後的Randa一定是要滿足等機率生成1到a的。比如，
| 1 2 | Rand5() + Rand5() - 1 |
上述代碼可以生成1到9的數，但它們是等機率生成的嗎？不是。生成1隻有一種組合： 兩個Rand5()都生成1時：(1, 1)；而生成2有兩種：(1, 2)和(2, 1)；生成6更多。 它們的生成是不等機率的。那要怎樣找到一個等機率生成數的組合呢？
我們先給出一個組合，再來進行分析。組合如下：
| 1 2 | 5 * (Rand5() - 1) + Rand5() |
Rand5産生1到5的數，減1就産生0到4的數，乘以5後可以産生的數是：0,5,10,15,20。 再加上第二個Rand5()産生的1,2,3,4,5。我們可以得到1到25， 而且每個數都隻由一種組合得到，即上述代碼可以等機率地生成1到25。OK， 到這基本上也就解決了。
套用上面的模闆，我們可以得到如下代碼：
| 1 2 3 4 5 6 | int Rand7(){ int x = ~(1<<31); // max int while(x > 7) x = 5 * (Rand5() - 1) + Rand5() // Rand25 return x; } |
上面的代碼有什麼問題呢？可能while循環要進行很多次才能傳回。 因為Rand25會産生1到25的數，而隻有1到7時才跳出while循環， 生成大部分的數都舍棄掉了。這樣的實作明顯不好。我們應該讓舍棄的數盡量少， 于是我們可以修改while中的判斷條件，讓x與最接近25且小于25的7的倍數相比。 于是判斷條件可改為x > 21，于是x的取值就是1到21。 我們再通過取模運算把它映射到1-7即可。代碼如下：
| 1 2 3 4 5 6 | int Rand7(){ int x = ~(1<<31); // max int while(x > 21) x = 5 * (Rand5() - 1) + Rand5() // Rand25 return x%7 + 1; } |
這個實作就比上面的實作要好，并且可以保證等機率生成1到7的數。
讓我們把這個問題泛化一下，從特殊到一般。現在我給你兩個生成随機數的函數Randa， Randb。Randa和Randb分别産生1到a的随機數和1到b的随機數，a，b不相等 (相等就沒必要做轉換了)。現在讓你用Randa實作Randb。
通過上文分析，我們可以得到步驟如下：
- 如果a > b，進入步驟2；否則構造Randa2 = a * (Randa - 1) + Randa， 表示生成1到a2 随機數的函數。如果a2 仍小于b，繼教構造 Randa3 = a * (Randa2 - 1) + Randa…直到ak > b，這時我們得到Randak , 我們記為RandA。
- 步驟1中我們得到了RandA(可能是Randa或Randak )，其中A > b， 我們用下述代碼構造Randb： 從上面一系列的分析可以發現，如果給你兩個生成随機數的函數Randa和Randb， 你可以通過以下方式輕松構造Randab，生成1到a*b的随機數。
1
2
3
4
5
6
7
// A > b
int Randb(){
int x = ~(1<<31); // max int
while(x > b*(A/b)) // b*(A/b)表示最接近A且小于A的b的倍數
x = RandA();
return x%b + 1;
}
如果再一般化一下，我們還可以把問題變成：給你一個随機生成a到b的函數， 用它去實作一個随機生成c到d的函數。有興趣的同學可以思考一下，這裡不再讨論。1
2
3
Randab = b * (Randa - 1) + Randb
Randab = a * (Randb - 1) + Randa