快捷導(dǎo)航

Java用遞歸方法解決漢諾塔問(wèn)題詳解

更新時(shí)間：2022年04月14日 10:39:38 作者：Killing?Vibe

漢諾塔問(wèn)題是一個(gè)經(jīng)典的問(wèn)題。漢諾塔（Hanoi?Tower），又稱(chēng)河內(nèi)塔，源于印度一個(gè)古老傳說(shuō)。本文將用Java遞歸方法求解這一問(wèn)題，感興趣的可以學(xué)習(xí)一下

前言

博主之前有寫(xiě)過(guò)關(guān)于遞歸問(wèn)題的思維模式：

遞歸的思路

下面將用這種思維模式來(lái)求解經(jīng)典漢諾塔問(wèn)題。

一、問(wèn)題描述

漢諾塔（又稱(chēng)河內(nèi)塔）問(wèn)題是源于印度一個(gè)古老傳說(shuō)。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤(pán)。

大梵天命令婆羅門(mén)把圓盤(pán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上。

并且規(guī)定，在小圓盤(pán)上不能放大圓盤(pán)，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤(pán)。

問(wèn)應(yīng)該如何操作？

玩法如下：

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

2.每次移動(dòng)一塊碟子,小的只能疊在大的上面

3.把所有碟子從A桿全部移到C桿上

在這里插入圖片描述

二、問(wèn)題分析

（兩步直接解決問(wèn)題）

1.第一步（先思考終止條件）

考慮n=1的情況：

在這里插入圖片描述

只需要把這個(gè)塊從A移到C即可。

在這里插入圖片描述

2.第二步（宏觀看待整個(gè)問(wèn)題）

當(dāng)n>=2時(shí)，把如圖藍(lán)色框框想象成上面的n-1個(gè)塊（我把它稱(chēng)為一堆塊），紅色框框表示的是最下面的一塊（命名為底塊），這樣問(wèn)題可以簡(jiǎn)化為如圖所示的三步。

在這里插入圖片描述

第一步：先把上面的一堆塊從A（起始柱子）移動(dòng)到B（目標(biāo)柱子）上，在這個(gè)過(guò)程中，C（輔助柱子）起到中轉(zhuǎn)的作用（因?yàn)轭}目要求移動(dòng)的過(guò)程中，小盤(pán)子要保證在大盤(pán)子上面）

第二步：把最下面的紅色大塊直接從A（起始柱子）移動(dòng)到C（目標(biāo)柱子）。這里注意，這一步的目標(biāo)柱子和第一步的不一樣。

第三步：把上面的一堆塊從B（起始柱子）移動(dòng)到C（目標(biāo)柱子）上，A（輔助柱子）起到中轉(zhuǎn)的作用。

三、解決方案

那么問(wèn)題就很簡(jiǎn)單了，遞歸的代碼就分為兩部分：終止條件和遞歸邏輯。

上一篇博客講到，我們思考遞歸問(wèn)題的時(shí)候，可以直接把這個(gè)大問(wèn)題拆解成很多個(gè)子問(wèn)題，想象這個(gè)功能別人已經(jīng)寫(xiě)好了（就是這個(gè)遞歸函數(shù)），我們做不到的功能直接調(diào)用這個(gè)遞歸函數(shù)就可以（注意邏輯）。

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

    /**
     * 傳入n個(gè)盤(pán)子，編號(hào)從1..n，我就能按照漢諾塔的規(guī)則，從目標(biāo)盤(pán)子A -> C ，B是輔助盤(pán)
     * @param nDisks
     * @param A 起始柱子
     * @param B 輔助柱子
     * @param C 目標(biāo)柱子
     */
    public static void hanoiTower(int nDisks,char A,char B,char C) {
        // 邊界
        if (nDisks == 1) {
            // 直接一步到位，用不到B，A上的這一個(gè)盤(pán)子從A -> C
            move(nDisks,A,C);
            return;
        }
        // n >= 2，核心步驟1,先把頂上的 n -1個(gè)小盤(pán)子從A -> B,C作為輔助
        hanoiTower(nDisks - 1,A,C,B);
        // 核心步驟2.此時(shí)A上就剩下第n個(gè)盤(pán)子，一步到位將最大的這個(gè)盤(pán)子一次移動(dòng)到C
        move(nDisks,A,C);
        // 核心步驟3.此時(shí)再把B上的這n-1個(gè)盤(pán)子從B -> C,A作為輔助
        hanoiTower(nDisks - 1,B,A,C);
    }

    /**
     * 將編號(hào)為n的盤(pán)子從sourceTower移動(dòng)到destTower
     * @param nDisks
     * @param sourceTower
     * @param destTower
     */
    public static void move(int nDisks, char sourceTower, char destTower) {
        System.out.println("編號(hào)為"+nDisks+"的盤(pán)子正在從"+sourceTower+"->"+destTower);
    }