很多孩子第一次見(jiàn)到漢諾塔問(wèn)題時(shí)，估計(jì)都是一頭霧水吧！也許你最終可以在網(wǎng)上找到標(biāo)準(zhǔn)答案，但是真正理解了它的求解過(guò)程的人應(yīng)該是少之又少了。今天我們就來(lái)給大家詳細(xì)的講解一下漢諾塔問(wèn)題的求解過(guò)程。所謂知己知彼，百戰(zhàn)不殆。在正式開(kāi)始分析問(wèn)題前，先來(lái)聽(tīng)一段故事：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，但不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

64片金片太多，可以讓小朋友們從簡(jiǎn)單的開(kāi)始。假設(shè)3根柱子是A, B, C。1個(gè)盤(pán)片：需要移動(dòng)1次，2個(gè)盤(pán)片：需要移動(dòng)3次，3個(gè)盤(pán)片：需要移動(dòng)7次，具體地，要把3個(gè)盤(pán)片從A號(hào)柱子搬到C號(hào)柱子，那么應(yīng)該首先將上面兩個(gè)1，2號(hào)盤(pán)片搬到B號(hào)柱子（移動(dòng)3次），然后將最底下的3號(hào)盤(pán)片搬到C號(hào)柱子，然后再將1,2號(hào)盤(pán)片從B號(hào)柱子搬到C號(hào)柱子（移動(dòng)3次）。此時(shí)，實(shí)際上已經(jīng)發(fā)現(xiàn)了相同結(jié)構(gòu)的但規(guī)模更小的問(wèn)題。也就是移動(dòng)3個(gè)盤(pán)片，可以利用之前移動(dòng)2個(gè)盤(pán)片的結(jié)果。

在此基礎(chǔ)上，將N個(gè)盤(pán)片從A號(hào)柱移動(dòng)到C號(hào)柱，我們不知道怎么做，但如果我們能首先把N-1個(gè)盤(pán)片從A號(hào)柱移動(dòng)到B號(hào)柱，再把最底下的那個(gè)盤(pán)片從A號(hào)柱移動(dòng)到C號(hào)柱，最后再把B號(hào)柱的N-1個(gè)盤(pán)片移動(dòng)到C號(hào)柱，這個(gè)問(wèn)題就解決了。在移動(dòng)上面N-1個(gè)盤(pán)片的時(shí)候，由于底下的盤(pán)片最大，所以可以假設(shè)它并不存在。因此F(N)=2×F(N-1)+1。

也就是說(shuō)按這一遞推關(guān)系，這個(gè)序列是1，3，7，15，31，63，127， …。可以看出，n個(gè)盤(pán)片移動(dòng)的次數(shù)是2?-1。成功移動(dòng)64個(gè)盤(pán)片需要18446744073709551615次。假如每移動(dòng)一個(gè)盤(pán)片花1秒，并且這些僧侶能夠正確無(wú)誤地移動(dòng)每一步的話(huà)（我是不相信的），需要花大約6000億年才能完成且不論這個(gè)傳說(shuō)是否可信，單從數(shù)學(xué)角度分析，如果每秒移動(dòng)一片金片的話(huà)，則移完所有的金片至少需要5845.54億年。到了那個(gè)時(shí)候，不要說(shuō)地球了，估計(jì)太陽(yáng)系都灰飛煙滅了吧（太陽(yáng)壽命還剩大約50億年）！從這個(gè)角度看，這些僧侶們還真沒(méi)忽悠人，甚至還有人相信婆羅門(mén)至今還在不停的移動(dòng)圓盤(pán)。

漢諾塔問(wèn)題是一個(gè)經(jīng)典遞歸問(wèn)題，漢諾塔問(wèn)題在數(shù)學(xué)界有很高的研究?jī)r(jià)值，而且至今還在被一些數(shù)學(xué)家們所研究，也是我們所喜歡玩的一種益智游戲，它可以幫助開(kāi)發(fā)智力，激發(fā)我們的思維。簡(jiǎn)化這一問(wèn)題，我們先從這一簡(jiǎn)單情形說(shuō)起，也能體會(huì)問(wèn)題內(nèi)在的韻味及魅力.先看看這一問(wèn)題變形版本吧。

問(wèn)題：相傳古印度一座梵塔圣殿中，鑄有一片巨大的黃銅板，之上樹(shù)立了三米高的寶石柱，其中一根寶石柱上插有中心有孔的64枚大小兩兩相異的一寸厚的金盤(pán)，小盤(pán)壓著較大的盤(pán)子，如圖，把這些金盤(pán)全部一個(gè)一個(gè)地從1柱移到3柱上去，移動(dòng)過(guò)程不許以大盤(pán)壓小盤(pán)，不得把盤(pán)子放到柱子之外．移動(dòng)之日，喜馬拉雅山將變成一座金山．

