您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“C#怎么利用遞歸算法解決漢諾塔問(wèn)題”的有關(guān)知識(shí),在實(shí)際案例的操作過(guò)程中,不少人都會(huì)遇到這樣的困境,接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
方法調(diào)用自己的行為就是遞歸,遞歸必須要有終止條件,不然它會(huì)無(wú)限遞歸。
1.先來(lái)看一下一個(gè)遞歸的例子
此程序的Fact方法從大到小地一級(jí)一級(jí)地調(diào)用自己,直到參數(shù)為1,然后就開(kāi)始返回一級(jí)一級(jí)的從小到大地累乘,然后就計(jì)算出number的階乘了。
static int Fact(int num) { if (num <= 1) { return num; } else { return num * 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è)問(wèn)題就返回。
下面再看一個(gè)具體的例子來(lái)了解遞歸。
漢諾塔由法國(guó)數(shù)學(xué)家愛(ài)德華·盧卡斯創(chuàng)造,他曾經(jīng)編寫(xiě)了一個(gè)印度的古老傳說(shuō):
在世界中心貝拿勒斯(在印度北部)的圣廟里,一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候,在其中一根針上從下到上地穿好了由大到小的64片金片,這就是所謂的漢諾塔。不論白天黑夜,總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片:一次只移動(dòng)一片,不管在哪根針上,小片必須在大片上面。僧侶們預(yù)言,當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí),世界就將在一聲霹靂中消滅,而梵塔、廟宇和眾生也都將同歸于盡。
回到編程,漢諾塔問(wèn)題主要就是解決這個(gè)問(wèn)題:
有A、B、C三根針,A上從小到大放著n層盤(pán)子,要從A上所有的盤(pán)子移動(dòng)到C盤(pán)上。
條件是一次只能移動(dòng)一個(gè)盤(pán)子,無(wú)論什么時(shí)候小盤(pán)子必須在大盤(pán)子上面。
漢諾塔問(wèn)題求的是把盤(pán)子從A移到C總共的移動(dòng)次數(shù)是多少。
這是我之前追蹤4層漢諾塔運(yùn)行步驟畫(huà)的筆記
事實(shí)證明,沒(méi)多大幫助。
要想理解遞歸必須要放棄理解遞歸,放棄跟蹤全程步驟。
解決問(wèn)題是計(jì)算機(jī)的事,你只要明確要把每一步怎么傳給計(jì)算機(jī),遞歸兩層之間怎么交接,以及遞歸結(jié)束的條件就可以。
要解決漢諾塔問(wèn)題就要用到遞歸思想,這里拿四層漢諾塔舉例子:
要完成四層漢諾塔,需要先把第四層盤(pán)子從A柱放到C柱,而要把第四層盤(pán)子放到C柱,就要把上面三層的盤(pán)子放到B柱:
那么要把這三層盤(pán)子移到B柱,那么就要先把第三層盤(pán)子移到B柱。
要把第三層盤(pán)子移到B柱,就要把第二層盤(pán)子移到C柱子。
要把第二層盤(pán)子移到C柱,就要把第一層盤(pán)子移到B柱子。
移動(dòng)一層漢諾塔到另一個(gè)柱不簡(jiǎn)單嗎?
這樣子把問(wèn)題解決了,第四層盤(pán)子就可以移動(dòng)到C柱上了。
然后把剩下的三層漢諾塔也按照上面的思想,就可以移動(dòng)到C柱上了。
視頻鏈接
把大象裝進(jìn)冰箱需要多少步
把冰箱門(mén)打開(kāi)
把大象放進(jìn)去
把冰箱門(mén)關(guān)上
把漢諾塔放到C柱需要多少步
把底層上面的盤(pán)子放到B柱
把最底層盤(pán)子放到C柱
把B柱那些盤(pán)子放到C柱
抽象一下就是:
把n-1層盤(pán)子從起點(diǎn)移到暫存區(qū)
然后把第n層盤(pán)子從起點(diǎn)移到終點(diǎn)
然后把n-1層盤(pán)子從暫存區(qū)移到終點(diǎn)
在這里可以創(chuàng)建一個(gè)Move方法來(lái)移動(dòng)盤(pán)子
static void Move(int pile, char src, char tmp, char dst) { }
src就是源起點(diǎn),tmp就是暫存區(qū),dst就是終點(diǎn)
最外層的Move方法完成的是把pile層漢諾塔從src經(jīng)過(guò)tmp移動(dòng)到dst
現(xiàn)在要把大象裝進(jìn)冰箱了
在Move方法里面調(diào)用Move方法來(lái)解決之后的問(wèn)題:
1. 把冰箱門(mén)打開(kāi)
Move(pile - 1, src, dst, tmp);
這層Move完成的是把pile-1層漢諾塔從src經(jīng)過(guò)dst移動(dòng)到tmp
2.把大象塞進(jìn)去
Move(1, src, tmp, dst);
這層Move完成的是把最底層漢諾塔盤(pán)子從src直接移動(dòng)到dst
3.把門(mén)關(guān)上
Move(pile - 1, tmp, src, dst);
這層Move完成的是把pile-1層漢諾塔從tmp經(jīng)過(guò)src移動(dòng)到dst
Move方法完整代碼:
static void Move(int pile, char src, char tmp, char dst) { if (pile == 1)//pile=1問(wèn)題就好解決了 { 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)傳過(guò)去就行了。
以下是完整代碼:
using System; namespace Hanoi { class Program { public const int MAX_VALUE = 30;//聲明最大值常量 public static int steps = 0; static void Main(string[] args) { int levels = 0; Console.Write($"輸入漢諾塔層數(shù)(1~{MAX_VALUE}): "); levels = int.Parse(Console.ReadLine()); if (levels > 0 && levels < MAX_VALUE) { Move(levels, 'A', 'B', 'C'); Console.WriteLine($"一共移動(dòng)了{(lán)Program.steps}次。"); Console.ReadKey(); return; } Console.WriteLine("輸入范圍錯(cuò)誤"); Console.ReadKey(); } static void Move(int pile, char src, char tmp, char dst) { if (pile == 1)//pile=1問(wèn)題就好解決了 { Console.WriteLine($"{src} --> {dst}"); steps++; return; } Move(pile - 1, src, dst, tmp); Move(1, src, tmp, dst); Move(pile - 1, tmp, src, dst); } } }
運(yùn)行結(jié)果如下:
“C#怎么利用遞歸算法解決漢諾塔問(wèn)題”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。