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

ABCD設有一個遞歸算法如下：ntunntn){fn<=)reurn;eereurnn*unn;}ABCD計算fun(n)需要執行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函數xy定義如下：xy=xy+xy)當x>且y>0xy=x+y否則則ABCD1234ABCD函數xy定義如下：n=n+n+1當n>1n=1否則則ABCD10151620ABCD某遞歸算法的執行時間的遞推關系如下：n=1當n=時n=n/+1當n>時ABCDO)Ogn)On)Ongn)某遞歸算法的執行時間的遞推關系如下：n=1當n=時n=n/+1當n>時則該算法的時間復雜度為（）。ABCABCDOgn)On)Ongn)某遞歸算法的執行時間的遞推關系如下：n=1當n=時n=n/+n當n>時則該算法的時間復雜度為（）。ABCABCDOgn)On)Ongn)

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