C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí):遞歸(3.1)

2019-11-17 05:04:11

字體：大中小

供稿：網(wǎng)友

　　遞歸法和回溯法

　　有人說，回溯實(shí)際上是遞歸的展開，但實(shí)際上。兩者的指導(dǎo)思想并不一致。

　　打個(gè)比方吧，遞歸法好比是一個(gè)軍隊(duì)要通過一個(gè)迷宮，到了第一個(gè)分岔口，有3條路，將軍命令3個(gè)小隊(duì)分別去探哪條路能到出口，3個(gè)小隊(duì)沿著3條路分別前進(jìn)，各自到達(dá)了路上的下一個(gè)分岔口，于是小隊(duì)長再分派人手各自去探路——只要人手足夠（對照而言，就是計(jì)算機(jī)的堆棧足夠），最后必將有人找到出口，從這人開始只要層層上報(bào)直屬領(lǐng)導(dǎo)，最后，將軍將得到一條通路。所不同的是，計(jì)算機(jī)的遞歸法是把這個(gè)并行過程串行化了。

　　而回溯法則是一個(gè)人走迷宮的思維模擬——他只能寄希望于自己的記憶力，假如他沒有辦法在分岔口留下標(biāo)記（電視里一演到什么迷宮尋寶，總有惡人去改好人的標(biāo)記）。

　　想到這里忽然有點(diǎn)明白為什么都喜歡遞歸了，他能夠滿足人心最底層的虛榮——難道你不覺得使用遞歸就象那個(gè)分派士兵的將軍嗎？想想漢諾塔的解法，也有這個(gè)傾向，“你們把上面的N－1個(gè)拿走，我就能把下面的挪過去，然后你們在把那N－1個(gè)搬過來”。笑談，切勿當(dāng)真。

　　這兩種方法的例程，我不給出了，網(wǎng)上很多。我只想對書上的遞歸解法發(fā)表點(diǎn)看法，因?yàn)闀系慕夥ㄓ型盗簱Q柱的嫌疑——迷宮的儲存不是用的二維數(shù)組，居然直接用岔路口之間的連接表示的——簡直是人為的降低了問題的難度。實(shí)際上，假如把迷宮抽象成（岔路口）點(diǎn)的連接，迷宮就變成了一個(gè)“圖”，求解入口到出口的路線，完全可以用圖的遍歷算法來解決，只要從入口DFS到出口就可以了；然而，從二維數(shù)組表示的迷宮轉(zhuǎn)化為圖是個(gè)很復(fù)雜的過程。并且這種轉(zhuǎn)化，實(shí)際上就是沒走迷宮之前就知道了迷宮的結(jié)構(gòu)，顯然是不合理的。對此，我只能說這是為了遞歸而遞歸，然后還自己給自己開綠燈。

　　但迷宮并不是只能用上面的方法來走，前提是，迷宮只要走出去就可以了，不需要找出一條可能上的最短路線——確實(shí)，迷宮只是前進(jìn)中的障礙，一旦走通了，沒人走第二遍。下面的方法是一位游戲玩家提出來的，既不需要遞歸，也不需要棧往返溯——玩游戲還是有收獲的。

　　另一種解法

　　請注重我在迷宮中用粗線描出的路線，實(shí)際上，在迷宮中，只要從入口始終沿著一邊的墻走，就一定能走到出口，那位玩家稱之為“靠一邊走”——假如你不把迷宮的通路看成一條線，而是一個(gè)有面積的圖形，很快你就知道為什么。編程實(shí)現(xiàn)起來也很簡單。

更多內(nèi)容請看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或　　下面的程序在TC2中編譯，不能在VC6中編譯——為了動態(tài)的表現(xiàn)人的移動情況，使用了gotoxy()，VC6是沒有這個(gè)函數(shù)的，而且堆砌迷宮的219號字符是不能在使用中文頁碼的操作系統(tǒng)的32位的console程序顯示出來的。

假如要在VC6中實(shí)現(xiàn)gotoxy()的功能還得用API，為了一個(gè)簡單的程序沒有必要，所以，就用TC2寫了，忽然換到C語言還有點(diǎn)不適應(yīng)。

　　#include

　　typedef strUCt hero {int x,y,face;} HERO;

　　void set_hero(HERO* h,int x,int y,int face){h->x=x;h->y=y;h->face=face;}

　　void go(HERO* h){if(h->face%2) h->x+=2-h->face;else h->y+=h->face-1;}
　　
　　void goleft(HERO* h){if(h->face%2) h->y+=h->face-2;else h->x+=h->face-1;}

　　void turnleft(HERO* h){h->face=(h->face+3)%4;}

　　void turnright(HERO* h){h->face=(h->face+1)%4;}

