快捷導(dǎo)航

Java手把手必會(huì)的實(shí)例漢諾塔講解練習(xí)

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

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

最適合菜鳥(niǎo)的漢諾塔講解

問(wèn)題引入

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

讓我們先從小事入手。

標(biāo)記漢諾塔的三根柱子分別為 a ，b ，c

標(biāo)記漢諾塔上的圓盤(pán)分別為：1 ，2，3，4 …n

a 柱上面只有一個(gè)圓盤(pán)時(shí)

只有這一種走法

a柱上有兩個(gè)圓盤(pán)時(shí)

a柱上有三個(gè)圓盤(pán)時(shí)

a柱上有四個(gè)圓盤(pán)時(shí)

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

第一部分為第一個(gè)紅框，用于將前 n -1 個(gè)圓盤(pán)移到 b 柱

第二部分用于將最大的盤(pán)子移到 c 柱

第三部分為第二個(gè)紅框，用于將前 n - 1 個(gè)圓盤(pán)移到 c 柱

我們之所以這樣分為三個(gè)部分，是因?yàn)椴还?a 柱上放了幾個(gè)盤(pán)子讓你移動(dòng) ，這三個(gè)部分是他們很明顯的共性，這便是規(guī)律所在。

（這樣的規(guī)律也是我們使用遞歸來(lái)解決漢諾塔問(wèn)題的基礎(chǔ)。正是因?yàn)樗麄冇泄残缘牡胤?，我們才可以將其共性的地方外包給下一級(jí)。）

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

用遞歸解決問(wèn)題

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

由此一來(lái)我們便可以將 n 個(gè)盤(pán)子的紅框部分外包給下一級(jí)的 n-1

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

n-2 同樣像上面那樣外包下去直至要?jiǎng)拥谋P(pán)子數(shù)為 1，程序便可以執(zhí)行了

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

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

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

比如

將 “4 個(gè)盤(pán)從a移到c” 中的 “將 3 個(gè)盤(pán)從 a 移到 b” 的操作外包給 “將 3 個(gè)盤(pán)從 a 移到 c” 時(shí)，雖然這是兩者共性

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

落實(shí)到代碼上就是

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