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。
- 第一步递归