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

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

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

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

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

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

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

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

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

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

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

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

【分析】根據(jù)移動(dòng)方法與規(guī)律發(fā)現(xiàn)，隨著盤子數(shù)目的增多，都是分兩個(gè)階段移動(dòng)，用盤子數(shù)目減1的移動(dòng)次數(shù)都移動(dòng)到2柱，然后把最大的盤子移動(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í)，小盤→2柱，大盤→3柱，小盤從2柱→3柱，完成，即h（2）＝3＝22﹣1；

n＝3時(shí)，小盤→3柱，中盤→2柱，小盤從3柱→2柱，[用h（2）種方法把中、小兩盤移到2柱，大盤3柱；再用h（2）種方法把中、小兩盤從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，

…

以此類推，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ī)律問題，根據(jù)題目信息，得出移動(dòng)次數(shù)分成兩段計(jì)數(shù)，利用盤子少一個(gè)時(shí)的移動(dòng)次數(shù)移動(dòng)到2柱，把最大的盤子移動(dòng)到3柱，然后再用同樣的次數(shù)從2柱移動(dòng)到3柱，從而完成移動(dòng)過程是解題的關(guān)鍵，本題對(duì)閱讀并理解題目信息的能力要求比較高．

變式1.老王和小王父子倆玩一種類似于古代印度的"漢諾塔游戲"；有3個(gè)柱子甲、乙、丙，在甲柱上現(xiàn)有4個(gè)盤子，最上面的兩個(gè)盤子大小相同，從第二個(gè)盤子往下大小不等，大的在下，小的在上（如圖），把這4個(gè)盤子從甲柱全部移到乙柱游戲即結(jié)束，在移動(dòng)過程中每次只能移動(dòng)一個(gè)盤子，甲、乙、丙柱都可以利用，且3個(gè)柱子上的盤子始終保持小的盤子不能放在大的盤子之下，設(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ī)律問題，根據(jù)題目信息，得出移動(dòng)次數(shù)分成兩段計(jì)數(shù)，利用盤子少一個(gè)時(shí)的移動(dòng)次數(shù)移動(dòng)到乙盤，再把最大的盤子移動(dòng)到丙盤，然后再用同樣的次數(shù)從乙柱移動(dòng)到丙柱，從而完成移動(dòng)過程是解題的關(guān)鍵，本題對(duì)閱讀并理解題目住處的能力要求比較高．試題

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

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

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

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

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

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