Java 細緻圖解帶你分析漢諾塔

2022-03-23 16:00:59

一、漢諾塔問題來源

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

二、問題分析

從簡單問題開始

直接拿64個盤子來想，可能會比較難，我們可以先從1個盤子開始看，如下圖：

一個盤子

A -> C

只有一個盤子情況下，我們可以直接將 A 柱子上面的盤子移到 C 柱子上

需要移動一次

兩個盤子

當有兩個盤子時，我們也可以通過下面方式實現：

A -> B A->C B->C

需要移動3次

1. A -> B

2. A -> C

3. B -> C

三個盤子

當有三個盤子時，移動步驟如下：

A -> C A -> B C -> B A -> C B -> A B -> C A -> C

共需要移動7次

1. A -> C

2. A -> B

3. C -> B

4. A -> C

5. B -> A

6. B -> C

7. A -> C

這就完成了3個盤子的移動

當有 4 個盤子時，這個問題其實就已經很複雜了

規律推導

1個盤子移動1次

2個盤子移動3次

3個盤子移動7次

……

N 個盤子移動 2^N - 1 次

那麼64個盤子就是需要移動 2^64 - 1 次

三、解決問題

我們可以通過遞回來解決這個問題，獲得正確的移動方式

如果有N個盤子該怎麼移動呢？

整體思路

我們可以先將 N - 1 個盤子從 A 柱藉助 C 柱移動到 B 柱，再將 A 柱剩下的一個盤子移動到 C柱，然後將 B 柱上的 N - 1 個盤子藉助 A 柱移動到 C 柱，就完成了所有柱子的移動（中間具體移動過程暫不討論）

上程式碼

public static void hanoi(int num, String src, String help, String dest) {
    if (num == 1) {     // 只有一個盤子的時候直接移動
        System.out.print(src + "->" + dest + "  ");  // 將一個盤子從源柱子挪到目標柱子
    } else {
        hanoi(num - 1, src, dest, help);   // 將n - 1個盤子從源柱子藉助目標柱子挪到輔助柱子
        System.out.print(src + "->" + dest + "  ");  // 將一個盤子從源柱子挪到目標柱子
        hanoi(num - 1, help, src, dest);  // 將輔助柱子上n - 1個盤子藉助源柱子挪到目標柱子
    }
}
public static void main(String[] args) {
    hanoi(3, "A", "B", "C");
}

這段程式碼中 src 是源柱子，help是輔助柱子，dest 是目標柱子

這是一個二路遞迴

執行結果：

這就成功完成了盤子的移動

四、婆羅門能否完成大梵天的任務

移動 64 個盤子需要多長時間

在這裡我們假設婆羅門的人都非常聰明，不需要思考就直接能知道正確的移動方法，移動一個盤子需要一秒鐘，一直不停的移

將2^64 - 1秒換算為年約為5849 4241 7355年（5849.42億年），而地球存在至今不過45億年，太陽系的預期壽命據說也就是數百億年。真的過了5849.42億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。

相關預言

有預言說，這件事完成時宇宙會在一瞬間閃電式毀滅。也有人相信婆羅門至今還在一刻不停地搬動著圓盤

計算機移動64個盤子需要多長時間？

我的電腦核心頻率為2.90GHz，也就是每秒鐘運算 29 億次，那麼移動 2^64 - 1次需要的時間約為201年

到此這篇關於Java 細緻圖解帶你分析漢諾塔的文章就介紹到這了,更多相關Java 漢諾塔內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Java 細緻圖解帶你分析漢諾塔

目錄

一、漢諾塔問題來源

二、問題分析

從簡單問題開始

三、解決問題

整體思路

四、婆羅門能否完成大梵天的任務

移動 64 個盤子需要多長時間

計算機移動64個盤子需要多長時間？

熱門文章

Java 細緻圖解帶你分析漢諾塔

目錄

一、漢諾塔問題來源

二、問題分析

從簡單問題開始

三、解決問題

整體思路

四、婆羅門能否完成大梵天的任務

移動 64 個盤子需要多長時間

計算機移動64個盤子需要多長時間 ？

熱門文章

計算機移動64個盤子需要多長時間？