快捷導航

Java手把手必會的實例漢諾塔講解練習

更新時間：2021年09月26日 15:23:41 作者：愛內(nèi)卷的王同學

漢諾塔，傳說神在創(chuàng)造世界的時候做了三根金剛石柱子，并在一個教塔里留下了三根金剛石棒，第一根上面從上到下套著64個按從小到大排列的金盤，神命令廟里的眾僧將它們一個個地從這根金剛石棒搬到另一根金剛石棒上，大盤不能放在小盤上。最后64個金盤仍然要按從小到大排列

最適合菜鳥的漢諾塔講解

問題引入

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

讓我們先從小事入手。

標記漢諾塔的三根柱子分別為 a ，b ，c

標記漢諾塔上的圓盤分別為：1 ，2，3，4 …n

a 柱上面只有一個圓盤時

只有這一種走法

a柱上有兩個圓盤時

a柱上有三個圓盤時

a柱上有四個圓盤時

如上圖的實際操作過程可以很明顯的找到漢諾塔的操作規(guī)律：即分出來三個部分：

第一部分為第一個紅框，用于將前 n -1 個圓盤移到 b 柱

第二部分用于將最大的盤子移到 c 柱

第三部分為第二個紅框，用于將前 n - 1 個圓盤移到 c 柱

我們之所以這樣分為三個部分，是因為不管 a 柱上放了幾個盤子讓你移動，這三個部分是他們很明顯的共性，這便是規(guī)律所在。

（這樣的規(guī)律也是我們使用遞歸來解決漢諾塔問題的基礎(chǔ)。正是因為他們有共性的地方，我們才可以將其共性的地方外包給下一級。）

記住，千萬不要試圖去糾結(jié) 紅框內(nèi)部的圓盤具體移動方式，這是沒有任何規(guī)律可循的，想到死也想不出來的。

用遞歸解決問題

上面我們已經(jīng)強調(diào)過了他們共性的部分是可以外包給下一級的

由此一來我們便可以將 n 個盤子的紅框部分外包給下一級的 n-1

n-1 再將自己的紅框部分外包給下一級的 n-2

n-2 同樣像上面那樣外包下去直至要動的盤子數(shù)為 1，程序便可以執(zhí)行了

執(zhí)行完之后，返回上一級執(zhí)行，上一級結(jié)束再去上上級，如同多米諾骨牌一樣，n == 1 是引起垮塌的關(guān)鍵牌

函數(shù)創(chuàng)建

根據(jù)我們分析出的漢諾塔特性就可以創(chuàng)建出我們需要的遞歸函數(shù)，我們發(fā)現(xiàn)，在外包的時候還是有一些細微的問題需要注意的

比如

將 “4 個盤從a移到c” 中的 “將 3 個盤從 a 移到 b” 的操作外包給 “將 3 個盤從 a 移到 c” 時，雖然這是兩者共性

本質(zhì)操作都是一樣的，移的都是相同數(shù)量的盤子，但是他們移的目的柱是不一樣的，所以我們可以使柱子交換位置（注意這并不是真的交換，這是通過函數(shù)參數(shù)位置的改變來實現(xiàn)）總而言之，就是一句話，將 “將 3 個盤從 a 移到 b” 中的 b 柱強行視為 c 柱，通過函數(shù)傳參就可以實現(xiàn)這種效果。

落實到代碼上就是

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);
}