算法导论9.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

9.1-1

算法GET-2-SMALLEST设计如下。基本思想是，通过类似“淘汰赛”的比较方式找到最小值。在这个阶段中，需要进行\(n-1\)次比较。在一轮淘汰过程中，需要进行\(\left\lfloor\dfrac{n}{2}\right\rfloor\)次的比较，并且记录被自己淘汰的选手。

最终经过\(\lceil\lg n\rceil\)轮的淘汰赛后，最终得出最小的胜者。

最小值必定和次小值进行过比较并且将其淘汰，否则，次小值最终会成为最小值。在最小值比较过的\(\lceil\lg n\rceil\)个数中，需要进行\(\lceil\lg n\rceil-1\)次比较才能找出这\(\lceil\lg n\rceil\)个数中的最小值，这个最小值就是全局的次小值。

因此，最终需要进行\(n-1+\lceil\lg n\rceil - 1=n+\lceil\lg n\rceil-2\)次比较就能找到最小值和次小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
GET-2-SMALLEST(A, n)
  let pre[1 : n], B be new array with 0
  for i = 1 to n
    INSERT(B, i)
    make pre[i] an empty list
  while B.size != 1
    let C be new array
    for i = 1 to B.size by 2
      if A[B[i]] <= A[B[i + 1]]
        INSERT(C, B[i])
        INSERT(pre[B[i]], B[i + 1])
      else        
        INSERT(C, B[i + 1])
        INSERT(pre[B[i + 1]], B[i])
    if B.size % 2 == 1
      INSERT(C, B[B.size])
    B = C
  smallest_1 = B[1]
  smallest_2 = B[smallest_1, 1]
  for i = 2 to pre[smallest_1].size
    if A[pre[smallest_1, i]] < A[smallest_2]
      smallest_2 = pre[smallest_1, i]
  return A[smallest_1], A[smallest_2]

9.1-2

总共需要\(3\)次比较。对数组中的前\(3\)个数直接进行排序，需要进行\(3\)次比较。这\(3\)个数中间的那个值一定不是最小值也不是最大值，因为它前面还有一个比它更小的数，后面还有一个比它更大的数。

9.1-3

总共需要\(7\)场比赛。

首先将这\(25\)匹马分成\(5\)组分别进行小组赛，并且决出组内排名，令\(h_{i,j}(1\le i,j\le 5)\)表示第\(i\)组第\(j\)名的马。

接下来，第\(6\)场比赛是由组内\(5\)个冠军进行展开，也就是\(h_{1,1},h_{2,1},h_{3,1},h_{4,1},h_{5,1}\)。最终假设第\(k\)名的马来自第\(r_k\)组，为\(h_{r_k,1}\)。

那么可以知道，\(h_{r_4,1},h_{r_5,1}\)不可能是前\(3\)好的马，并且\(h_{r_1,1}\)是最好的马。

第\(7\)场比赛由\(h_{r_1,2},h_{r_1,3},h_{r_2,1},h_{r_2,2},h_{r_3,1}\)之间进行，这场比赛前\(2\)好的马就是全局第\(2,3\)好的马。因为次好的马有可能来自\(r_1,r_2\)组。

\(\star\) 9.1-4

假设最大值候选集合为\(S\)，最小值候选集合为\(T\)。在一开始，\(|S|=|T|=n\)。那么当\(|S\cap T|\ge 2\)时，采用\(1\)次比较可以同时在\(S,T\)中分别去掉\(1\)个元素，这种比较最多只能使用\(\left\lfloor\dfrac{n}{2}\right\rfloor\)次。在此之后，两个集合都只剩下\(n-\left\lfloor\dfrac{n}{2}\right\rfloor=\left\lceil\dfrac{n}{2}\right\rceil\)个元素。

那么在每个集合内部，使用\(1\)次比较可以再次去掉集合内的\(1\)个元素，这时需要\(n-\left\lfloor\dfrac{n}{2}\right\rfloor-1\)次的比较。

因此，至少需要\(\left\lfloor\dfrac{n}{2}\right\rfloor+2\left(n-\left\lfloor\dfrac{n}{2}\right\rfloor-1\right)=2n-\left\lfloor\dfrac{n}{2}\right\rfloor-2=\left\lceil\dfrac{3n}{2}\right\rceil-2\)次比较。