最適合菜鳥的漢諾塔講解
問題引入
漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
讓我們先從小事入手。
標記漢諾塔的三根柱子分別為 a ，b ，c
標記漢諾塔上的圓盤分別為：1 ，2，3，4 …n
a 柱上面只有一個圓盤時
只有這一種走法
a柱上有兩個圓盤時
a柱上有三個圓盤時
a柱上有四個圓盤時
如上圖的實際操作過程可以很明顯的找到漢諾塔的操作規律：即分出來三個部分：
第一部分為 第一個紅框，用于將 前 n -1 個圓盤移到 b 柱
第二部分 用于將 最大的盤子移到 c 柱
第三部分為 第二個紅框，用于將 前 n - 1 個圓盤移到 c 柱
我們之所以這樣分為三個部分，是因為不管 a 柱上放了幾個盤子讓你移動 ，這三個部分是他們很明顯的共性，這便是規律所在。
（這樣的規律也是我們使用遞歸來解決漢諾塔問題的基礎。正是因為他們有共性的地方，我們才可以將其共性的地方外包給下一級。）
記住，千萬不要試圖去糾結 紅框 內部的圓盤具體移動方式，這是沒有任何規律可循的，想到死也想不出來的。
用遞歸解決問題
上面我們已經強調過了他們共性的部分是可以外包給下一級的
由此一來我們便可以將 n 個盤子的紅框部分 外包 給 下一級的 n-1
n-1 再將自己的紅框部分 外包 給 下一級的 n-2
n-2 同樣像上面那樣外包下去 直至 要動的盤子數為 1，程序便可以執行了
執行完之后，返回上一級執行 ，上一級結束再去上上級 ， 如同多米諾骨牌一樣，n == 1 是引起垮塌的關鍵牌
函數創建
根據我們分析出的漢諾塔特性就可以創建出我們需要的遞歸函數，我們發現，在外包的時候還是有一些細微的問題需要注意的
比如
將 “4 個盤從a移到c” 中的 “將 3 個盤從 a 移到 b” 的操作 外包 給 “將 3 個盤從 a 移到 c” 時，雖然這是兩者共性
本質操作都是一樣的，移的都是相同數量的盤子，但是 他們移的目的柱是不一樣的，所以我們可以使柱子交換位置（注意這并不是真的交換，這是通過函數參數位置的改變來實現） 總而言之，就是一句話，將 “將 3 個盤從 a 移到 b” 中的 b 柱強行視為 c 柱，通過函數傳參就可以實現這種效果。
落實到代碼上就是
h(int n,char a,char b,char c) {
if(n == 1){
System.out.println(a+"-->"+c);
}
h(n-1,a,c,b);
System.out.println(a+"-->"+c);
h(n-1,b,a,c);
}
思維圖
到此這篇關于Java手把手必會的實例漢諾塔講解練習的文章就介紹到這了,更多相關Java 漢諾塔 內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/qq_54693675/article/details/120242495
