


全文預(yù)覽已結(jié)束
下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
_遞歸馮文科一、遞歸的基本概念。一個(gè)函數(shù)、概念或數(shù)學(xué)結(jié)構(gòu),如果在其定義或說明內(nèi)部直接或間接地出現(xiàn)對(duì)其本身的引用,或者是為了描述問題的某一狀態(tài),必須要用至它的上一狀態(tài),而描述上一狀態(tài),又必須用到它的上一狀態(tài)這種用自己來定義自己的方法,稱之為遞歸或遞歸定義。在程序設(shè)計(jì)中,函數(shù)直接或間接調(diào)用自己,就被稱為遞歸調(diào)用。二、遞歸的最簡(jiǎn)單應(yīng)用:通過各項(xiàng)關(guān)系及初值求數(shù)列的某一項(xiàng)。在數(shù)學(xué)中,有這樣一種數(shù)列,很難求出它的通項(xiàng)公式,但數(shù)列中各項(xiàng)間關(guān)系卻很簡(jiǎn)單,于是人們想出另一種辦法來描述這種數(shù)列:通過初值及與前面臨近幾項(xiàng)之間的關(guān)系。要使用這樣的描述方式,至少要提供兩個(gè)信息:一是最前面幾項(xiàng)的數(shù)值,一是數(shù)列間各項(xiàng)的關(guān)系。比如階乘數(shù)列1、2、6、24、120、720如果用上面的方式來描述它,應(yīng)該是:如果需要寫一個(gè)函數(shù)來求的值,那么可以很容易地寫成這樣:int f(int n)if(n=1)return 1; return n*f(n-1);這就是遞歸函數(shù)的最簡(jiǎn)單形式,從中可以明顯看出遞歸函數(shù)都有的一個(gè)特點(diǎn):先處理一些特殊情況這也是遞歸函數(shù)的第一個(gè)出口,再處理遞歸關(guān)系這形成遞歸函數(shù)的第二個(gè)出口。遞歸函數(shù)的執(zhí)行過程總是先通過遞歸關(guān)系不斷地縮小問題的規(guī)模,直到簡(jiǎn)單到可以作為特殊情況處理而得出直接的結(jié)果,再通過遞歸關(guān)系逐層返回到原來的數(shù)據(jù)規(guī)模,最終得出問題的解。以上面求階乘數(shù)列的函數(shù)為例。如在求時(shí),由于3不是特殊值,因此需要計(jì)算,但是對(duì)它自己的調(diào)用,于是再計(jì)算,2也不是特殊值,需要計(jì)算,需要知道的值,再計(jì)算,1是特殊值,于是直接得出,返回上一步,得,再返回上一步,得,從而得最終解。用圖解來說明,就是的執(zhí)行過程(特殊值判斷:),繼續(xù)向下。(遞歸關(guān)系處理:)求,需要先計(jì)算,調(diào)用,且本身掛起得到,由正常出口返回的執(zhí)行過程(特殊值判斷:),繼續(xù)向下。(遞歸關(guān)系處理:)求,需要先計(jì)算,調(diào)用,且本身掛起得到,由正常出口返回的執(zhí)行過程(特殊值判斷:),由特殊情況出口直接返回1。下面再看一個(gè)稍復(fù)雜點(diǎn)的例子?!纠?】數(shù)列的前幾項(xiàng)為1、輸入,編程求的精確分?jǐn)?shù)解。分析:這個(gè)題目較易,發(fā)現(xiàn),其它情況下有。如要求實(shí)數(shù)解的話,這基本已經(jīng)可以寫出遞歸函數(shù)了。但由于題目要求精確的分?jǐn)?shù)解,還需做一些調(diào)整。設(shè),則由遞歸關(guān)系,有,再約分化簡(jiǎn),即得。但發(fā)現(xiàn)一個(gè)問題:求出時(shí),需要返回兩個(gè)整數(shù):分子與分母,而通常的函數(shù)只能返回一個(gè)整數(shù)。這個(gè)問題一般有兩類解決辦法,一種是讓求值函數(shù)返回一個(gè)結(jié)構(gòu)體變量,這樣就可以返回兩個(gè)變量了(其實(shí)還可以不只兩個(gè)呢);另一種是在求值函數(shù)的參數(shù)表中加入兩個(gè)指針變量或引用變量,通過參數(shù)給帶回?cái)?shù)值。但由于后一種做法會(huì)使程序結(jié)構(gòu)不清晰返回值是由參數(shù)表得到的,因此我們使用前一種方法。另外,在通過得出后,就已經(jīng)是最簡(jiǎn)分?jǐn)?shù)了,無須化簡(jiǎn)。證明如下:若是最簡(jiǎn)分?jǐn)?shù),即說明的最大公約數(shù)為1,即對(duì)任何,都有與不全為0,不防記、,則有只要與不全為0,且,就有與不全為0。因此對(duì)任何的,有與不全為0。而對(duì)于的情況而言,記,則有由于,因此同樣有與不全為0。所以對(duì)任意,都有與不全為0,因此它們的最大公約數(shù)為1,即是最簡(jiǎn)分?jǐn)?shù)。雖然這是個(gè)要求(即)是最簡(jiǎn)分?jǐn)?shù)的結(jié)論,但由于數(shù)列第二項(xiàng)為,是最簡(jiǎn)分?jǐn)?shù),因此可以證明第三項(xiàng)也是最簡(jiǎn)分?jǐn)?shù),同時(shí)也證明對(duì)所有的,求出的就是最簡(jiǎn)分?jǐn)?shù),無須化簡(jiǎn)。具體代碼如下:/ Exam1.cpp#include using namespace std;struct FS unsigned long long q, p;FS f(int n) FS r; if(n=1) r.q=1; r.p=1; return r; r=f(n-1); r.p=r.p+r.q; r.q=r.p-r.q; return r;int main() FS r; int n; cinn; r=f(n); coutr.q/r.pendl; system(pause); return 0;三、遞歸的精髓:只考慮當(dāng)前一步,剩下的讓下一步去做吧。對(duì)大多數(shù)問題而言,當(dāng)它的規(guī)模縮小至“特殊情況”時(shí),都可以非常輕易地得出問題的解,因此我們不過多地討論“特殊情況”,只詳細(xì)地討論遞歸關(guān)系的確定。尋找遞歸關(guān)系,最低標(biāo)準(zhǔn)是它能使問題的規(guī)模變小,且變小后的問題與原問題在本質(zhì)上是一樣的。當(dāng)找到遞歸關(guān)系后,我們的遞歸函數(shù)只須處理特殊情況與遞歸關(guān)系,不需要處理其它的信息至于下一步的事情,就讓下一步去做吧。另一個(gè)需要考慮的事情就是遞歸函數(shù)的參數(shù)表,首先,在通常情況下,參數(shù)表都要使用變量參數(shù),且遞歸函數(shù)中盡量使用局部變量這會(huì)減少很多不必要的麻煩;其次,參數(shù)表中,大多都有一個(gè)表示當(dāng)前在執(zhí)行第幾步的參數(shù)?!纠?】下圖是一個(gè)有向圖,輸入,打印的所有路徑。1357902468分析:仔細(xì)研究這個(gè)圖的特點(diǎn),發(fā)現(xiàn)以下規(guī)律:對(duì)任何結(jié)點(diǎn),都可以走到和,當(dāng)然如果它們不超過9的話。由于要打印路徑,因此需要保存查找過程中的部分路徑信息??梢宰鲆粋€(gè)全局?jǐn)?shù)組path來存儲(chǔ)這個(gè)信息,由于結(jié)點(diǎn)0沒有來路,且是所有路徑的起點(diǎn),因此記path0=0,遞歸函數(shù)負(fù)責(zé)填寫之后的路徑結(jié)點(diǎn)。我們這樣設(shè)計(jì)遞歸函數(shù):首先,這個(gè)遞歸函數(shù)的參數(shù)表中至少需要一個(gè)參數(shù)i,它的意義是表示現(xiàn)在在填路徑中的第幾個(gè)結(jié)點(diǎn),而pathi可以填的數(shù),要么是上一個(gè)結(jié)點(diǎn)加1,要么是上一個(gè)結(jié)點(diǎn)加2,即pathi=pathi-1+1或pathi=pathi-1+2;其次,特殊情況的討論:我們要找的是終止到的路徑,因此若出現(xiàn)pathi-1=的情況,就說明已經(jīng)找到路徑,無須將當(dāng)前層再填入結(jié)點(diǎn),可以將path中的信息輸出并結(jié)束函數(shù)了這是遞歸函數(shù)的特殊情況出口;第三、遞歸關(guān)系的處理:若還沒到達(dá)結(jié)點(diǎn),則填寫本結(jié)點(diǎn)pathi,上文已說明,pathi=pathi-1+1或pathi=pathi-1+2,當(dāng)然如果它們都不過9的話。將結(jié)點(diǎn)填好后,說明路徑向下走了一步,距離結(jié)點(diǎn)更近了一步,問題規(guī)模已經(jīng)變小。不要處理其它東西,直接遞歸,通過遞歸調(diào)用去填寫i+1結(jié)點(diǎn)就可以了。這里有處和【例1】不相同的地方,即pathi是有兩種可能可選的,我們的處理這這樣的,先令pathi=pathi-1+1,然后遞歸調(diào)用,填寫i+1結(jié)點(diǎn),當(dāng)這個(gè)調(diào)用返回時(shí),說明所有pathi為pathi-1+1的路徑都已經(jīng)討論完成了,再令pathi=pathi-1+2,再遞歸,當(dāng)它返回時(shí),整個(gè)函數(shù)執(zhí)行完畢,形成正常的執(zhí)行完成時(shí)的出口。具體代碼如下:/ Exam2.cpp#include using namespace std;#define MAX 9int pathMAX, N;int write(int i) int j; for(j=0;ji;j+) coutpathj; coutpathiendl;void f(int i) if(pathi-1=N) write(i-1); return; if(pathi-1+1=N) pathi=pathi-1+1; f(i+1); if(pathi-1+2N; path0=0; f(1); system(pause); return 0;【例3】我的畫筆。Windows中的畫筆從Windows3.x時(shí)代開始就已經(jīng)有了,雖然功能與Photoshop不能相比,但它小巧而迅速,一般的簡(jiǎn)單功能還是很方便的。畫筆中的填色工具是油漆桶,選定它,再指定一個(gè)顏色,在圖片中一點(diǎn),所有與這個(gè)點(diǎn)顏色相同且相連的象素就都被填充了。如下圖示:畫筆的油漆桶工具填充的是一個(gè)叫“四連通”的區(qū)域,即它只從上、下、左、右四個(gè)方向向外擴(kuò)展。請(qǐng)編寫程序,模擬油漆通工具。輸入文件:Exam3In.txt中有10行,每行是一個(gè)10字符的字符串,表示一個(gè)10*10的圖象,不同的字符表示不同的顏色;之后的一行有兩個(gè)用空格分開的整數(shù),表示油漆桶點(diǎn)中的位置,再后面一行是一個(gè)字符,表示油漆桶的填充顏色。輸出文件:Exam3Out.txt,輸出10行,每行10個(gè)字符的字符串,表示填充后的圖象。分析:本題給了一個(gè)點(diǎn)的位置,查找所有與它“四連通”的點(diǎn)就成為本題的核心問題。我們的算法是這樣的:先從這個(gè)起點(diǎn)出發(fā),沿四個(gè)方向展開,看這“直接相連”的四個(gè)點(diǎn)是否可以填充,若有可以的,則再以這個(gè)點(diǎn)為中心,再向四個(gè)方向展開直到所有可能展開的點(diǎn)都不能再展開了為止。遞歸函數(shù)這樣設(shè)計(jì):首先它的參數(shù)表需要兩個(gè)參數(shù),表示本次從哪個(gè)位置點(diǎn)展開;其次,依次討論它四個(gè)方向上相鄰的點(diǎn)是否可填充與起點(diǎn)顏色相同,如果可以,則填充,并以此點(diǎn)為中心,遞歸調(diào)用。代碼如下:/ Exam3.cpp#include using namespace std;#define N 10ifstream fin(Exam3In.txt);ofstream fout(Exam3Out.txt);char picNN+1, c, p;int col, row;void fill(int i, int j) if(i-1=0 & pici-1j=p) pici-1j=c; fill(i-1, j); if(i+1=0 & picij-1=p) picij-1=c; fill(i, j-1); if(j+1N & picij+1=p) picij+1=c; fill(i, j+1); int main() int i; for(i=0;ipici; finrowcol; finc; p=picrowcol; picrowcol=c; fill(row, col); for(i=0;iN;i+) foutpiciendl; return 0;本題中的遞歸函數(shù)fill似乎與常規(guī)的遞歸函數(shù)比較起來缺少了處理特殊情況的部分,其實(shí)不然,它的特殊情況處理已經(jīng)被融合到遞歸關(guān)系的處理當(dāng)中了,正常與非正常的出口合并到一起。特殊情況就是:當(dāng)向四個(gè)方向都無法展開時(shí),程序直接退出。這個(gè)程序的fill函數(shù)運(yùn)用的算法就是“種子填充算法”的遞歸寫法。它另有動(dòng)態(tài)規(guī)劃的寫法當(dāng)然比這個(gè)要快得多,大家可以想一想如何實(shí)現(xiàn)。四、遞歸函數(shù)的必然用法:處理遞歸定義的數(shù)據(jù)結(jié)構(gòu)。一些常用的數(shù)據(jù)結(jié)構(gòu)本身就是遞歸定義的,寫一個(gè)遞歸的函數(shù)來處理它,當(dāng)然是再正常不過的事情,就比如說二叉樹、廣義表【例4】二叉樹的操作。用字符串的形式給定一個(gè)完全二叉樹,保存在輸入文件Exam4In.txt中,編寫程序輸出其后序遍歷的結(jié)果至輸出文件Exam4Out.txt中。分析:本題的程序是簡(jiǎn)單的,唯一要注意的是:C+的數(shù)組從下標(biāo)0開始,因此對(duì)于結(jié)點(diǎn),它的左孩子編號(hào)應(yīng)該是,右孩子編號(hào)應(yīng)該是。其它的地方?jīng)]什么難度。代碼如下:/ Exam4.cpp#include using namespace std;#define M 100ifstream fin(Exam4In.txt);ofstream fout(Exam4Out.txt);char treeM;int L;void run(int i) if(2*i+1L) run(2*i+1); if(2*(i+1)L) run(2*(i+1); fouttree; L=strlen(tree); run(0); return 0;【例5】以字符串形式給出一棵完全二叉樹的先序遍歷與中序遍歷序列,編程輸出用字符串形式表示的完全二叉樹的結(jié)構(gòu)。分析:先序遍歷的首結(jié)點(diǎn)一定是整棵樹的根,因此可以直接標(biāo)在0處。在中序遍歷序列中,它左邊的結(jié)點(diǎn)構(gòu)成左子樹,右邊的結(jié)點(diǎn)構(gòu)成右子樹,從而可以知道,左子樹與右子樹的結(jié)點(diǎn)個(gè)數(shù),進(jìn)而得到及左子樹與右子樹的先序遍歷與中序遍歷序列,遞歸查找所有子樹的根即可。為了得到整棵樹的結(jié)構(gòu),設(shè)置全局?jǐn)?shù)組tree來存儲(chǔ),全局?jǐn)?shù)組s的意義是:si存儲(chǔ)整數(shù)表示第i層結(jié)點(diǎn)的起始下標(biāo)。代碼如下:/ Exam5.cpp#include using namespace std;#define M 100ifstream fin(Exam5In.txt);ofstream fout(Exam5Out.txt);char preM, midM, treeM;int L, sM;void build(int layer, int ps, int pe, int ms, int me) treeslayer=preps; slayer+; if(ps=pe) return; int i; i=ms; while(midi!=preps) i+; build(layer+1, ps+1, ps+i-ms, ms, i-1); build(layer+1, ps+i-ms+1, pe, i+1, me);int main() finpremid; L=strlen(pre); s0=0; int i, j; i=1; j=2; while(siL) si=j-1; j=j*2; i+; build(0, 0, L-1, 0, L-1); treeL=0; fouttree; return 0;五、遞歸與回溯法。遞歸的另一個(gè)常用的地方是實(shí)現(xiàn)回溯法。所謂回溯法,一般就是指先將問題分成幾步,在每一步時(shí)嘗試所有的可能,直到達(dá)到最終要求,或最后一步將所有可能嘗試完成后,再回到上一步,使上一步嘗試下一種可能,并繼續(xù)的作法。由于回溯的“步驟性”明顯,因此用遞歸實(shí)現(xiàn)回溯是相當(dāng)方便的事??聪旅娴囊粋€(gè)例題:【例6】n皇后問題。輸入整數(shù)n,打印n皇后問題的所有解及解的總數(shù)。代碼如下:/ Exam6.cpp#include using namespace std;#define MAX 100int n, qMAX, c;bool markMAX;void write() int i; char tMAX; memset(t, ., MAX*sizeof(char); tn=0; for(i=0;in;i+) tqi=Q; couttendl; tqi=.; coutendl;bool test(int i, int k) int j; j=0; while(jk & abs(j-k)!=abs(qj-i) j+; if(j=k & marki=false) return true; else return false;void search(int k) if(k=n) write(); c+; return; int i; for(i=0;in; memset(mark, 0, MAX*sizeof(bool); c=0; search(0); coutcendl; system(pause); return 0;六、練習(xí)【練習(xí)】為給定的表達(dá)式建立表達(dá)式樹,并求值。給定的表達(dá)式中,所有數(shù)字都是1位正整數(shù),出現(xiàn)的符號(hào)可能為、*、/、(、)。分析:這是一個(gè)與一般數(shù)據(jù)結(jié)構(gòu)書上講的用棧計(jì)算的方法本質(zhì)不同的方法。在詳細(xì)說明這個(gè)算法之前,需要首先明確這個(gè)算法用到的概念1、單元:一個(gè)單元可能是用括號(hào)括起來的一個(gè)表達(dá)式,或是一個(gè)整數(shù);2、項(xiàng):一個(gè)項(xiàng)是指由*與/連接起來的若干單元;3、表達(dá)式:一個(gè)表達(dá)式是指由或連接起來的若干項(xiàng)。要建立表達(dá)式樹,需要三個(gè)函數(shù)互相調(diào)用的函數(shù):一個(gè)是getunit,用于建立一個(gè)單元;一個(gè)是getexpr,用于建立一個(gè)項(xiàng),另一個(gè)就是build,用于建立一個(gè)表達(dá)式。getunit函數(shù)較易,如果字符串首字母是(的話,那么從它后面的字符開始用build建立一個(gè)表達(dá)式,這個(gè)表達(dá)式就是一個(gè)單元;否則,就處理一個(gè)整數(shù);getexpr函數(shù)是建立在getunit之上的,它先用getunit建立一個(gè)單元,然后不停地考察之后地連接符號(hào)是不是*或/,若是,則不停地重復(fù)讀連接符、建立另一個(gè)單元、建立連接的操作,直到連接符號(hào)不是*或/為止。build函數(shù)是用于最終建立表達(dá)式的,它先用getexpr建立一個(gè)項(xiàng),再用符號(hào)將剩余的各項(xiàng)連接成二叉樹。代碼如下:/ Exer.cpp#include using namespace std;struct NODE int n; char c; NODE *left, *right; NODE() left=NULL; right=NULL; ;char s100;int cur;NODE *tree;void clear(NODE *root) if(root=NULL) return; clear(root-left); clear(root-right); delete root;void cal(NODE *root) if(root-left!=NULL) cal(root-left); cal(root-right); switch(root-c) case +: root-n=root-left-n+root-right-n; break; case -: root-n=root-left-n-root-right-n; break; case *: root-n=root-left-n*root-right-n; break; case /: root-n=root-left-n/root-right-n; NODE *build();NODE *getunit() NODE *a; if(scur=() cur+; a=build(); else a=new NODE; a-n=scur-0; cur+; return a;NODE *getexpr() NODE *a, *b, *c; a=getunit(); while(scur=* | scur=/) b=new NODE; b-c=scur; cur+; c=getunit(); b-left=a; b-right=c; a=b; return a;NODE *build() NODE *a, *b, *c; a=getexpr(); while(scur!=0 & scur!=) b=new NODE; b-c=scur; cur+; c=getexpr(); b-left=a; b-right=c; a=b; if(scur=) cur+; return a;int main() cins; cur=0; tree=build(); cal(tree); coutn0又例如,F(xiàn)ibonacci(斐波那契)數(shù)列可遞歸定義為 0 若n=0Fib(n) = 1 若n=1 Fib(n-1)+Fib(n-2) 若n1 據(jù)此可以寫出實(shí)現(xiàn)求n 的階乘和求Fibonacci數(shù)列中第n項(xiàng)的遞歸算法,如算法21和算法22所示。long int fact(int n) /求非負(fù)整數(shù)n的階乘if(!n) return 1; /0!=1else return n*fact(n-1); /n!=n*(n-1)!/fact算法21 求階乘的遞歸算法long int fib(int n) /求斐波那契數(shù)列中的第n個(gè)數(shù)if(n1,f(n)=f(n-1)+f(n-2)/fib算法22 求斐波那契數(shù)的遞歸算法 一般地說,每一個(gè)遞歸函數(shù)的定義都包含兩個(gè)部分。(1) 遞歸基礎(chǔ) 對(duì)無需遞歸的規(guī)模最小的問題直接進(jìn)行處理。(2) 遞歸步驟 將一般情況的問題簡(jiǎn)化成一個(gè)或多個(gè)規(guī)模較小的同性質(zhì)的問題,遞歸地調(diào)用同樣的方法求解這些問題,使這些問題最終簡(jiǎn)化成基礎(chǔ)問題。 算法21的遞歸基礎(chǔ)是n=0時(shí),直接返回1(0!=1)。一般情況下,將fact(n)簡(jiǎn)化成規(guī)模較小的問題fact(n-1),求出fact(n-1)后再與n相乘即求得了fact(n) 。 算法22的遞歸基礎(chǔ)是n=01. if(n0) /若n=0,則不需做任何動(dòng)作,僅當(dāng)n0時(shí)2. hanoi(n-1,x,z,y); /先將n-1個(gè)盤從x柱經(jīng)z柱搬到y(tǒng)柱 coutMove Disk n from x to zendl;/將第n個(gè)盤從x搬到z4. hanoi(n-1,y,x,z); /再將y柱上的n-1個(gè)盤經(jīng)x柱搬到z柱5. /if6./hanoi算法23 求解漢諾塔問題的遞歸算法3 背包問題 設(shè)有一個(gè)背包可以放入總重量為S的物品,現(xiàn)有n件物品,重量分別為w1 ,w2,wn 。問能否從這n件物品中選擇若干件放入背包,使得放入的物品總重量恰好為S。如果存在一組符合上述要求的物品,則稱此背包問題有解(用TRUE表示問題有解),否則稱此問題無解(用FALSE表示無解)。假如我們定義一個(gè)維數(shù)組W存儲(chǔ)各物品的重量,用布爾函數(shù)knap(S,n)求解背包問題。其參數(shù)S表示背包還留有的容量,n為可供選擇的物品個(gè)數(shù)。顯然,如果S=0,背包問題總有解,即knap(0,n)為TRUE,因?yàn)椴贿x擇任何物品放入背包即可。當(dāng)S0但n0且n1,我們要求解背包問題有兩種途徑:一種是選擇第n件物品放入背包,于是背包剩余的容量為SWn(Wn中存儲(chǔ)wn ,即第n件物品的重量),可選擇的物品是前n-1件。如果knapn(s-wn,n-1)有解,則knap(S,n)也有解,否則knap(S,n)無解,說明選擇第n件物品是錯(cuò)的。另一種是不選第n件物品,此時(shí)背包問題簡(jiǎn)化為knap(S,n-1),如果它有解,則knap(S,n)也有解,如果它無解,則knap(S,n)也無解,從而背包問題可以遞歸地定義如下: TRUE 若S=0 knap(,n) = FALSE 若0且n0且n1上述遞歸定義是確定的,因?yàn)槊看芜f歸,n總減少1,S也可能減小Wn,所以遞歸若干次之后,遞歸基礎(chǔ)的條件(S0或n1)必定成立,所以遞歸過程在有限步之后總能結(jié)束。 例5 用遞歸方法求解背包問題。根據(jù)knap(S,n)的定義,容易寫出背包問題的遞歸算法,如算法24所示。const int MAXN=11; /假設(shè)最多只有十件物品int wMAXN=0,3,5,6,3,7,1,2,4,9,8; /假設(shè)物品的重量已存在w1.w10中int knap(int s,int n) / s為背包的容量,n為可供選擇物品的最大編號(hào)if(s=0) return TRUE; /若背包已裝滿,則有解if(s0)&(n1)return FALSE;/若背包容量為負(fù)數(shù)或已無物品可選,則必?zé)o解 if(knap(s-wn,n-1) /先試探將第n個(gè)物品裝入背包中,若因此有解,則原題有解 coutwn0)|!StackEmpty(s)/若尚未找到解且有物品可選或棧非空 if (n0) /如果還有物品可選 if (t=wn) /而且背包還能放得下 t-=wn; /就將物品n放入背包,t因此減少wn if (!StackFull(s) /若棧未滿 Push(s,n); /將n入棧,即將物品n放入背包 -n; /因此可選物品的編號(hào)小1 if (t=0) found=1; /若背包已滿,則求得一解 else exit(ERROR); /若棧已滿,則出錯(cuò) else -n; /若背包放不下物品n,則嘗試選擇物品n-1 /if(n0)/whileif (found) /如果找到一解,就將所選物品的重量輸出 for (i=s.top; i0; -i) Pop(s,e); coutwe0;-i) /first中存儲(chǔ)的數(shù)逐漸向第n個(gè)斐波那契數(shù)靠近 temp=first; first=second; second+=temp;/first移向下一個(gè)斐波那契數(shù)return first; /for語句結(jié)束時(shí),first已是第n個(gè)斐波那契數(shù)/Fibo算法28 求斐波那契數(shù)的非遞歸算法 顯然,也可以用圖10來解釋Fibo的執(zhí)行過程。由于Fibo消除了遞歸,省掉了n次函數(shù)調(diào)用的開銷,所以它的效率更高。 尾遞歸函數(shù)是一種特殊的遞歸函數(shù)。如果一個(gè)遞歸函數(shù)的返回值是直接計(jì)算而得或恰是一個(gè)遞歸調(diào)用自身而得到的返回值,那么這個(gè)遞歸函數(shù)就稱為尾遞歸函數(shù)。換句話說,如果遞歸函數(shù)中有一個(gè)遞歸調(diào)用(自身)的語句是這個(gè)函數(shù)的最后一個(gè)可執(zhí)行語句,那么這個(gè)函數(shù)就被稱做尾遞歸函數(shù)。應(yīng)該注意,最后一個(gè)可執(zhí)行語句并不一定是程序中的最后一條語句
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 小學(xué)知識(shí)考試題及答案
- 內(nèi)蒙古自治區(qū)巴彥淖爾市2024-2025學(xué)年高中畢業(yè)班第二次質(zhì)量檢查歷史試題含解析
- 天津?yàn)I海汽車工程職業(yè)學(xué)院《高等微生物學(xué)》2023-2024學(xué)年第二學(xué)期期末試卷
- 工業(yè)互聯(lián)網(wǎng)平臺(tái)2025年異構(gòu)數(shù)據(jù)庫融合技術(shù)在工業(yè)互聯(lián)網(wǎng)平臺(tái)創(chuàng)新中的應(yīng)用
- 家具設(shè)計(jì)中的社會(huì)功能與環(huán)境適應(yīng)性研究探討及案例分析試題及答案
- 家具行業(yè)的消費(fèi)者行為分析考題試題及答案
- 武漢航海職業(yè)技術(shù)學(xué)院《場(chǎng)地環(huán)境風(fēng)險(xiǎn)評(píng)價(jià)與修復(fù)》2023-2024學(xué)年第二學(xué)期期末試卷
- 教師教育教學(xué)反思的有效方法與策略試題及答案
- 家具設(shè)計(jì)中的空間美學(xué)考題及答案
- 未來出行領(lǐng)域技術(shù)展望試題及答案
- 2025屆浙江省杭州市高三下學(xué)期二模物理試題(原卷版+解析版)
- 登高車安全培訓(xùn)
- 成人重癥患者顱內(nèi)壓增高防控護(hù)理專家共識(shí)(2024版)解讀課件
- 在線監(jiān)測(cè)運(yùn)維管理體系
- 英語課件 外研版(2019)選擇性必修四 Unit6 Developing ideas
- 2025年數(shù)獨(dú)考試試題及答案
- 化工工藝學(xué)知到智慧樹章節(jié)測(cè)試課后答案2024年秋廣州大學(xué)
- 產(chǎn)后抑郁癥的原因及護(hù)理文獻(xiàn)匯報(bào)
- 湖北省武漢市華中師大一附中2025屆高考數(shù)學(xué)全真模擬密押卷含解析
- 2024年司法考試完整真題及答案
- ARVR在電商設(shè)計(jì)中的應(yīng)用與前景
評(píng)論
0/150
提交評(píng)論