用random(0,1)来实现random(a,b),并估计运行时间.

假设Random(a,b)以相同概率返回a到b之间的任何一个数字，描述Random(a,b)过程的一种实现，它只调用现有实现Random（0，1）。作为a和b的函数，你的程序的期望运行时间是多少？假设Ramdom（0，1）的运行时间是常数。

想到一种解法,分治法:
     1.分解,将a-b区间分成2部分,通过random(0,1)控制,则进入前半部和后半部的概率是一样的;
     2.递归的处理前后两个部分,若问题足够小,即落到某个具体位置上时,则直接返回;

伪代码:
int random( a, b )
{
   if( a == b )
     return a;
   if( random( 0, 1 ) )
     return random( a, (a+b)/2 );
   else
     return random( (a+b)/2 + 1, b );
}

但仔细分析下发现有问题.

令 n = b-a, 问题简化为 1/n = f( 1/(2^x) ), 
                root
                 / \
                0    1
               / \   / \
             /   .....   \
            0 .........  1
时间复杂度为 O(lgn),通过lgn次random(0,1)调用,即生成长度为lg(b-a)的"前后后前..."随机序列来控制最后落定的位置,类似2叉决策树的决策过程,x次random(0,1)调用最多可能产生2^x条路径,即最多可能返回2^x种结果,每条路径的产生概率相等,即1/(2^x).

但如果n不是2的整数次方,不可能将概率平均分配到每条路径,所以不可能在有限次调用内生成精确的平均返回概率.

如, n=8时,可以取x=3,正好8种返回结果的概率一样,都是1/8.但如果n=7,那么b的返回概率可能会是2/8,其余值的返回概率均为1/8.就不是相同的概率了，要想是等概率则n=2^x。
  

思路1：

这个题目相当于在能随机生成 0, 1 的前提下，要求随机生成 n 个整数。（每个数生成的概率相等）
把要生成的数标记为 0,1,2,..., n-1
取最小的 m，使得 2^m >= n-1（二分法分m次后每等分里面只有一个）
通过随机生成 0,1 的函数生成一个  m 比特整数（随机生成每一位），这样能随机生成 [0, 2^m) 内的整数。
随机生成一个 [0,2^m) 中的整数，如果这个数大小在 [0,n-1] 内，则取这个数为结果。
如果这个数在 [0,n-1] 外，则丢弃它，重新生成一个。

思路2：

k = b-a+1，如果k为偶数，则将S均分成两组，通过一次R(0,1)来淘汰其中一组；如果S为奇数， 则用上述方法来分组，将占多数的一组淘汰。可以证明这个算法后也是正确的。只要在某一轮的测试中R(0,1)的输出为全0或全1，问题的规模就可以缩小一 半。

思路3：

或者用二分的方式，根据Ramdom（0，1）是0还是1进入[a,b]区间的前半部分或者后半部分，这样同样面临如果区间长度不是2的整数次方，会导致每个数生成的概率不一样，应该再做一点处理，扩大生成的范围，像思路1中把不是范围内的数丢掉。

在在没看答案之前 自己想了个方法：
  random（a,b）
{
  temp = a;
  while(i=0;i<=b-a;i++)
  {
  temp += random(0,1);
  }

  return temp;

}

我的个人感觉这个temp的概率也是1/(b-a+1); 大家的意见呢？ 没找到数学方法证明对错

最开始的想到的是一个错误的算法，运行RANDOM(0,1)(b-a+1)次，然后将运行的结果累加，然后加上a得到最后的结果。
我感觉这也是很多人对这个问题的最直观的想法。
假设在运行RANDOM(0，1)(b-a+1)次中每次的结果形成一个序列，那么这个序列的和会重复，并且每一种结果重复的次数还是不一样的，所以导致了该算法的结果不对。
如果控制每一种和的序列只产生一次，那么这样就可以实现等概率分布了。
我的想法是将所有产生的序列控制为下面的形式：
000......001
000......011
000......111
............
............
............
001......111
011......111
111......111
以上是一个(b-a+1)阶的矩阵。
我现在的算法是只产生这个矩阵中每一行这种形式的序列。然后将这一行的结果进行相加。然后加上(a-1)得到最后的结果。
在这个矩阵的序列中有一个规律就是只要序列的某位为1，那么后面的元素都为1。

下面是伪代码（可能不是很规范，要是不明白的地方我马上补充）
Random(a,b)
//A是长度为b-a+1的数组，用来存储生成的序列
//i用来控制循环，也作为数组的标，temp用来存储每次random(0,1)生成的结果，
//test用来检测random(0,1)第一次生成的时候，一旦random(0,1)得到了1，那么以后的random(0,1)就只能得到1这个结果
//得到0的就舍弃并继续循环，直到得到特定形式的序列
A=new array(b-a+1); 
let i=1,temp=0,test=false; 
while(i<=b-a+1)
temp=RANDOM(0,1)
if test == true and temp == 0
continue;
if test== false and temp =1
test = true;
A[i] = temp;
i = i+1；
return a-1+sum(A)

再次感谢。
--------------------------------------------------------------------------------------------------
----------------------------------------------自己的改进方法----------------------------------------------------
谢谢Xi Yang的解答。根据他的回答，我修改了算法的实现过程。
主要是在利用多次循环来粗暴的找到所需的序列，而不是在一次循环中控制每次随机生成的结果
下面是伪代码（可能不是很规范，要是不明白的地方我马上补充）
Random(a,b)
//A是长度为b-a+1的数组，用来存储生成的序列
//i用来控制循环，也作为数组的标，temp用来存储每次random(0,1)生成的结果，
//test用来检测random(0,1)第一次生成的时候，一旦random(0,1)得到了1，那么以后的random(0,1)就只能得到1这个结果，这时将test赋值真
//在后面中如果random(0,1)得到0的就舍弃并重新开始循环，直到得到特定形式的序列
A=new array(b-a+1); ; 
let i=1,temp=0,test=false; 
while(true)
{
i=1
while(i<=b-a+1)
{
temp=RANDOM(0,1)
if test == true and temp == 0
break;
if test== false and temp =1
test = true;
A[i] = temp;
i = i+1
}
}
return a-1+sum(A)

再次感谢。

本文转自农夫山泉别墅博客园博客，原文链接：http://www.cnblogs.com/yaowen/p/4460483.html，如需转载请自行联系原作者