算法设计技巧与分析习题参考答案

(n?k)!?ki(n?k)!(n?i)!?k?(k?1)!(n?k?i?1)!???in!/(n?i)!n!(n?k?i?1)!?(k?1)!iC(n?k)!(n?i)!k!??i?n!(n?k?i?1)!(k?1)!Ck?1n?ikn

于是，

n?k?1?i?1iCCk?1n?iknn?1?k?1

可以证明上式的成立。事实上，上式等价于

n?k?1i?1?iCk?1n?in?1k(n?1)n!k?1kk?1?Cn??Cn?C?C?1nn k?1(k?1)k!(n?k)!n?k?1即要证明

?i?1k?1kk?1iCn?C?C?inn成立。思路：右边变换→左边形式

C?C?C?Cknk?1n?1k?1n?1k?1n?1?C?C?C?C?Ckn?1k?1n?2k?1n?2?C?C?C?Ckn?2k?1n?3?Ckn?3?...

Ck?1n?C?Ckn?1k?1n?1k?1n?1kn?2k?1n?2k?1n?2kn?3k?1n?3k?1n?3?...?C?...?Ckk?1kk?1k?1k，另一方面

?Ck?1k?1?C?C?C?...?C?C，(*) 其中

kkCCCkn?1kn?2???Ck?1n?2?Ck?1n?3?...?Ck?1k?Ck?1k?1

Ck?1n?3?...?CCk?1k?C?Ck?1k?1kk?1k?1kk?1k?1

C?kkCk?1k?1将以上各式(除了*式)相加，即可得到

kk?1k?1k?1k?1k?1Cn?Cn=Cn?2C?3C?...?(n?k?1)C?1n?2n?3k?1?n?k?1i?1n?k?1?i?1k?1iCn?i

iC?即有

k?1n?i?C?Cknk?1n成立。

总结：随机查找

E(ASL)?n，线性查找E(ASL)?n?1kk?1，

n?1nk?nk?1?k?k(k?1)?0，故线性查找更快。

因为14.16 修改14.7节的随机抽样算法，使得它不再需要布尔数组S[1…n]，假设n比m大得多，比如n>m.

解：算法设计如下: 1. k←1

2. while k≤m

3. r←random(1,n) 4. i←k-1

5. while i≥1 and r≠A[i] 6. i←i-1 7. end while 8. if i=0 9. A[k]←r 10. k←k+1 11. end if 12. end while

2