漢諾塔問題的求解與分析

一、遞歸算法介紹

????????這篇文章講的是一個(gè)古老而又經(jīng)典的漢諾塔問題,他是遞歸算法的一個(gè)很好的應(yīng)用實(shí)例寻行。有關(guān)遞歸函數(shù)的介紹,在使用遞歸函數(shù)求解字符串的逆置問題文章中介紹過匾荆。遞歸思想是來解決可計(jì)算問題的拌蜘,他的根本特征在于逐步的計(jì)算和分解這一計(jì)算,通過將某一大問題不斷的分解成邏輯上相同的小問題牙丽,然后對小問題的求解進(jìn)而獲得最終的答案简卧。使用遞歸算法的程序在形式上往往都比較簡潔明了,這也正是他的價(jià)值所在烤芦。(更好地閱讀體驗(yàn)举娩,請?jiān)L問程序員在旅途
  計(jì)算機(jī)使用棧內(nèi)存結(jié)構(gòu)來從物理上實(shí)現(xiàn)遞歸算法,每一次的遞歸調(diào)用拍棕,系統(tǒng)都要將本次調(diào)用的返回地址晓铆、局部變量、形式參數(shù)等值壓入到棧中绰播,調(diào)用結(jié)束之后骄噪,再從棧頂取出保存的信息返回給相應(yīng)的變量并退出棧,再繼續(xù)執(zhí)行遞歸的上一層函數(shù)蠢箩。由于計(jì)算機(jī)系統(tǒng)給每一個(gè)程序分配的椓慈铮空間有限,因此谬泌,在使用遞歸求解問題的時(shí)候滔韵,一定要注意遞歸的深度,如果遞歸的次數(shù)太多掌实,很可能會出現(xiàn)棧溢出的情況陪蜻,導(dǎo)致問題求解失敗。

二贱鼻、漢諾塔問題

2.1 問題由來

相傳在古印度圣廟中宴卖,有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上邻悬,有三根桿(編號A症昏、B、C)父丰,在A桿自下而上肝谭、由大到小按順序放置64個(gè)金盤。游戲的目標(biāo):把A桿上的金盤全部移到C桿上,并仍保持原有順序疊好攘烛。操作規(guī)則:每次只能移動(dòng)一個(gè)盤子魏滚,并且在移動(dòng)過程中三根桿上都始終保持大盤在下,小盤在上坟漱,操作過程中盤子可以置于A栏赴、B、C任一桿上.


漢諾塔柱子.png

2.2 問題分析

????????漢諾塔問題是一種多分支的遞歸解法靖秩,相對于單分支的遞歸解法(如:階乘的遞歸解法)來說,不太容易理解竖瘾,但是只要把握住遞歸的思想核心就能夠理解這個(gè)程序的邏輯沟突。漢諾塔解法總結(jié)起來有三步驟:

1) 把 N-1個(gè)盤子 移到中轉(zhuǎn)柱
2)把第N個(gè)盤子移動(dòng)到 目標(biāo)柱
3)把中轉(zhuǎn)柱上面的N-1個(gè)盤子借助目前空閑的柱子 移動(dòng)到 目標(biāo)柱。

????????注意捕传,上面的中轉(zhuǎn)柱惠拭,起始柱,是會變化的庸论。每一層遞歸的邏輯都是职辅,借助"目標(biāo)柱子",將n-1個(gè) 盤子移動(dòng)到 "中轉(zhuǎn)柱"聂示,然后再將最后一個(gè)盤子移動(dòng)到"目標(biāo)柱子"域携,再將中轉(zhuǎn)柱上的盤子按照同樣的規(guī)律移動(dòng)到"目標(biāo)柱子"。
  無論有多少盤子鱼喉,在移動(dòng)的過程中秀鞭,都是遵循上面的三個(gè)步驟。在移動(dòng)第N個(gè)盤子的時(shí)候扛禽,我們總得要想辦法把前面N-1個(gè)盤子移到中轉(zhuǎn)柱锋边,然后才能將第N個(gè)盤子移到目標(biāo)柱。在移動(dòng)第N-1個(gè)盤子的時(shí)候编曼,也是得要把前面N-2個(gè)盤子移到中轉(zhuǎn)柱豆巨,然后才能把第N-1個(gè)盤子移到目標(biāo)柱。所以掐场,你可以看到往扔,移動(dòng)N、N-1刻肄、N-2···號盤子到目標(biāo)柱的思路是一樣的瓤球,因此,我們可以用遞歸的思想解決這個(gè)問題敏弃。

