CSP 2024 入门级第一轮（88.5）

4.

以下哪个序列对应数字 00 至 88 的 44 位二进制格雷码（Gray code）？（ ）

1.  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 

原因：首先，格雷码具有以下性质：

1. 相邻两个编码只能有一位不同。
2. 首尾两个编码视作相邻，也只能有一位不同。
3. 同一编码不能重复出现。

• 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

1. ⑤ 处应填（ ）
   A. 0
   B. 1
   C. i - 1
   D. i

正解：B

错解：A 

 原因：

回顾汉诺塔的地柜逻辑

1. 把 n-1 个圆盘从 原柱子（源代码中src） 借助 目标柱子（源代码中tgt） 移动到 中间柱子（源代码中tmp） 。
2. 把第 n 个圆盘从 原柱子（src） 直接移动到 目标柱子（tgt） 。
3. 把 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 。