Question 40

③ 的第一次递归参数

在汉诺塔程序中,③ 处应填什么?

完善程序3难度 中等

正确答案

B. src, tgt, tmp

一句话考点

第一次递归是把前 `i - 1` 个盘子从源柱移到临时柱,此时原目标柱变成辅助柱。

经典递归题递归参数

Shared Context

完善程序(2)汉诺塔

汉诺塔是递归入门的经典模型,空位考查递归终止条件和三个柱子的角色转换。

基础模型

`dfs(i, src, tmp, tgt)` 的含义是:把 i 个盘子从 src 移到 tgt,tmp 作为辅助柱。

终止条件

当只剩 1 个盘子时,直接从源柱挪到目标柱,不再继续拆分。

参数变换

第一次递归的目标是把前 i - 1 个盘子移到临时柱,第二次递归才是把它们移到最终目标柱。

cpp

共享程序片段
#include <iostream>
#include <vector>
using namespace std;

void move(char src, char tgt) {
  cout << "从柱子" << src << "挪到柱子" << tgt << endl;
}

void dfs(int i, char src, char tmp, char tgt) {
  if (i == ①) {
    move(②);
    return;
  }
  dfs(i - 1, ③);
  move(src, tgt);
  dfs(⑤, ④);
}

int main() {
  int n;
  cin >> n;
  dfs(n, 'A', 'B', 'C');
}

题组阅读提醒

把 n 个盘子从 A 移到 C,需要先把前 n - 1 个从 A 借助 C 移到 B,再把最大的盘子从 A 移到 C,最后把前 n - 1 个从 B 借助 A 移到 C。

三根柱子在两次递归中的身份不同,很多同学会把临时柱和目标柱的位置写反,这正是本组题的主要陷阱。

本题属于第 完善程序 分区,题组覆盖题号: 38、39、40、41、42

Prompt

题目与选项

在汉诺塔程序中,③ 处应填什么?

A. src, tmp, tgt

B. src, tgt, tmp

C. tgt, tmp, src

D. tgt, src, tmp

Quick Check

做题抓手

先判断题型

先确定这行代码在整体算法中的职责,再看四个选项谁能完成这个职责。

再核对边界

第一轮很爱在闭区间、下标偏移、递归终止条件和布尔返回值上设陷阱。

最后看输出层次

尤其是阅读程序题,要分清函数返回值、变量值和最终打印值是不是同一件事。

Explanation

详细讲解

  1. Step 1

    在把最大的盘子挪到目标柱之前,必须先把上面的 `i - 1` 个小盘子转移到临时柱上。

  2. Step 2

    这一步的任务是:从 `src` 出发,借助原来的 `tgt`,把盘子移到 `tmp`,所以参数顺序应为 `src, tgt, tmp`。

  3. Step 3

    因此 ③ 选 B。

Pitfalls

易错点

  • 记住了要先移到临时柱,但没有同步调整“辅助柱”的角色。
  • 把三个参数当成固定顺序抄模板,没有按当前任务重新解释。

Extend

拓展补充

  • 递归参数最稳的写法,是先用自然语言把子任务说清楚,再映射到 `dfs(盘数, 源, 辅助, 目标)`。

返回总览

回到整套试卷

返回题目总览页,继续从目录、知识图谱或其他分区进入。

所属分区

返回 完善程序

回到首页对应分区,继续顺序刷题或查看同类知识点。

上一题

第 39 题

② 的移动参数

下一题

第 41 题

④ 的第二次递归参数