2.3 程序?qū)崿F(xiàn)

#include<stdio.h>

void hnt(int n, char a,  char b, char c){

   if(n == 1){   // 遞歸出界條件
   
       printf("%c -- > %c \n", a,c); 
   }else{
       /*
       每一層遞歸的邏輯都是卦羡,借助"目標(biāo)柱子",將n-1個(gè) 盤子移動(dòng)到  "中轉(zhuǎn)柱",然后再將最后一個(gè)盤子移動(dòng)到"目標(biāo)柱子".

       注意绿饵,這里的中轉(zhuǎn)柱是會變化的欠肾。

       */
       hnt(n-1,a,c,b); // ① 借助 c 柱子將a柱子上的n-1個(gè)盤子 移動(dòng)到 b 柱子上

       printf("%c -- > %c \n", a,c); //  ② 將 a柱子上的第n個(gè)盤子 移動(dòng)到 c柱子上

       hnt(n-1, b,a,c);  // ③ 將在b柱子上的n-1個(gè)盤子,借助 a 柱子(此時(shí)a空閑) 移動(dòng)到 c 柱子上
   }
}

int main(){
   int n;
   scanf("%d", &n);
   hnt(n,'a','b','c');
   return 0;
}

2.4 程序分析

????????通過對漢諾塔問題的分析拟赊,你或許會明白刺桃,上面的程序是可以求解出問題的答案,但是你可能會有一些疑惑吸祟,為什么上面的程序瑟慈,可以記錄下每一步的移動(dòng)過程?對于這種多分支的遞歸算法來說屋匕,如果像理解單分支遞歸那樣葛碧,在腦海中盡可能的窮舉出每一步的移動(dòng)過程,有時(shí)候是很困難的过吻,這樣也不符合用遞歸解決問題的原則进泼。但是如果我們實(shí)在是想搞明白這每一步具體的過程,怎么辦呢纤虽?下面用歸納總結(jié)的方式乳绕,來列出N∈[1,4]的移動(dòng)過程,分析他的移動(dòng)規(guī)律逼纸。
  當(dāng)N =1時(shí):


n=1.png

當(dāng)N =2時(shí):

n=2.png

當(dāng)N =3時(shí):
  通過N=1洋措,N=2的求解,我們可以推斷出樊展,N =3的時(shí)候呻纹,會有 3 + 1 + 3 = 7次移動(dòng)。3個(gè)盤子的話专缠,我們得要先把前兩個(gè)盤子移到B雷酪,然后把第三個(gè)盤子移到C,最后再把B上面的兩個(gè)盤子涝婉,借助A移動(dòng)到C哥力。上面的兩個(gè)盤子,先是移動(dòng)到B墩弯,然后又移動(dòng)到C吩跋,這兩個(gè)過程,需要的移動(dòng)次數(shù)是一樣的渔工,移動(dòng)邏輯也是一樣的锌钮。


n=3.png

當(dāng)N =4時(shí):
  還是前面的邏輯,N=4的時(shí)候引矩,會有 7 + 1 + 7 = 15次移動(dòng)梁丘。思路和前面一樣侵浸, 把前3個(gè)盤子,借助C移到B氛谜,再把第四個(gè)盤子移到C掏觉。


n=4.png

????????通過前面的幾個(gè)演示能看得出來,求解 N 和求解 N-1 的思路完全一致值漫,這是保證可以使用遞歸算法的核心所在澳腹。
  A、B杨何、C只是形式上的標(biāo)注酱塔,本質(zhì)上面的意義是,起始危虱、中轉(zhuǎn)延旧、目標(biāo)。在移動(dòng)過程中槽地,如果要保證小的在上,大的在下芦瘾,我們就必須得要借助中轉(zhuǎn)捌蚊,才可以實(shí)現(xiàn),至于中轉(zhuǎn)是誰近弟,這和(N-1)這一堆盤子所在的位置有關(guān)缅糟。
  在寫遞歸程序的時(shí)候,需要注意的點(diǎn)如下圖所示:


