《算法导论》第五章

#《算法导论》第五章| 来源: 网络整理| 查看: 265

算法导论（第三版）参考答案：练习5.1-1，练习5.1-2，练习5.1-3

Exercise 5.1-1

Show that the assumption that we are always able to determine which candidate is best, in line 4 of procedure HIRE-ASSISTANT, implies that we know a total order of the ranks of the candidates.

如果一个偏序关系同时又是一个全关系，则称为全序或线性序。一个偏序关系，要求满足自反性、反对称性和传递性。

假设这里的关系为 “是否好或更好于”，

自反性：每个应聘者都比自己好或更好。满足反对称性：如果应聘者A好或更好于应聘者B，同时应聘者B又好或更好于应聘者A，则可知A和B一样好。满足传递性：如果应聘者A好或更好于应聘者B，应聘者B又好或更好于应聘者C，则A好或更好于C。满足

所以该关系是一个偏序。又因为所有的应聘者出现的情况的关系，我们都可以判断，所以该关系又是一个全关系。因此，该关系是一个全序。

Exercise 5.1-2

⋆ Describe an implementation of the procedure RANDOM(a,b) that only makes calls to RANDOM(0,1). What is the expected running time of your procedure as a function of a and b ?

RANDOM(a,b) 要求等概率出现，其中有 (a,a+1,...,b) 共 b−a+1 个数。利用二进制编码来表示这些数。

Pseudocode

RANDOM(a,b) n = [lg(b-a+1)] //向上取整 x = 0 // line 2 for i = 0 to n-1 x += pow(2, i)*RANDOW(0, 1) if x > b-a+1 back to line 2 return a+x

for循环每次需要跑 n 次RANDOM(0,1)。同时需要经过多少次”back to line 2”后最终return，这其实服从几何分布

【本文地址】

《算法导论》第五章

《算法导论》第五章

今日新闻

推荐新闻