算法导论习题 5.1 -2

描述random(a, b)过程的一种实现，它只调用random(0,1)。作为a和b的函数，

你的程序期望运行时间是多少？

?

算法描述
这个题目相当于在能随机生成0,1的前提下，要求生成[0, 1, ...,n-1]范围内的一个整数
1 求出最小的 m，使2^m >= n-1
2 通过random(0,1)，产生一个m比特的整数，这样能随机产生[0, 2^m-1]内的整数，

若产生的整数位于[0, n-1]内，则取这个数作为结果。如果这个数在[0,n-1]外，则丢弃它，再次运行算法重新生成一个。

?

算法的正确性
?a) 证明上述算法可以产生 [0, n-1]范围内的随机数
在范围[0,1, ..., n-1, n, ..., 2^m-1]范围内，总共有p = 2^m个数，其中合法的数是[0, 1, ..., n-1]共n个，

非法的数为?[n, ..., 2^m-1]共q = 2^m-n个，则有 n + q = p。

?

?

算法最后会产生一个合法的随机数 X，0 <= X <= n-1， 显然 X 是

[0, n-1] 上的一个均匀分布。 P{X = i } = 1/n，?所以上述方法可以产生随机数

?

算法的复杂度

算法的数学模型是： 重复一系列伯努力实验，每次实验成功的概率是 n/p， 失败的概率是 q/p。

在取得一次成功前一共要进行多少次试验？ ?

设Pi表示产生随机数时运行了i次算法的概率，那么前i-1次产生的都是非法的数，

第i次产生的是合法的数，所以

?

这是典型的几何分布，其期望值等于成功概率的倒数为： ?p/n = 2^m / n