当前位置：首页 > article >正文

汉诺塔问题详解：递归与分治的经典案例

article 2025/3/6 2:00:08

嘿，小伙伴们！今天我可算撞见了个超有意思的东西，就是那大名鼎鼎的汉诺塔问题！我这好奇心一下子就被勾起来了，迫不及待地想深挖一下，然后把那些好玩的、烧脑的、让人拍案叫绝的解题思路和奇妙故事都分享给大家，咱们一起在这汉诺塔的“迷宫”里找找乐子，看看能不能把这看似不可能的任务变得超简单！快来一起探索吧！

一、问题的由来

汉诺塔（Tower of Hanoi）问题最早出现于1883年，由法国数学家爱德华·卢卡斯发明。这个问题有一个有趣的传说：

在古印度有一座神庙，庙内有三根金刚石柱子，神庙建成时印度教祭司就在其中一根柱子上放置了64个由大到小的金盘。祭司们依照一个古老的预言，日夜不停地将这些盘子按照规则从一根柱子移到另一根柱子。预言说，当他们完成这个工作时，世界就会结束。

二、问题描述

2.1 基本设置

有三根柱子，分别称为 A、B、C

A 柱子上有 n 个盘子，从下到上按照大小顺序摆放

目标是将所有盘子从 A 移动到 C

2.2 移动规则

每次只能移动一个盘子

每次只能移动柱子最顶端的盘子

任何时候大盘子不能放在小盘子上面

三、解题思路

3.1 从简单情况开始思考

让我们从最简单的情况开始分析：

当 n = 1 时：

直接将盘子从 A 移动到 C

只需 1 步

当 n = 2 时：

将小盘子从 A 移动到 B

将大盘子从 A 移动到 C

将小盘子从 B 移动到 C

需要 3 步

3.2 发现规律

当 n = 3 时，我们可以将问题分解为：

将上面2个盘子（看作整体）移动到 B

将最大的盘子移动到 C

将B柱上的2个盘子移动到 C

3.3 递归思想的应用

这就是典型的递归思想：

将 n 个盘子的问题 → 转化为 n-1 个盘子的问题

当 n = 1 时得到最简单的解

四、代码实现

public class Hanoi {

    public static void move(int n, char from, char temp, char to) {

        if (n == 1) {

            System.out.println("将盘子 1 从 " + from + " 移动到 " + to);

            return;

        }

        

        // 将n-1个盘子从源柱子移动到辅助柱子

        move(n - 1, from, to, temp);

        

        // 将第n个盘子从源柱子移动到目标柱子

        System.out.println("将盘子 " + n + " 从 " + from + " 移动到 " + to);

        

        // 将n-1个盘子从辅助柱子移动到目标柱子

        move(n - 1, temp, from, to);

    }

    public static void main(String[] args) {

        int n = 3; // 设置盘子数量

        move(n, 'A', 'B', 'C');

    }

}