汉诺塔问题

题目描述

经典汉诺塔：三根杆上，最左边的杆自上而下、由小到大串着 $n$ 个圆盘（编号 $1\sim n$ ），要把所有盘移到目标杆；一次只能移一个盘，且大盘不能压小盘。输入为一个整数 $n$ （小于 20）和三个单字符，依次表示盘子数目、源杆、目标杆、辅助杆；每次移动输出一行 a->3->b，表示把编号为 3 的盘从 a 杆移至 b 杆。样例输入 2 a b c，样例输出：

text

1
2
3a->1->c
a->2->b
c->1->b

思路

递归分治：先把上面 $n-1$ 个盘借助目标杆移到辅助杆，再把最大的 $n$ 号盘直接移到目标杆，最后把 $n-1$ 个盘借助源杆从辅助杆移到目标杆； $n=0$ 时递归结束。注意题面中三个杆子的输入顺序是「源杆、目标杆、辅助杆」，不要按习惯当成「源、辅助、目标」。总步数为 $2^n-1$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 23:27
# update_at: 2026-09-29 23:27

import sys


def hanoi(n: int, src: str, aux: str, dst: str) -> None:
    """把第 1~n 号盘从 src 柱借助 aux 柱移到 dst 柱，按移动顺序输出。"""
    if n == 1:
        sys.stdout.write(f"{src}->{n}->{dst}\n")
        return
    hanoi(n - 1, src, dst, aux)          # 先移走上面的 n-1 个盘
    sys.stdout.write(f"{src}->{n}->{dst}\n")
    hanoi(n - 1, aux, src, dst)          # 再把 n-1 个盘从辅助柱移过来


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    # 输入三根柱子依次：源、目的、辅助
    src, dst, aux = next(data).decode(), next(data).decode(), next(data).decode()
    hanoi(n, src, aux, dst)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:32
 * update_at: 2026-10-05 05:32
 */

#include <cstdio>

typedef long long ll;

ll n;            // 盘子数目
char src, dst, aux; // 三个杆子的编号：src 源杆，dst 目标杆，aux 辅助杆

// 把 1~num 号盘从 from 杆借助 mid 杆移到 to 杆（mid 为辅助杆）
void hanoi(ll num, char from, char mid, char to) {
    if (num == 0) return;      // 没有盘子可移，递归结束
    hanoi(num - 1, from, to, mid);   // 先把上面 num-1 个盘从 from 借助 to 移到 mid
    printf("%c->%lld->%c\n", from, num, to); // 再把最大的 num 号盘直接移到 to
    hanoi(num - 1, mid, from, to);   // 最后把 num-1 个盘从 mid 借助 from 移到 to
}

int main() {
    scanf("%lld %c %c %c", &n, &src, &dst, &aux);
    hanoi(n, src, aux, dst);
    return 0;
}

目录

题目描述

思路

参考代码