算法导论9.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 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{r5,1}$不可能是前$3$好的马，并且$h{r_1,1}$是最好的马。

第$7$场比赛由$h{r_1,2},h{r1,3},h{r2,1},h{r2,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$次比较。