設(shè)h（n）是把n個(gè)盤(pán)子從1柱移到3柱過(guò)程中移動(dòng)盤(pán)子之最少次數(shù)

n＝1時(shí)，h（1）＝1；

n＝2時(shí)，小盤(pán)→2柱，大盤(pán)→3柱，小盤(pán)從2柱→3柱，完成．即h（2）＝3；

n＝3時(shí)，小盤(pán)→3柱，中盤(pán)→2柱，小盤(pán)從3柱→2柱．[即用h（2）種方法把中、小兩盤(pán)移到2柱，大盤(pán)3柱；再用h（2）種方法把中、小兩盤(pán)從2柱3柱，完成；

我們沒(méi)有時(shí)間去移64個(gè)盤(pán)子，但你可由以上移動(dòng)過(guò)程的規(guī)律，計(jì)算n＝6時(shí)，h（6）＝（ ）

A．11 B．31 C．63 D．127

【分析】根據(jù)移動(dòng)方法與規(guī)律發(fā)現(xiàn)，隨著盤(pán)子數(shù)目的增多，都是分兩個(gè)階段移動(dòng)，用盤(pán)子數(shù)目減1的移動(dòng)次數(shù)都移動(dòng)到2柱，然后把最大的盤(pán)子移動(dòng)到3柱，再用同樣的次數(shù)從2柱移動(dòng)到3柱，從而完成，然后根據(jù)移動(dòng)次數(shù)的數(shù)據(jù)找出總的規(guī)律求解即可．

【解答】根據(jù)題意，n＝1時(shí)，h（1）＝1，

n＝2時(shí)，小盤(pán)→2柱，大盤(pán)→3柱，小盤(pán)從2柱→3柱，完成，即h（2）＝3＝22﹣1；

n＝3時(shí)，小盤(pán)→3柱，中盤(pán)→2柱，小盤(pán)從3柱→2柱，[用h（2）種方法把中、小兩盤(pán)移到2柱，大盤(pán)3柱；再用h（2）種方法把中、小兩盤(pán)從2柱3柱，完成]，

h（3）＝h（2）+h（2）+1＝3×2+1＝7＝23﹣1，

h（4）＝h（3）+h（3）+1＝7×2+1＝15＝2^4﹣1，

…

以此類(lèi)推，h（n）＝h（n﹣1）+h（n﹣1）+1＝2?﹣1，

∴h（6）＝2^6﹣1＝64﹣1＝63．故選：C．

【點(diǎn)評(píng)】本題考查了圖形變化的規(guī)律問(wèn)題，根據(jù)題目信息，得出移動(dòng)次數(shù)分成兩段計(jì)數(shù)，利用盤(pán)子少一個(gè)時(shí)的移動(dòng)次數(shù)移動(dòng)到2柱，把最大的盤(pán)子移動(dòng)到3柱，然后再用同樣的次數(shù)從2柱移動(dòng)到3柱，從而完成移動(dòng)過(guò)程是解題的關(guān)鍵，本題對(duì)閱讀并理解題目信息的能力要求比較高．

變式1.老王和小王父子倆玩一種類(lèi)似于古代印度的"漢諾塔游戲"；有3個(gè)柱子甲、乙、丙，在甲柱上現(xiàn)有4個(gè)盤(pán)子，最上面的兩個(gè)盤(pán)子大小相同，從第二個(gè)盤(pán)子往下大小不等，大的在下，小的在上（如圖），把這4個(gè)盤(pán)子從甲柱全部移到乙柱游戲即結(jié)束，在移動(dòng)過(guò)程中每次只能移動(dòng)一個(gè)盤(pán)子，甲、乙、丙柱都可以利用，且3個(gè)柱子上的盤(pán)子始終保持小的盤(pán)子不能放在大的盤(pán)子之下，設(shè)游戲結(jié)束需要移動(dòng)的最少次數(shù)為n，則n＝（ ）

A．15 B．11 C．8 D．7

【解答】由題意得，根據(jù)甲乙丙三圖可知最上面的兩個(gè)是一樣大小的，

所以比三個(gè)操作的此時(shí)（23﹣1）要多，此四個(gè)操作的此時(shí)（2^4﹣1）要少，

相當(dāng)與操作三個(gè)的時(shí)候，最上面的那個(gè)動(dòng)了幾次，就會(huì)增加幾次，故選：B．

【點(diǎn)評(píng)】本題考查了圖形變化的規(guī)律問(wèn)題，根據(jù)題目信息，得出移動(dòng)次數(shù)分成兩段計(jì)數(shù)，利用盤(pán)子少一個(gè)時(shí)的移動(dòng)次數(shù)移動(dòng)到乙盤(pán)，再把最大的盤(pán)子移動(dòng)到丙盤(pán)，然后再用同樣的次數(shù)從乙柱移動(dòng)到丙柱，從而完成移動(dòng)過(guò)程是解題的關(guān)鍵，本題對(duì)閱讀并理解題目住處的能力要求比較高．試題

變式2.小張和小王兩位同學(xué)課余時(shí)間玩一種類(lèi)似于古代印度的" 漢諾塔游戲"．有甲、乙丙3個(gè)柱子，甲柱子上有n（n≥3）個(gè)盤(pán)子，從上往下大小不等，大的在下，小的在上（如圖），把這n個(gè)盤(pán)子從甲柱子全部移到乙柱子上游戲結(jié)東，在移動(dòng)過(guò)程中每次只能夠移動(dòng)一個(gè)盤(pán)子，甲、乙、丙3個(gè)柱子都可以利用，且3個(gè)柱子上的盤(pán)子始終保持小的盤(pán)子不能放在大的盤(pán)子

【點(diǎn)評(píng)】本題考查的知識(shí)要點(diǎn)：數(shù)列的通項(xiàng)公式的求法及應(yīng)用，主要考查學(xué)生的運(yùn)算能力和轉(zhuǎn)化能力，屬于基礎(chǔ)題型．

變式3.古代印度婆羅門(mén)教寺廟內(nèi)的僧侶們?cè)?jīng)玩過(guò)一種被稱(chēng)為"漢諾塔問(wèn)題"的游戲，其玩法如下：如圖，設(shè)有n（n∈N*）個(gè)圓盤(pán)依其半徑大小，大的在下，小的在上套在A柱上，現(xiàn)要將套在A柱上的盤(pán)換到C柱上，要求每次只能搬動(dòng)一個(gè)，而且任何時(shí)候不允許將大盤(pán)套在小盤(pán)上面，假定有三根柱子A、B、C可供使用．

