C#利用遞歸算法解決漢諾塔問題

第C#利用遞歸算法解決漢諾塔問題目錄一、什么是遞歸二、漢諾塔問題1.漢諾塔的故事2.解決思路3.怎么解決漢諾塔問題4.具體代碼實(shí)現(xiàn)三、完整代碼

一、什么是遞歸

方法調(diào)用自己的行為就是遞歸，遞歸必須要有終止條件，不然它會(huì)無限遞歸。

1.先來看一下一個(gè)遞歸的例子

此程序的Fact方法從大到小地一級(jí)一級(jí)地調(diào)用自己，直到參數(shù)為1，然后就開始返回一級(jí)一級(jí)的從小到大地累乘，然后就計(jì)算出number的階乘了。

staticintFact(intnum)

if(num=1)

returnnum;

else

returnnum*Fact(num-1);//調(diào)用自己，這一步是關(guān)鍵

2.遞歸的基本原理

以下是《C#圖解教程》對(duì)于遞歸的描述：

除了調(diào)用其他方法，方法也可以調(diào)用自身，這叫做遞歸。

調(diào)用方法自身的機(jī)制和調(diào)用其他方法其實(shí)是完全一樣的，都是為每一次方法調(diào)用把新的棧幀壓入棧頂。

我個(gè)人認(rèn)為遞歸就是把你要干的事情抽象一個(gè)成可以有限步數(shù)解決的方法，然后某一步解決不了就再調(diào)用這個(gè)方法，直到可以解決（結(jié)束遞歸的條件）這個(gè)問題就返回。

下面再看一個(gè)具體的例子來了解遞歸。

二、漢諾塔問題

1.漢諾塔的故事

漢諾塔由法國(guó)數(shù)學(xué)家愛德華盧卡斯創(chuàng)造，他曾經(jīng)編寫了一個(gè)印度的古老傳說：

在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

2.解決思路

回到編程，漢諾塔問題主要就是解決這個(gè)問題：

有A、B、C三根針，A上從小到大放著n層盤子，要從A上所有的盤子移動(dòng)到C盤上。

條件是一次只能移動(dòng)一個(gè)盤子，無論什么時(shí)候小盤子必須在大盤子上面。

漢諾塔問題求的是把盤子從A移到C總共的移動(dòng)次數(shù)是多少。

這是我之前追蹤4層漢諾塔運(yùn)行步驟畫的筆記

事實(shí)證明，沒多大幫助。

要想理解遞歸必須要放棄理解遞歸，放棄跟蹤全程步驟。

解決問題是計(jì)算機(jī)的事，你只要明確要把每一步怎么傳給計(jì)算機(jī)，遞歸兩層之間怎么交接，以及遞歸結(jié)束的條件就可以。

3.怎么解決漢諾塔問題

要解決漢諾塔問題就要用到遞歸思想，這里拿四層漢諾塔舉例子：

要完成四層漢諾塔，需要先把第四層盤子從A柱放到C柱，而要把第四層盤子放到C柱，就要把上面三層的盤子放到B柱：

那么要把這三層盤子移到B柱，那么就要先把第三層盤子移到B柱。

要把第三層盤子移到B柱，就要把第二層盤子移到C柱子。

要把第二層盤子移到C柱，就要把第一層盤子移到B柱子。

移動(dòng)一層漢諾塔到另一個(gè)柱不簡(jiǎn)單嗎？

這樣子把問題解決了，第四層盤子就可以移動(dòng)到C柱上了。

然后把剩下的三層漢諾塔也按照上面的思想，就可以移動(dòng)到C柱上了。

視頻鏈接

4.具體代碼實(shí)現(xiàn)

把大象裝進(jìn)冰箱需要多少步

把冰箱門打開把大象放進(jìn)去把冰箱門關(guān)上

把漢諾塔放到C柱需要多少步

把底層上面的盤子放到B柱把最底層盤子放到C柱把B柱那些盤子放到C柱

抽象一下就是：

把n-1層盤子從起點(diǎn)移到暫存區(qū)

然后把第n層盤子從起點(diǎn)移到終點(diǎn)

然后把n-1層盤子從暫存區(qū)移到終點(diǎn)

在這里可以創(chuàng)建一個(gè)Move方法來移動(dòng)盤子

staticvoidMove(intpile,charsrc,chartmp,chardst)

???????}

src就是源起點(diǎn)，tmp就是暫存區(qū)，dst就是終點(diǎn)

最外層的Move方法完成的是把pile層漢諾塔從src經(jīng)過tmp移動(dòng)到dst

現(xiàn)在要把大象裝進(jìn)冰箱了

在Move方法里面調(diào)用Move方法來解決之后的問題：

1.把冰箱門打開

Move(pile-1,src,dst,tmp);

這層Move完成的是把pile-1層漢諾塔從src經(jīng)過dst移動(dòng)到tmp

2.把大象塞進(jìn)去

Move(1,src,tmp,dst);

這層Move完成的是把最底層漢諾塔盤子從src直接移動(dòng)到dst

3.把門關(guān)上

Move(pile-1,tmp,src,dst);

這層Move完成的是把pile-1層漢諾塔從tmp經(jīng)過src移動(dòng)到dst

Move方法完整代碼：

staticvoidMove(intpile,charsrc,chartmp,chardst)

if(pile==1)//pile=1問題就好解決了

Console.WriteLine($"{src}--{dst}");

steps++;

return;

Move(pile-1,src,dst,tmp);

Move(1,src,tmp,dst);

Move(pile-1,tmp,src,dst);

每一層Move方法都有他自己的起點(diǎn)、暫存區(qū)和終點(diǎn)，我們只需要把上一層的起點(diǎn)、暫存區(qū)和終點(diǎn)傳過去就行了。

三、完整代碼

以下是完整代碼：

usingSystem;

???????namespaceHanoi

classProgram

publicconstintMAX_VALUE=30;//聲明最大值常量

publicstaticintsteps=0;

staticvoidMain(string[]args)

intlevels=0;

Console.Write($"輸入漢諾塔層數(shù)（1~{MAX_VALUE}）:");

levels=int.Parse(Console.ReadLine());

if(levels0levelsMAX_VALUE)

Move(levels,'A','B','C');

Console.WriteLine($"一共移動(dòng)了{(lán)Program.steps}次。");

Console.ReadKey();

return;

Console.WriteLine("輸入范圍錯(cuò)誤");

Console.ReadKey();

staticvoidMove(intpile,charsrc,chartmp,chardst)

if(pile==1)//pile=1問題就好解決了

Console.Writ