第5章遞歸習題參考答案 一、單選題ABCD遞歸模型如下：=1n=n+nn>1ABCD.=0.=1C.=1.n=n遞歸模型如下：=1n=n+nn>1其中遞歸體是 。ABCD.ABCD.=1C.n=n+n.n=nABCDABCD線性表棧隊列樹ABCD函數(shù)x，y定義如下：n=n+n+1當n>1n=1否則則ABCD10151620ABCD函數(shù)x，y定義如下：x，y=x，y+x，y)當x>且y>0x，y=x+y否則則，ABCD1234某遞歸算法的執(zhí)行時間的遞推關(guān)系如下：n=1當n=時n=n/+1當n>時則該算法的時間復(fù)雜度為 。ABCABCDOgn)On)Ongn)

ABCD設(shè)有一個遞歸算法如下：ntunntn){fn<=)reurn;eereurnn*unn;}ABCD計算fun(n)需要執(zhí)行n次遞歸.un=0C.此遞歸算法最多只能計算到un).ABCABCD棧隊列樹圖ABCD遞歸模型為=，n=n+n（n>ABCD.=0.=1C.=1.n=nABCD遞歸模型為=，n=n+n（n>ABCD.=0.=1C.n=n+n.n=nABCABCD遞歸出口遞歸體遞歸出口和遞歸體以上都不包含ABCD函數(shù)xy定義如下：xy=xy+xy)當x>且y>0xy=x+y否則則ABCD1234ABCD函數(shù)xy定義如下：n=n+n+1當n>1n=1否則則ABCD10151620ABCD某遞歸算法的執(zhí)行時間的遞推關(guān)系如下：n=1當n=時n=n/+1當n>時ABCDO)Ogn)On)Ongn)某遞歸算法的執(zhí)行時間的遞推關(guān)系如下：n=1當n=時n=n/+1當n>時則該算法的時間復(fù)雜度為（）。ABCABCDOgn)On)Ongn)某遞歸算法的執(zhí)行時間的遞推關(guān)系如下：n=1當n=時n=n/+n當n>時則該算法的時間復(fù)雜度為（）。ABCABCDOgn)On)Ongn)

