算法导论14.1 Exercises 答案

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

14.1-1

使用数学归纳法证明。

当\(n=0\)时，结论显然成立：\(T(0)=2^0=1\)。

当\(n>0\)时，假设结论对\(k=0,1,2,\dots,n-1\)时都成立，那么

\[T(n)=1+\sum_{k=0}^{n-1}=1+\sum_{k=0}^{n-1} 2^k=1+2^n-1=2^n\]

原结论仍然成立。

14.1-2

当\(n=4\)，考虑下表情况：

\(\begin{array}{|l|l|l|l|l|} \hline i&1&2&3&4\\ \hline p_i&1&12&21&24\\ \hline p_i/i&1&6&7&6\\ \hline \end{array}\)

按照这个贪心策略，那么先切掉一根长度为\(3\)的棍子（密度为\(7\)，最大），然后剩下长度为\(1\)的棍子，总价值为\(22\)。而实际上不切除反而更好，直接可以卖出\(24\)。

14.1-3

1
2
3
4
5
6
7
8
9
BOTTOM-UP-CUT-ROD-WITH-COST(p, n, c)
  let r[0 : n] be a new array // will remember solution values in r
  r[0] = 0
  for j = 1 to n // for increasing rod length j
    q = p[j] // 不切除钢条，也是一种策略，
    for i = 1 to j - 1 // 此时钢条必须被切除一次，因此当前切割长度i不能循环到达j。
      q = max {q, p[i] + r[j − i] - c}
    r[j] = q // remember the solution value for length j
  return r[n]

14.1-4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
CUT-ROD(p, n)
  if n == 0
    return 0
  q = −∞
  for i = 1 to ⌊n/2⌋
    q = max {q, p[i] + CUT-ROD(p, n − i)}
    if i + i != n
      q = max {q, p[n - i] + CUT-ROD(p, i)}
    return q

MEMOIZED-CUT-ROD-AUX(p, n, r)
  if r[n] ≥ 0 // already have a solution for length n?
    return r[n]
  if n == 0
    q = 0
  else q = −∞
  for i = 1 to ⌊n/2⌋ // i is the position of the first cut
    q = max {q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n − i, r)}
    if i + i != n
      q = max {q, p[n - i] + MEMOIZED-CUT-ROD-AUX(p, i, r)}
  r[n] = q // remember the solution value for length n
  return q

改成了这种方式后，产生的递归子问题集合仍然和修改前的一样，因此对运行时间没有显著改变。

14.1-5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
MEMOIZED-CUT-ROD-SOLUTION(p, n)
  let r[0 : n] and s[0 : n] be a new array // will remember solution values in r
  for i = 0 to n
    r[i] = −∞
  q = MEMOIZED-CUT-ROD-AUX-SOLUTION(p, n, r, s)
  return q and s

MEMOIZED-CUT-ROD-AUX-SOLUTION(p, n, r, s)
  if r[n] ≥ 0 // already have a solution for length n?
    return r[n]
  if n == 0
    q = 0
  else q = −∞
  for i = 1 to n // i is the position of the first cut
    t = p[i] + MEMOIZED-CUT-ROD-AUX-SOLUTION(p, n − i, r, s)
    if t > q
      q = t
      s[n] = i
  r[n] = q // remember the solution value for length n
  return q

PRINT-MEMOIZED-CUT-ROD-SOLUTION(p, n)
  (q, s) = MEMOIZED-CUT-ROD-SOLUTION(p, n)
  while n > 0
    print s[n] // cut location for length n
    n = n − s[n]

14.1-6

1
2
3
4
5
6
FIB(n)
  let fib[0 : n] be a new array
  fib[0] = fib[1] = 1
  for i = 2 to n
    fib[i] = fib[i - 1] + fib[i - 2]
  return fib[n]

以\(n=7\)为例，可以画出如下子问题图：

可以发现，这个图中一共有\(n+1\)个节点，分别为\(v_0,v_1,v_2,\dots,v_{n-1},v_n\)。

其中，对于\(\forall k\ge 2\)，\(v_k\)都有两条出边，因此整个图一共有\(2(n-1)\)条边。