一：描述random(a, b)过程的一种实现，它只调用random(0,1)。作为a和b的函数，你的程序期望运行时间是多少？
Random（a，b）需满足的条件：
1）a、b之间的元素是等概率出现的
2）其概率=1/(b-a+1)
以下解题思路仅实现了---等概率出现，至于得到的概率<=1/(b-a+1)
解析：1·Random(0,1)可以等概率产生0、1，如果将(b-a+1)写成二进制形式，则可以用Random(0,1)产生的值（0或1）串起来表示(b-a+1)，执行Random(0,1)
p次后，得到的结果将是Random(0, 2^p)，当2^p >= (b-a+1)时，实际上0~(b-a+1)【准确的说是0~2^p】之间的元素已经可以等概率出现了
2·分治法：
2.1分解,将a-b区间分成2部分,通过random(0,1)控制,则进入前半部和后半部的概率是一样的;
2.2.递归的处理前后两个部分,若问题足够小,即落到某个具体位置上时,则直接返回;
注意：当元素个数(b-a+1)不是2的幂次时，直接进行分治得不到等概率
元素；此时需要添加(b+1)、(b+2)、(b+3)···以使得元素个数等于2的幂次，然后再对a~(b+i)进行分治
- #include <iostream>
- #include <cstdlib>
- #include <time.h>
- using namespace std;
- int random(int a , int b)
-
{
- int p,m=1; //m用来保存2^p
-
for(p=0 ; m<b-a+1; p++) //p是二进制位数
，b - a + 1 至少要p位二进制才能存下。 - {
- m *= 2; //再用m保存十进制的值
- }
- m = rand()%2;
- for(int i=0 ; i<p; i++)
- {
- m = m*2+rand()%2;//将生成的01串表示成十进制，注意每次都要左移，所以m*2
- }
- if(m > b-a)
- {
- return random(a , b);
- }
- else
- {
- return m+a;
- }
- }
- int main()
- {
- int a,b;
- cin >> a >>b;//输入3和7
- srand(time (0) );
- int m;
- int three , four , five ,
- six , seven;//这几个变量用来统计3,4,5,6,7出现次数
- three = four = five =
- six = seven=0;
- for(int i=0 ; i<1000 ; i++)
- {