Java用递归方法解决汉诺塔问题详解

时间：2022-10-02 12:52:20|栏目：JAVA代码|点击：次

前言

博主之前有写过关于递归问题的思维模式：

递归的思路

下面将用这种思维模式来求解经典汉诺塔问题。

一、问题描述

汉诺塔（又称河内塔）问题是源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

问应该如何操作？

玩法如下：

1.有三根杆子A,B,C。A杆上有若干碟子

2.每次移动一块碟子,小的只能叠在大的上面

3.把所有碟子从A杆全部移到C杆上

在这里插入图片描述

二、问题分析

（两步直接解决问题）

1.第一步（先思考终止条件）

考虑n=1的情况：

在这里插入图片描述

只需要把这个块从A移到C即可。

在这里插入图片描述

2.第二步（宏观看待整个问题）

当n>=2时，把如图蓝色框框想象成上面的n-1个块（我把它称为一堆块），红色框框表示的是最下面的一块（命名为底块），这样问题可以简化为如图所示的三步。

在这里插入图片描述

第一步：先把上面的一堆块从A（起始柱子）移动到B（目标柱子）上，在这个过程中，C（辅助柱子）起到中转的作用（因为题目要求移动的过程中，小盘子要保证在大盘子上面）

第二步：把最下面的红色大块直接从A（起始柱子）移动到C（目标柱子）。这里注意，这一步的目标柱子和第一步的不一样。

第三步：把上面的一堆块从B（起始柱子）移动到C（目标柱子）上，A（辅助柱子）起到中转的作用。

三、解决方案

那么问题就很简单了，递归的代码就分为两部分：终止条件和递归逻辑。

上一篇博客讲到，我们思考递归问题的时候，可以直接把这个大问题拆解成很多个子问题，想象这个功能别人已经写好了（就是这个递归函数），我们做不到的功能直接调用这个递归函数就可以（注意逻辑）。

public class Recursion {
    public static void main(String[] args) {
        int n = 3;
        hanoiTower(n,'A','B','C');
    }

    /**
     * 传入n个盘子，编号从1..n，我就能按照汉诺塔的规则，从目标盘子A -> C ，B是辅助盘
     * @param nDisks
     * @param A 起始柱子
     * @param B 辅助柱子
     * @param C 目标柱子
     */
    public static void hanoiTower(int nDisks,char A,char B,char C) {
        // 边界
        if (nDisks == 1) {
            // 直接一步到位，用不到B，A上的这一个盘子从A -> C
            move(nDisks,A,C);
            return;
        }
        // n >= 2，核心步骤1,先把顶上的 n -1个小盘子从A -> B,C作为辅助
        hanoiTower(nDisks - 1,A,C,B);
        // 核心步骤2.此时A上就剩下第n个盘子，一步到位将最大的这个盘子一次移动到C
        move(nDisks,A,C);
        // 核心步骤3.此时再把B上的这n-1个盘子从B -> C,A作为辅助
        hanoiTower(nDisks - 1,B,A,C);
    }

    /**
     * 将编号为n的盘子从sourceTower移动到destTower
     * @param nDisks
     * @param sourceTower
     * @param destTower
     */
    public static void move(int nDisks, char sourceTower, char destTower) {
        System.out.println("编号为"+nDisks+"的盘子正在从"+sourceTower+"->"+destTower);
    }