汉诺塔问题的递归解法详解

那我掉的头发算什么

发布于 2026-01-12 18:27:36

2560

问题描述

汉诺塔（Tower of Hanoi）是一个经典的数学难题，由法国数学家爱德华·卢卡斯在1883年发明。问题描述如下：

有三根柱子A、B、C，柱子A上有n个大小不一的盘子，初始时所有盘子按大小顺序叠放在A柱上，最小的在上，最大的在下。要求将所有盘子从A柱移动到C柱，且在移动过程中需要遵守以下规则： 1.一次只能移动一个盘子 2.每次移动时，将最上面的盘子移动到某一根柱子上 3.任何时候都不能将较大的盘子放在较小的盘子上面

递归解法

JAVA解法

import java.util.Scanner;

public class HanoiTower {
    public static void solveHanoi(int n, char from, char goBy, char to) {
        if (n == 1) {
            System.out.println("将盘子" + n + "从" + from + "移动到" + to);
            return;
        }
        solveHanoi(n - 1, from, to, goBy);
        System.out.println("将盘子" + n + "从" + from + "移动到" + to);
        solveHanoi(n - 1, goBy, from, to);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入盘子数量：");
        int n = scan.nextInt();
        char from = 'A';
        char goBy = 'B';
        char to = 'C';
        solveHanoi(n, from, goBy, to);
    }
}

Python解法

def hanoi(n, from_rod, to_rod, aux_rod):
    """
    汉诺塔问题的Python递归解法
    :param n: 盘子数量
    :param from_rod: 起始柱子
    :param to_rod: 目标柱子
    :param aux_rod: 辅助柱子
    """
    if n == 1:
        print(f"将盘子 {n} 从 {from_rod} 移动到 {to_rod}")
        return
    hanoi(n-1, from_rod, aux_rod, to_rod)
    print(f"将盘子 {n} 从 {from_rod} 移动到 {to_rod}")
    hanoi(n-1, aux_rod, to_rod, from_rod)

if __name__ == "__main__":
    n = int(input("请输入盘子数量："))
    hanoi(n, 'A', 'C', 'B')

C语言解法

#include <stdio.h>

void hanoi(int n, char from, char to, char aux) {
    /*
    汉诺塔问题的C语言递归解法
    n: 盘子数量
    from: 起始柱子
    to: 目标柱子
    aux: 辅助柱子
    */
    if (n == 1) {
        printf("将盘子 %d 从 %c 移动到 %c\n", n, from, to);
        return;
    }
    hanoi(n-1, from, aux, to);
    printf("将盘子 %d 从 %c 移动到 %c\n", n, from, to);
    hanoi(n-1, aux, to, from);
}

int main() {
    int n;
    printf("请输入盘子数量：");
    scanf("%d", &n);
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

代码解析（JAVA为例）

方法参数说明

solveHanoi方法接收四个参数：

n：当前要移动的盘子数量

from：起始柱子（移动的起点）

goBy：辅助柱子（中转站）

to：目标柱子（移动的终点）

递归逻辑

基本情况：当只有一个盘子时（n == 1），直接将它从起始柱子移动到目标柱子

递归步骤：

将上面的n-1个盘子从起始柱子移动到辅助柱子（使用目标柱子作为中转）

将最下面的第n个盘子从起始柱子移动到目标柱子

将那n-1个盘子从辅助柱子移动到目标柱子（使用起始柱子作为中转）

示例运行

当输入盘子数量为3时，程序输出：

请输入盘子数量：
3
将盘子1从A移动到C
将盘子2从A移动到B
将盘子1从C移动到B
将盘子3从A移动到C
将盘子1从B移动到A
将盘子2从B移动到C
将盘子1从A移动到C

移动过程可视化

让我们以3个盘子为例，详细展示每一步的移动过程：

初始状态:
A: [3, 2, 1] (底部到顶部)
B: []
C: []

步骤1: 将盘子1从A移动到C
A: [3, 2]
B: []
C: [1]

步骤2: 将盘子2从A移动到B
A: [3]
B: [2]
C: [1]

步骤3: 将盘子1从C移动到B
A: [3]
B: [2, 1]
C: []

步骤4: 将盘子3从A移动到C
A: []
B: [2, 1]
C: [3]

步骤5: 将盘子1从B移动到A
A: [1]
B: [2]
C: [3]

步骤6: 将盘子2从B移动到C
A: [1]
B: []
C: [3, 2]

步骤7: 将盘子1从A移动到C
A: []
B: []
C: [3, 2, 1]