4.
以下哪個序列對應數字?00?至?88?的?44?位二進制格雷碼（Gray code）？（ ）
- ?A.?
0000, 0001, 0011, 0010, 0110, 0111, 0101, 1000
?B.?0000, 0001, 0011, 0010, 0110, 0111, 0100, 0101
?C.?0000, 0001, 0011, 0010, 0100, 0101, 0111, 0110
?D.?0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100
正解：D
錯解：A?
原因：首先，格雷碼具有以下性質：
- 相鄰兩個編碼只能有一位不同。
- 首尾兩個編碼視作相鄰，也只能有一位不同。
- 同一編碼不能重復出現。
- A 選項：0111 和 0101 有兩位不同（從右往左數第 2 位和第 3 位），不滿足相鄰兩個編碼只能有一位不同的性質，所以 A 選項錯誤。
- B 選項：0111 和 0100 有兩位不同（從右往左數第 1 位和第 3 位），不滿足相鄰兩個編碼只能有一位不同的性質，所以 B 選項錯誤。
- C 選項：0110 和 0000 有三位不同（從右往左數第 1 位、第 2 位和第 4 位），不滿足首尾兩個編碼只能有一位不同的性質，所以 C 選項錯誤。
- D 選項：該序列中相鄰兩個編碼都只有一位不同，且首尾兩個編碼 0000 和 0100 也只有一位不同，同時沒有重復的編碼，滿足格雷碼的所有性質，所以 D 選項正確。
17-5
如果輸入的?
cost?數組為?={10,15,30,5,5,10,20}，程序的輸出為（）。?A.?25
?B.?30
?C.?35
?D.?40
正解：B
錯解：A?
原因：compute?函數實現了一個DP的邏輯：
dp[i]?表示處理到第?i?個元素時的最小成本（cost?數組）。
狀態轉移方程：dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]?，即第?i?步的最小成本，是?前 1 步最小成本?和?前 2 步最小成本?中的較小值，加上當前元素的成本（cost[i-1]?是因為數組下標從 0 開始 ）。
返回?min(dp[n], dp[n-1])?，即處理完所有元素后，最后一步?和 倒數第二步?的最小成本中的較小值。（打擂臺）
2. 代入數據計算
輸入?cost?數組為?[10, 15, 30, 5, 5, 10, 20]?，n = 7?，然后打一個表逐步計算?dp?數組的值：
i | cost[i-1] | dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1] | dp?數組值 |
|---|---|---|---|
| 1 | 10 | dp[1] = cost[0] = 10 | dp[1] = 10 |
| 2 | 15 | min(dp[1]=10, dp[0]=0) + 15 = 0 + 15 = 15 | dp[2] = 15 |
| 3 | 30 | min(dp[2]=15, dp[1]=10) + 30 = 10 + 30 = 40 | dp[3] = 40 |
| 4 | 5 | min(dp[3]=40, dp[2]=15) + 5 = 15 + 5 = 20 | dp[4] = 20 |
| 5 | 5 | min(dp[4]=20, dp[3]=40) + 5 = 20 + 5 = 25 | dp[5] = 25 |
| 6 | 10 | min(dp[5]=25, dp[4]=20) + 10 = 20 + 10 = 30 | dp[6] = 30 |
| 7 | 20 | min(dp[6]=30, dp[5]=25) + 20 = 25 + 20 = 45 | dp[7] = 45 |
最后返回?min(dp[7], dp[6]) = min(45, 30) = 30?。
所以，程序輸出為?30?。
20-5
- ⑤ 處應填（ ）
A.?0
B.?1
C.?i - 1
D.?i
正解：B
錯解：A?
?原因：
回顧漢諾塔的地柜邏輯
- 把?
n-1?個圓盤從?原柱子（源代碼中src）?借助?目標柱子（源代碼中tgt）?移動到?中間柱子（源代碼中tmp）?。 - 把第?
n?個圓盤從?原柱子（src）?直接移動到?目標柱子（tgt）?。 - 把?
n-1?個圓盤從?中間柱子（tmp）?借助?原柱子（src）?移動到?目標柱子（tgt）?。
代碼邏輯
- 函數?
dfs(int i, char src, char tmp, char tgt)?中：i?表示要處理的圓盤數量（從最上面第 1 個到第?i?個圓盤 ）。src?是 “原柱子”，tmp?是 “中間柱子”，tgt?是 “目標柱子”。
- 終止條件：當?
i == 1?時，直接把這 1 個圓盤從?src?移到?tgt?。 - 遞歸過程：
- 第一步遞歸?
dfs(i - 1, src, tgt, tmp)?：把?i-1?個圓盤從?src?借助?tgt?移到?tmp?（對應 把?n-1?個圓盤從原柱子借助目標柱子移到中間柱子?）。 - 然后執行?
move(src, tgt)?：把第?i?個圓盤從?src?移到?tgt?（對應 把第?n?個圓盤從原柱子移到目標柱子?）。 - 第二步遞歸：需要把?
i-1?個圓盤從?tmp?借助?src?移到?tgt?，即?dfs(i - 1, tmp, src, tgt)?。這一步對應第 5 空，所以第 5 空應填?i - 1?。
- 第一步遞歸?