本題的（1）問(wèn)關(guān)鍵是從特殊中發(fā)現(xiàn)一般性的規(guī)律，考查構(gòu)造法求數(shù)列的通項(xiàng)；（2）問(wèn)體現(xiàn)等價(jià)轉(zhuǎn)化的數(shù)學(xué)思想，同時(shí)應(yīng)注意放縮法的運(yùn)用．

漢諾塔問(wèn)題（游戲）還有個(gè)最關(guān)鍵的問(wèn)題就是第一步的第一小步是將頂層圓盤(pán)挪至輔助柱還是還是目標(biāo)柱的問(wèn)題。說(shuō)它關(guān)鍵，是因?yàn)橐徊藉e(cuò)，步步錯(cuò)。第一步走錯(cuò)了，后面再怎么走，也不會(huì)走對(duì)。那這關(guān)鍵的第一步該怎么走呢？經(jīng)過(guò)推理與分析，找到了問(wèn)題的答案：若塔層數(shù)為奇數(shù)，頂層圓盤(pán)應(yīng)首先放在目標(biāo)柱；若是偶數(shù)，則放在輔助柱。這就是漢諾塔，一款起源于印度古老傳說(shuō)的簡(jiǎn)單而又不那么簡(jiǎn)單的益智小游戲。從漢諾塔游戲中的規(guī)律可發(fā)現(xiàn)漢諾塔游戲中蘊(yùn)藏著豐富的數(shù)學(xué)內(nèi)容，因此，玩好漢諾塔游戲不僅可以從中獲得游戲的快樂(lè)，而且還能夠從中學(xué)到很多數(shù)學(xué)知識(shí)，體會(huì)很多數(shù)學(xué)思想與數(shù)學(xué)方法。小游戲中蘊(yùn)含大智慧，雖然比賽結(jié)束了，但是游戲精神，思維模式會(huì)伴隨著孩子的成長(zhǎng)，使孩子們終生受益。

狗尾續(xù)貂說(shuō)一點(diǎn)，遞歸在計(jì)算機(jī)中占有極為重要的地位，從形式化定義到算法，它的身影無(wú)處不在。可以這么說(shuō)，對(duì)初涉編程的人，是否會(huì)用遞歸思維去解決問(wèn)題是一名普通程序員邁向一名優(yōu)秀程序員的一大門(mén)檻。從小讓孩子具備一些遞歸思維，漢諾塔游戲是學(xué)習(xí)編程優(yōu)質(zhì)素材，或許會(huì)讓孩子學(xué)習(xí)編程容易一點(diǎn)，在未來(lái)受益匪淺。