ABCABCD線性表棧隊列樹ABCABCD較快較慢相同無法比較ABCABCD一般而言，使用遞歸解決問題較使用循環(huán)解決問題需要定義更多的變量遞歸算法的執(zhí)行效率相對較低遞歸算法的執(zhí)行需要用到棧以上都是錯誤的二、編程題POJ1664—放蘋果時間限制：1000ms，空間限制：10000K。[描述]輸入格式：第一行是測試數(shù)據(jù)的數(shù)目（≤≤）。以下每行均包含兩個整數(shù)和n，以空格分開，≤，n≤。輸出格式：對輸入的每組數(shù)據(jù)m和n，用一行輸出相應(yīng)的k。答：prtvu*;prtvuScnner;pubccsn{pubccntventntn)//求解算法{1;eem<n)reurnve;ee==n)reurnve+;eereurnven+venn;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;=nnexIn;he>){=nnexIn;n=nnexIn;Syeuprnnven;}}}OJ—分形問題時間限制：，空間限制：。[描述]問題描述：分形是某種技術(shù)意義上在所有尺度上自相似方式顯示的物體或數(shù)值。物體不需要在所有尺度上都具有完全相同的結(jié)構(gòu)，但在所有尺度上必須具有相同的結(jié)構(gòu)“類型”XXXX如果用B(n-1)表示n-1級盒子分形，那么遞歸地定義n級盒子分形如下B(n-1)B(n-1)B(n-1)B(n-1)B(n-1)你的任務(wù)是畫出n級盒子分形。輸入格式：輸入包含幾個測試用例。輸入的每一行包含一個不大于7的正整數(shù)n，輸入的最后一行是負整數(shù)-1，表示輸入的結(jié)束。輸出格式：對于每個測試用例，使用表示法輸出框分形。請注意是一個大寫字母。在每個測試用例后打印一行只有一個短劃線。答：prtvu*;prtvuScnner;pubccsn{cntN=;cben]p=newbenNN;cn]p=;//的n次冪表cvdventxntyntn) //求解算法{n==){pxy=rue;return;}vexyn; //遞歸繪制左上角的圖形vexy+*pnn; //遞歸繪制右上角的圖形vex+pny+pnn;//遞歸繪制中間的圖形vex+*pnyn; //遞歸繪制左下角的圖形vex+*pny+*pnn;//遞歸繪制右下角的圖形}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;herue){n=nnexIn;fn==)rnt=;i<N;++)//p初始化rnt=;j<N;++)p=e;ven;rnt=;i<=pn;++){rnt=;j<=pn;++)p)Syeuprn"";eeSyeuprn"";Syeuprnn;}Syeuprnn"";}}}.：2000ms，空間限制：65536K8號了，但是對于學校財務(wù)處的工作人員來說，這一天則是很忙碌的一天，財務(wù)處的小胡老師最近就在考慮一個問題：如果每個老師的工資額都知道，最少需要準備多少張人民幣，才能在給每位老師發(fā)工資的時候都不用老師找零呢？這里假設(shè)老師的工資都是正整數(shù)，單位元，人民幣一共有100元、50元、10元、5元、2元和1n（n<100），表示老師的人數(shù)，然后是n個老師的工資。n=0表示輸入的結(jié)束，不做處理。輸出格式：對于每個測試實例輸出一個整數(shù)x，表示至少需要準備的人民幣張數(shù)。每個輸出占一行。答：prtvu*;prtvuScnner;pubccsn{cntN=;cnt]=newnN;cnt]b=;pubccntgecunntx)//求解算法{x==)0;x>=)reurn+gecunx;eex>=0&x<)reurn+gecunx;eex<0&x>=)reurn+gecunx;eex<0&x>=)reurn+gecunx;eex<5&x>=)reurn+gecunx;ee //n=1reurn+gecunx;}pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntn;ntherue){n=nnexIn;n==)brek;rnt=;i<n;++)=nnexIn;u=;rnt=;j<n;++)u+=gecun;Syeuprnnu;}}}.HDU2013蟠桃記問題時間限制：2000ms，空間限制：65536K。[描述]問題描述：喜歡西游記的同學肯定都知道悟空偷吃蟠桃的故事，你們一定都覺得這猴子太鬧騰了，其實你們是有所不知：悟空是在研究一個數(shù)學問題！什么問題？他研究的問題是蟠桃一共有多少個！不過，到最后他還是沒能解決這個難題。當時的情況是這樣的：第一天悟空吃掉桃子總數(shù)一半多一個，第二天又將剩下的桃子吃掉一半多一個，以后每天吃掉前一天剩下的一半多一個，到第n天準備吃的時候只剩下一個桃子。聰明的你，請幫悟空算一下，他第一天開始吃的時候桃子一共有多n（1<n<30），表示只剩下一個桃子的時候是在第n式：對于每組輸入數(shù)據(jù)，輸出第一天開始吃的時候桃子的總數(shù)，每個測試實例占一行。答：prtvuScnner;pubccsn{pubccvdnSrng]rg){Scnnern=newScnnerSyen;ntnn;henhNex){n=nnexIn;n=;n--;hen=)n=n+*;Syeuprnnn;}}}.H—漢諾塔問題時間限制：，空間限制：。描述問題描述：n個盤子的漢諾塔問題的最少移動次數(shù)是^n，即在移動過程中會產(chǎn)生2^n個系列。由于發(fā)生錯移產(chǎn)生的系列就增加了，這種錯誤是放錯了柱子，并不會把大盤放到小盤上，即各柱子從下往上的大小仍保持如下關(guān)系：n=+p+q>>…>mb>b>…>bpc>c>…>cq其中是柱上的盤的盤號系列，b是柱上的盤的盤號系列，ci是C柱上的盤的盤號系列，最初目標是將A柱上的n個盤子移到C盤。給出一個系列，判斷它是否是在正確的移動中產(chǎn)生的系列。例，n=33//柱上只有盤號的盤2//柱上只有盤號的盤1//C柱上只有盤號的盤是正確的。而例，n=33//柱上只有盤號的盤1//柱上只有盤號的盤2//C柱上只有盤號的盤是不正確的。注：對于例如果目標是將柱上的n個盤子移到盤，則是正確的。輸入格式：包含多組數(shù)據(jù)，首先輸入t，表示有t組數(shù)據(jù)，每組數(shù)據(jù)4行，第1行n是盤子的數(shù)目n≤64，后3ma1a2ampb1b2bpqc1c2…cqn=+p+q，≤≤n，≤p≤n，≤q≤n。輸出格式：對于每組數(shù)據(jù)，判斷它是否是在正確的移動中產(chǎn)生的系列，正確輸出rue，否則e。答：prtvu*;prtvuScnner;pubccsn{cntN=;cntp=newnN;cn]n=newn;cbenhnntnntntbntc){n==) //returntrue;pn==n)//當盤子n在上時，下面該判斷盤子n是否在或上{n++;reurnhnncb;}eepcnc==n)//當盤子n在C上時，下面該判斷盤子n是否在或C上{nc++;reurnhnnbc;}eereurne; //其他情況返回e}pubccvdnSrng]rg){Scnnern=newScnnerSyen;nt;=nnexIn;he>){ntnpq;rnt=;i<;++)//p初始化rnt=;j<N;++)p=;rnt=;i<;++)//n初始化n=;n=nnexIn;=nnexIn;rnt=;i<;++)p=nnexIn;p=nnexIn;rnt=;i<p;++)p=nnexIn;q=nnexIn;rnt=;i<q;++)p=nnexIn;hnn//初始個塔對應(yīng)到2Syeuprnn"rue";eeSyeuprnn"e";}}}OJ—字母旋轉(zhuǎn)游戲限制時間：，限制空間：。問題描述：：給定兩個整數(shù)，n，生成一個×n的矩陣，矩陣中元素取值為至的個字母中的一個，在左上角，其余各數(shù)按順時針方向旋轉(zhuǎn)前進，依次遞增放置，當超過時又從開始填充。例如，當=，n=時，矩陣中的內(nèi)容如圖所示。輸入格式：m為行數(shù)，n為列數(shù)，其中m，n都為大于0的整數(shù)。輸出格式：分行輸出相應(yīng)的結(jié)果問題描述：：給定兩個整數(shù)，n，生成一個×n的矩陣，矩陣中元素取值為至的個字母中的一個，在左上角，其余各數(shù)按順時針方向旋轉(zhuǎn)前進，依次遞增放置，當超過時又從開始填充。例如，當=，n=時，矩陣中的內(nèi)容如圖所示。n為列數(shù)，其中m，n都為大于0答：prtvuScnner;pubccsn{cnt=;cntN=;cchr]=newchrN;cntn;cntr=;pubccvdCreentxntyntntn)//遞歸創(chuàng)建矩陣{fm<=0||n<=) //遞歸結(jié)束條件return;f==1&n>) //矩陣只有第y行的n個元素{rnt=x;j<=x+n;++){y=chrn+r%;r++;}return;}f>0&n==) //矩陣只有第x列的個元素{rnt=y;i<=y+;++){x=chrn+r%;r++;}return;}rnt=x;j{y=chrn+r%;;r++;}rnt=y;i{x+n=chrn+r%;;r++;}rnt=x+n;>x;) //下一行{y+=chrn+r%;r++;}rnt=y+;>y;) //左一列{x=chrn+r%;r++;}Creex+y+n; //遞歸調(diào)用}pubccvdp //輸出螺旋矩陣{rnt=;i{rnt=;jSyeuprn""+;Syeuprnn;}}pubccvdnSrng]rg){Scnnern=newScnnerSyen;m=nnexIn;n=nnexIn;Creen;p;}}三、簡答題什么是遞歸，遞歸有哪些形式？ 答：在定義一個函數(shù)時出現(xiàn)調(diào)用本函數(shù)的成分，稱為遞歸。遞歸分為直接遞歸和間接遞歸兩種形式。直接遞歸是指在函數(shù)在執(zhí)行過程中調(diào)用本身。間接遞歸是指函數(shù)在執(zhí)行過程中調(diào)用其它函數(shù)再經(jīng)過這些函數(shù)調(diào)用本身。簡述遞歸的特點。 答：遞歸的特點是它既有遞堆過程，又有求值（回歸）過程，而且在任何一個深度時，它的所有變量和參數(shù)的值都保存著，同一變量或參數(shù)在不同深度的值，都壓入系統(tǒng)棧中。簡述遞歸算法的優(yōu)缺點。 答：遞歸算法優(yōu)點是結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。遞歸算法的缺點是算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。推導出求x的n次冪的遞歸模型。 答：xn=x當n=時xn=n*xn)當n>時某遞歸算法求解時間復(fù)雜度的遞推式如下：n=1當n=0n=n+n+3當n>0求該算法的時間復(fù)雜度。 答：四、填空題將遞歸算法轉(zhuǎn)換為非遞歸算法時，通常使用這種數(shù)據(jù)結(jié)構(gòu)。 答：棧遞推式=，n=n+n的解是。 答：n(n-1)/2遞推式=，n=n/+的解是。 答：設(shè)a是一個含有n個整數(shù)的數(shù)組，求該數(shù)組最大元素的遞歸定義是。 答：=，=}（≥）設(shè)a是一個含有n個整數(shù)的數(shù)組，求該數(shù)組最小元素的遞歸定義是。 答：=，=IN（≥）設(shè)a是一個含有n個整數(shù)的數(shù)組，求該數(shù)組所有元素之和的遞歸定義是。 答：=，=+)（≥）