首先我們來一道最簡單的題目作為引子
1、已知有一個隨機函數(shù)rand_0_and_1_with_p()，它能以概率p產生0，以概率1 - p產生1，只使用該函數(shù)，設計一新的隨機函數(shù)，要求以等概率產生1和0。
我們知道，運行rand_0_and_1_with_p()函數(shù)一次，那么P(0) = p, P(1) = 1 - p。那么如果運行兩次的話，P(0 and 1) = p(1 - p),P(1 and 0) = p(1 - p)，這樣就出現(xiàn)了等概率，所以我們可以如下實現(xiàn)：


注意到，因為題目只是說等概率生成1和0，并沒有要求P(1) = 0.5, P(0) = 0.5，所以上述實現(xiàn)是合理的，并且保證了性能，不過實用性不大。那么如果要求該隨機函數(shù)只能產生0和1，并且等概率呢？其實只要在上述實現(xiàn)中加個循環(huán)即可：


ok，現(xiàn)在又有新的要求了。
2、已知有一個隨機函數(shù)rand_0_and_1_with_p()，它能以概率p產生0，以概率1 - p產生1，只使用該函數(shù)，設計一新的隨機函數(shù)，要求以等概率1/n產生1到n之間的隨機數(shù)。
其實這個問題可以這么想，我們先用rand_0_and_1_with_p()來實現(xiàn)一個以等概率0.5產生1和0的新函數(shù)，見上rand_0_and_1_with_equal_prob()。有了這個函數(shù)，我們不妨考慮數(shù)字i的二進制，它只有0和1組成，那么我們每次生成一個0或者1，生成log₂n次就可以以等概率生成數(shù)字i了。代碼如下：


這里有個細節(jié)需要注意，就是運行l(wèi)og2n次rand_0_and_1_with_equal_prob()函數(shù)，最終產生的數(shù)可能比n大，因為有可能是如下這種情況：n = 101b，而最后產生的數(shù)字是111b，則應該舍棄這種情況，如代碼中所示。
3、給定函數(shù)rand5()，它能等概率隨機產生1~5之間的數(shù)字，要求據此實現(xiàn)rand7()，使得能等概率產生1~7之間的數(shù)字。
這個題目個人感覺非常棒，可以從題2中獲得一定的靈感，題2中是將n表示成2進制，那是因為已知的隨機函數(shù)是產生0和1的，對于該題，一直的隨機函數(shù)是隨機產生1~5的，我們可以很容易的將該函數(shù)轉化成隨機產生0~4，然后再將7表示成5進制的數(shù)，則1=01₅, 2=02₅, 3=03₅, 4=04₅, 5=10₅, 6=11₅, 7=12₅。不過這里我們同樣是生成所有兩位的五進制數(shù)，那么最高是44₅，即24，然后去掉21,22,23,24剩下的21個數(shù)0~20模7正好可以等概率生成0~6，然后加1即可。代碼如下：


注意上面的代碼第3行不能直接寫成int k = 5 * (rand5() - 1)。
4、假設已知randn()可以等概率的產生0~n-1的值，現(xiàn)在要求設計一個randm要求等概率產生0~m-1的值。
該題可看成是rand5和rand7的擴展，同樣的思路：
如果n >= m，則直接取randn()結果的0~m-1即可；
如果n < m，則可以先判斷m可以表示成多少位的n進制數(shù)，然后再采用類似上面的算法；
代碼如下：


可以寫簡單的程序驗證一下結果即可。

5、如何產生如下概率的隨機數(shù)？0出1次，1出現(xiàn)2次，2出現(xiàn)3次，n-1出現(xiàn)n次？
我們注意到有如下規(guī)律：n - 1 = (n - 1) + 0 = (n - 2) + 1 = (n - 3) + 2 = ... = 2 + (n - 3) = 1 + (n - 2) = 0 + (n - 1)
可以發(fā)現(xiàn)，滿足a + b = n - i的(a, b)數(shù)對的個數(shù)為n - i + 1個。所以我們得到如下代碼：