　　void PRint_hero(HERO* h, int b)

　　{

　　gotoxy(h->x + 1, h->y + 1);

　　if (b)

　　{

　　switch (h->face)

　　{

　　case 0: printf("%c", 24); break;

　　case 1: printf("%c", 16); break;

　　case 2: printf("%c", 25); break;

　　case 3: printf("%c", 27); break;

　　default: break;

　　}

　　　　}

　　else printf(" ");

　　}

　　int maze[10][10] =

　　{

更多內(nèi)容請看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或　　0, 0, 0, 1, 0, 0, 0, 1, 0, 0,

　　1, 0, 1, 1, 0, 1, 1, 1, 1, 0,

　　1, 0, 0, 0, 0, 0, 0, 0, 0, 0,

　　0, 0, 1, 0, 1, 1, 0, 1, 1, 1,

　　0, 0, 1, 0, 1, 1, 0, 0, 0, 1,

　　1, 0, 1, 0, 1, 1, 0, 1, 0, 1,

　　0, 0, 1, 0, 1, 1, 0, 1, 0, 1,

　　0, 1, 1, 0, 0, 0, 0, 1, 0, 1,

　　0, 0, 0, 0, 1, 0, 1, 1, 0, 1,

　　0, 1, 1, 1, 1, 0, 0, 0, 0, 0

　　};

　　void print_maze()

　　{

　　int i, j;

　　for (i = 0; i < 10; i++)

　　{

　　　　for (j = 0; j < 10; j++)

　　{

　　　　if (maze[i][j]) printf("%c", 219);

　　　　　　else printf(" ");

　　}

　　printf("/n");

　　}

　　}

　　int gomaze(HERO* h)

　　{

　　HERO t = *h; int i;

　　for (i = 0; i < 2; t = *h)

　　{

　　print_hero(h, 1); sleep(1); go(&t);

　　if (t.x >= 0 && t.x < 10 && t.y >= 0 && t.y < 10 && !maze[t.y][t.x])
　　{

　　print_hero(h, 0); go(h);/*前方可走則向前走*/

　　if (h->x == 9 && h->y == 9) return 1; goleft(&t);

　　if (h->x == 0 && h->y == 0) i++;

　　if (t.x >= 0 && t.x < 10 && t.y >= 0 && t.y < 10 && !maze[t.y][t.x]) turnleft(h);/*左方無墻向左轉(zhuǎn)*/

　　}
　　else turnright(h);/*前方不可走向右轉(zhuǎn)*/

　　}

　　return 0;

　　}

　　main()

　　{

　　HERO Tom;/*有個(gè)英雄叫Tom*/

　　set_hero(&Tom, 0, 0, 0);/*放在(0,0)面朝北*/

　　clrscr();

　　print_maze();

　　gomaze(&Tom);/*Tom走迷宮*/

　　}

更多內(nèi)容請看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或　　總結(jié)

　　書上講的基本上就這些了，要是細(xì)說起來，幾天幾夜也說不完。前面我并沒有講如何寫遞歸算法，實(shí)際上給出的都是非遞歸的方法，我也覺得有點(diǎn)文不對題。

我的目的是使大家明白，能寫出什么算法，主要看你解決問題的指導(dǎo)思想，換而言之，就是對問題的熟悉程度。所以初學(xué)者現(xiàn)在就去追求“漂亮”的遞歸算法，是不現(xiàn)實(shí)的，結(jié)果往往就是削足適履，搞的一團(tuán)糟——有位仁兄寫了個(gè)騎馬游世界的“遞歸”程序，在我機(jī)器上10分鐘沒反映。其實(shí)優(yōu)秀的遞歸算法是在對問題有了清楚的熟悉后才會得出的。

　　最后說說用匯編語言寫遞歸函數(shù)。我的匯編水平并不高，不過我想說的是用匯編寫遞歸函數(shù)，絕對不像《匯編與c解決遞歸問題之比較》http://www.csdn.net/develop/article/17/17597.shtm那篇文章說的，實(shí)際上比高級語言并不復(fù)雜，甚至在masm32v7中，和高級語言一樣，因?yàn)槟抢锩嬗幸痪浜芟蟠鷧⒑瘮?shù)調(diào)用的INVOKE eXPression [，arguments]。那位作者顯然連教科書都沒看全，因?yàn)樵谖覀兊闹v8086匯編語言的書上就有一個(gè)階乘的遞歸函數(shù)例程，假如他看過，就不會有那個(gè)結(jié)論了。

更多內(nèi)容請看C/C++技術(shù)專題數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)教程專題，或

上一篇：C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí):遞歸(2.2)

下一篇：C++數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí):二叉樹(1)