一、什么是遞歸

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

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

此程序的Fact方法從大到小地一級(jí)一級(jí)地調(diào)用自己，直到參數(shù)為1，然后就開始返回一級(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è)問題就返回。

下面再看一個(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)盤子

static void Move(int pile, char src, char tmp, char dst)
{
???????}

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方法完整代碼：

static void Move(int pile, char src, char tmp, char dst)
        {
            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)傳過去就行了。

三、完整代碼

以下是完整代碼：

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問題就好解決了
            {
                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é)果如下：

到此這篇關(guān)于C#利用遞歸算法解決漢諾塔問題的文章就介紹到這了,更多相關(guān)C#漢諾塔遞歸算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論