中–难 · 递归

汉诺塔

这是第一道答案就是调用你自己的题。第一次看会觉得像作弊。并不是 —— 这就是递归的全部。

一句话答案借助 B 把 n 个盘子从 A 移到 C，三次递归调用 —— 先把 n−1 个移到备用柱，再移最后一个，最后把 n−1 个移回来 —— 总共 2ⁿ − 1 步。

题目

输入: 一个整数 n(1 ≤ n ≤ 8)—— 圆盘个数,全部一开始都在柱子 A 上。

输出: 每行一步,格式 X->Y,把整叠盘子从 A 搬到 C,B 作为中转。大盘永远不能压在小盘上。

样例:

输入	输出
`1`	`A->C`
`2`	`A->B A->C B->C`
`3`	`A->C A->B C->B A->C B->A B->C A->C`

n 个盘子恰好需要 2ⁿ − 1 步:1、3、7、15…… 这个数字就是递归的指纹 —— 每一层都是「两倍的工作加一步」。

你的解答

main.cpp — 你的解答

「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 先把小盘子忘掉

要把 n 个盘子从 A 搬到 C,你不需要考虑 n 个盘子。你只需要考虑一个:最大的那个。它最终必须落在 C 上,为此 C 必须是空的、其余 n−1 个盘子必须全在 B 上。这就是解法的全部结构。

提示 2 — 三行,其中一行是打印

把 n−1 个从 from 搬到 aux(to 当备用)。打印 from->to。再把 n−1 个从 aux 搬到 to(from 当备用)。就这样。你从头到尾没直接搬过任何一个盘子 —— 你只描述局面,让递归去干活。

提示 3 — 出口是 n == 0,不是 n == 1

两种都能跑,但 n == 0 更干净:「搬零个盘子」是一个合法、完整、什么都不用做的请求。把 n == 1 当出口,你就得为打印单独开一个分支,三步的循环体也不再统一。把出口选好,等于写好了一半的递归。

题解（先自己试试！）

#include <iostream>
using namespace std;

void hanoi(int n, char from, char aux, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, aux);
    cout << from << "->" << to << endl;
    hanoi(n - 1, aux, from, to);
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

看看这段代码有多短 —— 六行,而这个问题大多数人要在白板上推半天。这就是递归的回报:你只描述一层,机器替你展开成 2ⁿ − 1 步。但代价是真实的:调用栈会涨到 n 层,如果递归不是对半砍而是线性的,输入一大就会爆栈 —— 这就是为什么每个递归都必须有一个真的能到达的出口。最后一题,技巧在算术而不在代码:阶乘末尾零。

深度解析

为什么这样做对

要搬 n 个盘子,只考虑最大的那个:它最终必须落在 C 上,为此 C 必须空、其余 n−1 个必须全在 B 上。于是问题自己变成了两个更小的自己。

代价

恰好 2^n − 1 步 —— 这是递归的指纹:每层都是「两倍的工作加一步」。调用栈深度是 n。

常见错法

出口写成 n == 1 而不是 n == 0:得为打印单独开一个分支,三步的循环体也不再统一。
第二次递归调用从 from 出发而不是 aux:输出会重复甚至无效,而且它根本不报错 —— 只是错了。

下一步

最后一题,技巧在算术而不在代码:阶乘末尾零。

记住这两句

只考虑最大的那个盘子,剩下的交给递归。
出口选 n == 0,三步才统一。

🐞 这段是错的 —— 点开,亲手让它挂一次

第二次递归从 from 出发而不是 aux —— 步骤重复了

#include <iostream>
using namespace std;

void hanoi(int n, char from, char aux, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, aux);
    cout << from << "->" << to << endl;
    hanoi(n - 1, from, aux, to);
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}