首先我們來一道最簡單的題目作為引子
1、已知有一個隨機函數(shù)rand_0_and_1_with_p()，它能以概率p產(chǎn)生0，以概率1 - p產(chǎn)生1，只使用該函數(shù)，設(shè)計一新的隨機函數(shù)，要求以等概率產(chǎn)生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 int rand_0_and_1_with_equal_prob() {
2 int tmp1 = rand_0_and_1_with_p();
3 int tmp2 = rand_0_and_1_with_p();
4 if (tmp1 == 1 && tmp2 == 0) {
5 return 1;
6 } else if (tmp1 == 0 && tmp2 == 1) {
7 return 0;
8 } else {
9 return -1;
10 }
11 }
注意到，因為題目只是說等概率生成1和0，并沒有要求P(1) = 0.5, P(0) = 0.5，所以上述實現(xiàn)是合理的，并且保證了性能，不過實用性不大。那么如果要求該隨機函數(shù)只能產(chǎn)生0和1，并且等概率呢？其實只要在上述實現(xiàn)中加個循環(huán)即可：
1 int rand_0_and_1_with_equal_prob() {
2 while (1) {
3 int tmp1 = rand_0_and_1_with_p();
4 int tmp2 = rand_0_and_1_with_p();
5 if (tmp1 == 1 && tmp2 == 0) {
6 return 1;
7 } else if (tmp1 == 0 && tmp2 == 1) {
8 return 0;
9 }
10 }
11 }
12
ok，現(xiàn)在又有新的要求了。
2、已知有一個隨機函數(shù)rand_0_and_1_with_p()，它能以概率p產(chǎn)生0，以概率1 - p產(chǎn)生1，只使用該函數(shù)，設(shè)計一新的隨機函數(shù)，要求以等概率1/n產(chǎn)生1到n之間的隨機數(shù)。
其實這個問題可以這么想，我們先用rand_0_and_1_with_p()來實現(xiàn)一個以等概率0.5產(chǎn)生1和0的新函數(shù)，見上rand_0_and_1_with_equal_prob()。有了這個函數(shù)，我們不妨考慮數(shù)字i的二進制，它只有0和1組成，那么我們每次生成一個0或者1，生成log
2n次就可以以等概率生成數(shù)字i了。代碼如下：
1 int rand_0_to_n_minus_1_with_equal_prob(int n) {
2 int k = 0;
3 while (n) {
4 k++;
5 n >>= 1;
6 }
7 do {
8 int res = 0;
9 for (int i = 0; i < k; ++i) {
10 res |= rand_0_and_1_with_equal_prob() << i;
11 }
12 } while (res >= n);
13 return res;
14 }
這里有個細節(jié)需要注意，就是運行l(wèi)og2n次rand_0_and_1_with_equal_prob()函數(shù)，最終產(chǎn)生的數(shù)可能比n大，因為有可能是如下這種情況：n = 101b，而最后產(chǎn)生的數(shù)字是111b，則應(yīng)該舍棄這種情況，如代碼中所示。
3、給定函數(shù)rand5()，它能等概率隨機產(chǎn)生1~5之間的數(shù)字，要求據(jù)此實現(xiàn)rand7()，使得能等概率產(chǎn)生1~7之間的數(shù)字。
這個題目個人感覺非常棒，可以從題2中獲得一定的靈感，題2中是將n表示成2進制，那是因為已知的隨機函數(shù)是產(chǎn)生0和1的，對于該題，一直的隨機函數(shù)是隨機產(chǎn)生1~5的，我們可以很容易的將該函數(shù)轉(zhuǎn)化成隨機產(chǎn)生0~4，然后再將7表示成5進制的數(shù)，則1=01
5, 2=02
5, 3=03
5, 4=04
5, 5=10
5, 6=11
5, 7=12
5。不過這里我們同樣是生成所有兩位的五進制數(shù)，那么最高是44
5，即24，然后去掉21,22,23,24剩下的21個數(shù)0~20模7正好可以等概率生成0~6，然后加1即可。代碼如下：
1 int rand7() {
2 do {
3 int k = 5 * (rand5() - 1) + rand5() - 1;
4 } while (k >= 21);
5 return (k % 7) + 1;
6 }
注意上面的代碼第3行不能直接寫成int k = 5 * (rand5() - 1)。
4、假設(shè)已知randn()可以等概率的產(chǎn)生0~n-1的值，現(xiàn)在要求設(shè)計一個randm要求等概率產(chǎn)生0~m-1的值。
該題可看成是rand5和rand7的擴展，同樣的思路：
如果n >= m，則直接取randn()結(jié)果的0~m-1即可；
如果n < m，則可以先判斷m可以表示成多少位的n進制數(shù)，然后再采用類似上面的算法；
代碼如下：
1 int randm(int n, int m) {
2 int res = 0;
3 if (m <= n) {
4 do {
5 res = randn();
6 } while (res >= m);
7 return res;
8 }
9
10 int count = 1;
11 int tmp = n - 1;
12 while (tmp < m) {
13 tmp = tmp * n + n - 1;
14 count++;
15 }
16 int times = (tmp / m) * m;
17
18 do {
19 res = randn();
20 for (int i = 0; i < count; ++i) {
21 res = res * n + randn();
22 }
23 } while (res >= times);
24
25 return res % m;
26 }
可以寫簡單的程序驗證一下結(jié)果即可。
5、
如何產(chǎn)生如下概率的隨機數(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個。所以我們得到如下代碼：
1 int Rand(int n) {
2 while (1) {
3 int tmp1 = rand() % n;
4 int tmp2 = rand() % n;
5 if (tmp1 + tmp2 < n) {
6 return tmp1 + tmp2;
7 }
8 }
9 }
posted on 2012-09-10 14:36
myjfm 閱讀(1175)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)