5分鐘帶你解決智力游戲-----漢諾塔問題

漢諾塔簡介：👇

漢諾塔（Tower of Hanoi），又稱河內塔，是一個源于印度古老傳說的益智游戲，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤， ---摘自《百度百科》

單獨看這樣一段話很難理解，我們用數學模型加以解釋：👇

漢諾塔問題可以簡化為如何把 A 柱上的 64 個盤子按照 同樣的大小順序 并且每次只能動一個盤子，在每次移動的程序中也要保證大小順序的情況下轉移到 C 柱（可以借助A和B柱）

64個盤子對于我們來說數量過大不好計算它是如何完成的，那我們簡化問題👇

假設 1 ： A 柱上就 一個盤子 我們應該如何轉移到 C 柱上呢？

👉 我們可以直接把這個盤子從A轉移到C上就大功告成了！！！

步驟：A->C 一共是一步完成的轉移

假設 2 ： A 柱上就 兩個盤子 我們應該如何轉移到 C 柱上呢？

👉 我們可以把最上面的盤子先轉移到 B 柱上，然后最下面的盤子轉移到 C 柱，最后把 B 柱的盤子轉移到 C 柱就完成了，圖解如下： 👇

我們可以看到轉移的步驟是：A->B A->C B->C 一共是三步完成的

假設 3 ： A 柱上就 三個盤子 我們應該如何轉移到 C 柱上呢？

👉步驟較多我們用圖例來進行解釋：👇

?? 切忌在轉移程序中也要保證大小順序！！！

步驟：A——>C A——>B C——>B A——>C B——>A B——>C A——>C 一共是七步

👉 綜上三種情況我們可以用數學歸納法得出結論：👇

當一個盤子時：需要一步

當兩個盤子時：需要三步

當三個盤子時：需要七步

👉 所以：我們發現盤子的個數和轉移的步數存在關系！！！

盤子個數我們設為 n， 步數為 x

即：x = 2^n - 1

👉 那我們思考一個問題：那 64 個盤子需要多少步：2^64-1步

😱 嗯……………………大概就是這么多步

我們假設一個問題：如果要是人計算的話需要多長時間：如果一個人都是在 1s 內完全正確的擺放

😱 嗯……………………大概就是這么多年

? 如果計算機計算呢？？？

博主的計算機是：2.1GHZ的

😱 嗯……………………大概就是這么多年，不過欣慰的是少了蠻多年的，就200多年😊

??下面我們來看一下實作漢諾塔的代碼：👇

這里我采用Java實作：

public class TestDemo {
    /**
     * 在這里傳入兩個需要移動的坐標
     * @param pos1
     * @param pos2
     */
    public static void move(char pos1, char pos2){
        System.out.print(pos1+"——>"+pos2+" ");
    }
    public static void hannotta(int n, char pos1, char pos2, char pos3){
        if(n==1){
            move(pos1,pos3);
        }
        else{
            hannotta(n-1,pos1,pos3,pos2);
            move(pos1,pos3);
            hannotta(n-1,pos2,pos1,pos3);
        }
    }
    public static void main(String[] args) {
        hannotta(1,'A','B','C');
        System.out.println();
        hannotta(2,'A','B','C');
        System.out.println();
        hannotta(3,'A','B','C');
    }
}

A——>C
A——>B A——>C B——>C
A——>C A——>B C——>B A——>C B——>A B——>C A——>C

?? 代碼決議：👇

我們在這里采用的是遞回的思想，該代碼遞回本身展開后十分復雜，所以這里只說明遞回的思想，展開的計算就交給計算機來計算👇

我們參考上面三個轉移的假設，我們可以借助3個盤子的案例得出一個結論：③號盤子在轉移的前幾步是不動的，是①和②號盤子先進行移動的，①和②的起始位置都是A柱，目及地都是B柱，途中①在C柱有一步中轉，所以由于①和②的起始位置以及目及地都是相同的，所以把除去最底層的③號盤剩余的盤子看做一個整體（①和②看做整體），在③轉移到C柱后，由①②組成的整體以B柱作為起始位置，C作為目及地途中①會在A柱中轉一次，通過分析我們三個盤子的案例我們把這個規律應用到64盤子的案例👇

64個盤子：先把除去64號盤子剩余的63個盤子看做一個整體，此整體的起始位置是A柱，會有部分單體需要在C柱進行中轉，目及地是B柱，待64號盤子轉移到C柱后，整體以B柱作為起始位置，部分單體需要在A柱進行中轉，C柱作為整體的目及地，每次完成轉移后整體數-1，直到整體數為1遇到遞回的終止條件，把最后一個盤子由A轉移轉移到C程式結束，這樣就完成了我們所有的盤子按照漢諾塔規則的轉移

圖解：

??逐陳述句決議：

1?? 這里呼叫 hannotta 方法去列印步驟，傳入盤子數量以及ABC三個柱，每列印一種情況的步驟換一次行👇

 public static void main(String[] args) {
        hannotta(1,'A','B','C');
        System.out.println();
        hannotta(2,'A','B','C');
        System.out.println();
        hannotta(3,'A','B','C');
    }

2?? 寫一個 move 方法模擬盤子移動的步驟：👇

 public static void move(char pos1, char pos2){
        System.out.print(pos1+"——>"+pos2+" ");
    }

3?? hannotta實作漢諾塔的方法，這里pos1，pos2，pos3分別是A,B,C柱，方法的第一個引數（pos1）是起始位置，第二個引數（pos2）是中轉位置，第三個引數（pos3）是目及地，進來先判斷如果只有一個盤子，直接由 A 柱轉移到 C 柱，如果盤子的總數 n 大于1，就先把 n-1 個盤子看做整體，按照我們上面說的方法進行移動 👇

   public static void hannotta(int n, char pos1, char pos2, char pos3){
        if(n==1){
            move(pos1,pos3);
        }
        else{
            hannotta(n-1,pos1,pos3,pos2);
            move(pos1,pos3);
            hannotta(n-1,pos2,pos1,pos3);
        }
    }

那我們運行一下64個盤子的案例：😲

hannotta(64,'A','B','C');

截取了一部分運行結果，200年后差不多就可以看見所有的步驟啦😂

👉這就是漢諾塔的解決辦法，代碼雖然簡單，但是對于不熟悉遞回思想的同學有些難，希望本篇文章可以對大家有所幫助！！！如果本篇文章對你有所幫助，還請大家一鍵三連，謝謝支持！！

💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕💕