前两天，睡觉前，偶尔翻起算法导论，看到随机函数这一块内容，里面有一个练习题．
5.1-2 描述random(a,b)过程的一种实现，它只调用random(0,1).作为a和b的函数，你的程序的期望运行时间是多少？
注：random(a,b)为产生a,a+1,a+2,...,b的函数发生器，且产生各整数的概率相等，同为1/(b - a + 1)．
看到这个题目时，似曾相识，脑海浮现了利用random(0,1)产生0或1，从而组成二进制数，来完成random(a,b)的实现．但是细想以后，感觉有个问题在脑海中有点不明不白．
运行random(0,1)函数k次，使得2k>=(b-a+1)，将得到[0,2k)的整数区间，如何将[0,2k)映射到[a,b]的整数区间，保证产生各整数的概率相等，同为1/(b-a+1).
1.当存在k使得2k=(b-a+1)时，只需将产生的二进制数与[a,b]整数一一对应，即可满足概率同为1/(b-a+1)的要求．
例如，random(3,6)，k=2. 此时，对应关系可为00~3,01~4,10~5,11~6．产生的概率为1/4.
2.当不存在k使得2k=(b-a+1)时，产生[0,2k)区间整数的概率为1/2k，小于1/(b-a+1)．[0,2k)如何映射到[a,b]整数区间．
思路一：扩大[0,2k)区间，使得2k可以被(b-a+1)整除，这样可以把[0,2k)分成N段时，每一段对应[a,b]里的一个整数．
但这个思路，是不可行的，因为不存在这样的k值．要么2k=(b-a+1)，要么2k>(b-a+1)且不可被(b-a+1)整除．
思路二：参取截断映射，即 [0,2k) 的前部分映射到[a,b]，这样虽然可以达到产生整数的概率相等，但不等于1/(b-a+1)，还有如果产生[0,2k)后部分的值如何处理．
这个思路，是可行的，如果产生后部分的值，就继续调用自身，重新random.从结果输出分析，最终random(a,b)最终输出的只有[a,b]里的整数，而且每个整数的概率相等，因而其产生的概率值是1/(b-a+1).
具体的实现代码如下：
int random(int a,int b) { int m = 1; int len = b - a + 1; int k = 0; //计算最小的正整数k,使2^k >= len while(m < len) { k++; m *= 2; } m = 0; for(int i = 0;i < k;i++) { m += random(0,1) * (1<<i); } if(m + 1 > len) { return random(a,b); } else { return m + a; } }
由于冗余的存在，该方法运行时间最坏的情况是无究，就是无限地递归调用自身．运行时间的下限是O(log(b-a+1)).
由上述的练习题可扩展出更多类似的问题．
利用rand5()产生rand7()．rand5()产生1到5的整数，rand7()产生1到7的整数．
解决思路与上述的练习题是一样的．利用rand5()产生的一个整数空间，然后将其映射到[1,7]的整数空间上，映射时保证概率相等，且等于1/7.
下面介绍几个有意思的实现．
1.利用预置数组 该方法简单，易理解，但是不具扩展性，需要额外存储空间．
1 int rand7() 2 { 3 int vals[5][5] = { 4 {1,2,3,4,5}, 5 {6,7,1,2,3}, 6 {4,5,6,7,1}, 7 {2,3,4,5,6}, 8 {7,0,0,0,0} 9 }; 10 int result = 0; 11 while(result == 0) 12 { 13 int i = rand5(); 14 int j = rand5(); 15 result = vals[i - 1][j - 1]; 16 } 17 return result; 18 }
2.常规实现方法 可扩展，主要分为三步，构造大的整数区间，限制整数区间，最后映射整数区间．
1 int rand7() 2 { 3 int i; 4 do{ 5 i = 5 * (rand5() - 1) + rand5(); //产生[1,25]的整数区间 6 }while(i > 21); //将[1,25]整数区间控制于[1,21] 7 return i%7 + 1; //将[1,21]映射到[1,7] 8 }
3.看似正确的方法 其实错误的方法
1 int rand7() 2 { 3 int i; 4 i = rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5(); 5 return i%7 + 1; 6 }
与方法2的思路一样，构造新的整数区间，但是方法3中构造的整数区间并不是等概率的．
第4代码中，将会产生5^7种可能的计算，但最终这些可能映射到[7,35]的整数区间中，但是[7,35]区间内整数的产生的概率并不相等．
例如，通过累加区间[0,1]三次，可以得到[0,3]的区间，但是[0,3]每个整数的概率并不相等，分别为1/8,3/8,3/8,1/8．
来源：http://www.cnblogs.com/dwdxdy/archive/2012/07/28/2613135.html