Java用遞迴方法解決漢諾塔問題詳解

2022-04-14 13:02:13

前言

博主之前有寫過關於遞迴問題的思維模式：

遞迴的思路

下面將用這種思維模式來求解經典漢諾塔問題。

一、問題描述

漢諾塔（又稱河內塔）問題是源於印度一個古老傳說。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著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);
    }

四、範例

n=3的時候

以上就是用宏觀思維去進行遞迴求解漢諾塔的方法，希望大家多多支援喲(●ˇ∀ˇ●)

到此這篇關於Java用遞迴方法解決漢諾塔問題詳解的文章就介紹到這了,更多相關Java 漢諾塔內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Java用遞迴方法解決漢諾塔問題詳解

目錄

前言

一、問題描述

二、問題分析

三、解決方案

四、範例

熱門文章