手撕“漢諾塔算法”之詳細圖解

hello，你好呀，我是灰小猿，一個超會寫bug的程序猿，

今天和大家分享一個遞歸經典算法案例---“漢諾塔”。

漢諾塔問題回顧

漢諾塔(Tower of Hanoi)源于印度傳說中，大梵天創造世界時造了三根金鋼石柱子，其中一根柱子自底向上疊著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

這是一個著名的問題，幾乎所有的教材上都有對這個問題的介紹。由于條件是：

借助一個中轉柱，使起始柱中按照規則排放的盤子移動到終點柱，且一次只能移動一個盤，且不允許大盤放在小盤上面，所以64個盤的移動次數是：18,446,744,073,709,551,615

這是一個天文數字，若每一微秒可能計算(并不輸出)一次移動，那么也需要幾乎一百萬年。我們僅能找出問題的解決方法并解決較小N值時的漢諾塔，但很難用計算機解決64層的漢諾塔。

在平常的編程練習過程中，漢諾塔問題也是一個十分常見的算法案例。今天我就和小伙伴們具體分析一下漢諾塔問題的解決方案。

首先我們來看一個三層漢諾塔的圖解，來對漢諾塔問題的解決有一個簡單的了解：

如上圖所示，我們可以看出，當盤子的數量只有一個的時候，我們可以直接將盤子移動到目標盤，在進行三層漢諾塔問題的解決時。我們先將最上方的兩個盤子借助目標盤移動至中轉盤，再將最大的盤子移動至目標盤，之后再將中轉盤上的第一個盤子移動至起始盤，這個時候我們就可以將二號盤移動至目標盤，最后將起始盤上的一號盤移動至目標盤。

由此我們可以總結出n層漢諾塔的解決方案：

將前n-1個盤子借助當前的中轉盤（不一定是B托盤）移動至相鄰的空托盤上，再將第n個盤子移動至目標盤，之后重復上述步驟直至將所有的盤子都移動至目標盤。在這個也用到了函數方法的遞歸思想。

接下來分別使用java和Python向大家演示一下n階漢諾塔的求解方法：

Java求解漢諾塔

package 漢諾塔算法;

public class Hanoi {

public static void main(String[] args) {

// TODO Auto-generated method stub

Hanoi h = new Hanoi();

char a = 'A';

char b = 'B';

char c = 'C';

int count = h.hanoi(3, a, b, c);

System.out.println(count);

}

/**

* 漢諾塔問題

* @param n 階數

* @param a 起始柱

* @param b 中轉柱

* @param c 目標柱

* @return 移動次數

* */

public int hanoi(int n,char a,char b,char c) {

if (n == 1) {

move(a, c);

} else {

hanoi(n-1, a, c, b);

move(a, c);

hanoi(n-1, b, a, c);

}

//漢諾塔的移動次數為（2**n）-1

return (int) Math.pow(2, n)-1;

}

public void move(char a,char b) {

System.out.println(a + "--->" + "b");

}

}

Python求解漢諾塔

i = 1 # 定義全局變量記錄次數

def move(n, a, c):

global i

print("第{}步：將編號為{}的盤子從{}--->{}".format(i, n, a, c))

i += 1

def hanoi(n,a,b,c):

#a,b,c分別是三根柱子，n為套在a柱上的圓圈個數

if n == 1:

move(n, a, c)

else:

hanoi(n-1, a, c, b)

move(n, a, c)

hanoi(n-1, b, a, c)

if __name__ == '__main__':

n = int(input("請輸入盤子數量："))

hanoi(n, "A", "B", "C")

好了，關于漢諾塔問題的講解就和小伙伴們分享到這里，有不足的地方還希望大家提出指正，大灰狼陪你一起進步！

Java

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。