首先我们来一道最简单的题目作为引子
1、已知有一个随机函数rand_0_and_1_with_p()，它能以概率p产生0，以概率1 - p产生1，只使用该函数，设计一新的随机函数，要求以等概率产生1和0。
我们知道，运行rand_0_and_1_with_p()函数一次，那么P(0) = p, P(1) = 1 - p。那么如果运行两次的话，P(0 and 1) = p(1 - p),P(1 and 0) = p(1 - p)，这样就出现了等概率，所以我们可以如下实现：
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，所以上述实现是合理的，并且保证了性能，不过实用性不大。那么如果要求该随机函数只能产生0和1，并且等概率呢？其实只要在上述实现中加个循环即可：
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，现在又有新的要求了。
2、已知有一个随机函数rand_0_and_1_with_p()，它能以概率p产生0，以概率1 - p产生1，只使用该函数，设计一新的随机函数，要求以等概率1/n产生1到n之间的随机数。
其实这个问题可以这么想，我们先用rand_0_and_1_with_p()来实现一个以等概率0.5产生1和0的新函数，见上rand_0_and_1_with_equal_prob()。有了这个函数，我们不妨考虑数字i的二进制，它只有0和1组成，那么我们每次生成一个0或者1，生成log
2n次就可以以等概率生成数字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 }
这里有个细节需要注意，就是运行log2n次rand_0_and_1_with_equal_prob()函数，最终产生的数可能比n大，因为有可能是如下这种情况：n = 101b，而最后产生的数字是111b，则应该舍弃这种情况，如代码中所示。
3、给定函数rand5()，它能等概率随机产生1~5之间的数字，要求据此实现rand7()，使得能等概率产生1~7之间的数字。
这个题目个人感觉非常棒，可以从题2中获得一定的灵感，题2中是将n表示成2进制，那是因为已知的随机函数是产生0和1的，对于该题，一直的随机函数是随机产生1~5的，我们可以很容易的将该函数转化成随机产生0~4，然后再将7表示成5进制的数，则1=01
5, 2=02
5, 3=03
5, 4=04
5, 5=10
5, 6=11
5, 7=12
5。不过这里我们同样是生成所有两位的五进制数，那么最高是44
5，即24，然后去掉21,22,23,24剩下的21个数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、假设已知randn()可以等概率的产生0~n-1的值，现在要求设计一个randm要求等概率产生0~m-1的值。
该题可看成是rand5和rand7的扩展，同样的思路：
如果n >= m，则直接取randn()结果的0~m-1即可；
如果n < m，则可以先判断m可以表示成多少位的n进制数，然后再采用类似上面的算法；
代码如下：
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 }
可以写简单的程序验证一下结果即可。
5、
如何产生如下概率的随机数？0出1次，1出现2次，2出现3次，n-1出现n次？
我们注意到有如下规律：n - 1 = (n - 1) + 0 = (n - 2) + 1 = (n - 3) + 2 = ... = 2 + (n - 3) = 1 + (n - 2) = 0 + (n - 1)
可以发现，满足a + b = n - i的(a, b)数对的个数为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 阅读(1125)
评论(0) 编辑 收藏 引用 所属分类:
算法基础