程序注意點(diǎn).png

三祷愉、總結(jié)

????????遞歸算法的核心在于遞推邏輯窗宦,因此,使用遞歸算法求解問題二鳄,我們不必要糾結(jié)每一層函數(shù)的具體操作是什么樣子的赴涵,而要把核心放在邏輯上,如果問題的求解是可歸納的订讼,有遞推關(guān)系在里面髓窜,并且是可計(jì)算的,那么邏輯上就不存在問題欺殿,一般也就可以使用遞歸算法來求解寄纵。
  遞歸有單分支的遞歸和多分支遞歸,單分支相對來說簡單理解一些脖苏,比如下面的遞歸程序

int f(int n) //求n的階乘
{
  int fac;
  if (n == 0 || n == 1)
    fac = 1;
  else
    fac = f(n - 1) * n;
  return fac;
}

????????多分支的如漢諾塔恍涂、二叉樹遍歷等诊沪,就比較難理解一些,但是思想是一樣的。
  計(jì)算機(jī)執(zhí)行遞歸程序的時(shí)候,對每一層函數(shù)的調(diào)用鹤树,是使用棧數(shù)據(jù)結(jié)構(gòu)來進(jìn)行現(xiàn)場保護(hù)的,因此在編寫遞歸程序的時(shí)候,要注意遞歸的深度至扰,防止出現(xiàn) Stack Overflow 異常。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末资锰,一起剝皮案震驚了整個(gè)濱河市敢课,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌绷杜,老刑警劉巖直秆,帶你破解...
    沈念sama閱讀 222,464評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異鞭盟,居然都是意外死亡圾结,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,033評論 3 399
  • 文/潘曉璐 我一進(jìn)店門齿诉,熙熙樓的掌柜王于貴愁眉苦臉地迎上來筝野,“玉大人,你說我怎么就攤上這事粤剧⌒梗” “怎么了?”我有些...
    開封第一講書人閱讀 169,078評論 0 362
  • 文/不壞的土叔 我叫張陵抵恋,是天一觀的道長焕议。 經(jīng)常有香客問我,道長弧关,這世上最難降的妖魔是什么盅安? 我笑而不...
    開封第一講書人閱讀 59,979評論 1 299
  • 正文 為了忘掉前任,我火速辦了婚禮世囊,結(jié)果婚禮上别瞭,老公的妹妹穿的比我還像新娘。我一直安慰自己株憾,他們只是感情好畜隶,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,001評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著号胚,像睡著了一般籽慢。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上猫胁,一...
    開封第一講書人閱讀 52,584評論 1 312
  • 那天箱亿,我揣著相機(jī)與錄音,去河邊找鬼弃秆。 笑死届惋,一個(gè)胖子當(dāng)著我的面吹牛髓帽,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播脑豹,決...
    沈念sama閱讀 41,085評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼郑藏,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了瘩欺?” 一聲冷哼從身側(cè)響起必盖,我...
    開封第一講書人閱讀 40,023評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎俱饿,沒想到半個(gè)月后歌粥,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,555評論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡拍埠,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,626評論 3 342
  • 正文 我和宋清朗相戀三年失驶,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片枣购。...
    茶點(diǎn)故事閱讀 40,769評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡嬉探,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出棉圈,到底是詐尸還是另有隱情甲馋,我是刑警寧澤,帶...
    沈念sama閱讀 36,439評論 5 351
  • 正文 年R本政府宣布迄损,位于F島的核電站,受9級特大地震影響账磺,放射性物質(zhì)發(fā)生泄漏芹敌。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,115評論 3 335
  • 文/蒙蒙 一垮抗、第九天 我趴在偏房一處隱蔽的房頂上張望氏捞。 院中可真熱鬧,春花似錦冒版、人聲如沸液茎。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,601評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽捆等。三九已至,卻和暖如春续室,著一層夾襖步出監(jiān)牢的瞬間栋烤,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,702評論 1 274
  • 我被黑心中介騙來泰國打工挺狰, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留明郭,地道東北人买窟。 一個(gè)月前我還...
    沈念sama閱讀 49,191評論 3 378
  • 正文 我出身青樓,卻偏偏與公主長得像薯定,于是被迫代替她去往敵國和親始绍。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,781評論 2 361