漢諾塔問題的求解與分析

一、遞歸算法介紹

????????這篇文章講的是一個(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 異常。