调用RANDOM(0,1),实现RANDOM(a,b)的过程
算法导论上的5.1-2习题。
*5.1-2 描述RANDOM( a, b )过程的一种实现,它只调用RANDOM( 0, 1 )。作为a和b的函数,你的程序的期望运行时间是多少?
网上给的答案是用二进制上的每一位调用random(0,1)方法很巧妙
在在没看答案之前 自己想了个方法:
random(a,b)
{
temp = a;
while(i=0;i<=b-a;i++)
{
temp += random(0,1);
}
return temp;
}
我的个人感觉这个temp的概率也是1/(b-a+1); 大家的意见呢? 没找到数学方法证明对错
[解决办法]
这个解法的效果是二项分布吧