首页 > 代码库 > 《算法导论》 调用RANDOM(0,1),实现RANDOM(a,b)的过程
《算法导论》 调用RANDOM(0,1),实现RANDOM(a,b)的过程
描述RANDOM(a,b)的过程的一种实现，它只调用RANDOM(0,1)。作为a和b的函数，你的程序的期望运行时间是多少？（RANDOM(0,1)以等概率输出0或者1，RANDOM(a,b)以等概率输出[a,b]之间的数（整数））
要RANDOM(a,b)等概率输出[a,b]之间的数，只要等概率得到[0,b-a]之间的一个数即可。既然可以通过RANDOM(0,1)得到1或者0，这时候就能等概率把[0,b-a]区间划分成更小的区间，假设当得到1时区间缩小为[(b-a)/2,b-a]，0时为[0,(b-a)/2]。如此递归，最终得到只有一个整数的区间假如为[x,x]，此时a+x就是最终的结果。
上面的思路看似很美好，但是有一个蛮致命问题没考虑到，就是[0,b-a]中b-a+1必须为2^x（2的幂）才能保证等概率。举个栗子，[0,2]中有3个数{0,1,2}这时得到2的概率明显比0跟1的大。这边的解决办法是扩充区间保证区间中的整数个数是2的幂。当得到的整数比b-a大则重新执行..如此
1 // Random.cpp : 定义控制台应用程序的入口点。 2 // 3 4 #include "stdafx.h" 5 #include "windows.h" 6 #include "stdio.h" 7 #include "math.h" 8 #include "time.h" 9 10 /*11 实现RANDOM(0,1)的函数12 */13 14 int eitherRand()15 {16 return rand()%2;17 }18 /*19 执行递归20 */21 long rand(int *arr, int beg, int end)22 {23 if(beg == end)24 {25 return beg;26 }27 else28 {29 return eitherRand()==0?rand(arr,beg,(beg+end)/2):rand(arr,(beg+end)/2+1,end); 30 }31 }32 int main()33 { 34 int a=2;35 int b=7;36 int dif=b-a+1;37 long rs =1;38 int exp = 0; 39 while(rs<dif)40 {41 rs = rs*2;42 exp ++;43 }44 int *arr = (int *)malloc(rs*sizeof(long));45 //随机种子，设置一直就可以了。重复设置会产生相同的值46 srand((unsigned)time(0));47 int rdNum = rand(arr,0,rs-1);48 while(rdNum>dif)49 {50 rdNum = rand(arr,0,rs-1);51 }52 printf("%d",rdNum+a);53 system("pause");54 return 0;55 }
《算法导论》 调用RANDOM(0,1),实现RANDOM(a,b)的过程
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。