數(shù)據(jù)結(jié)構(gòu)(Java語(yǔ)言版)-習(xí)題及答案 第5章遞歸習(xí)題答案_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)(Java語(yǔ)言版)-習(xí)題及答案 第5章遞歸習(xí)題答案_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)(Java語(yǔ)言版)-習(xí)題及答案 第5章遞歸習(xí)題答案_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)(Java語(yǔ)言版)-習(xí)題及答案 第5章遞歸習(xí)題答案_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)(Java語(yǔ)言版)-習(xí)題及答案 第5章遞歸習(xí)題答案_第5頁(yè)
已閱讀5頁(yè),還剩4頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

ABCD設(shè)有一個(gè)遞歸算法如下:ntunntn){fn<=)reurn;eereurnn*unn;}ABCD計(jì)算fun(n)需要執(zhí)行n次遞歸.un=0C.此遞歸算法最多只能計(jì)算到un).ABCABCD棧隊(duì)列樹圖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)當(dāng)x>且y>0xy=x+y否則則ABCD1234ABCD函數(shù)xy定義如下:n=n+n+1當(dāng)n>1n=1否則則ABCD10151620ABCD某遞歸算法的執(zhí)行時(shí)間的遞推關(guān)系如下:n=1當(dāng)n=時(shí)n=n/+1當(dāng)n>時(shí)ABCDO)Ogn)On)Ongn)某遞歸算法的執(zhí)行時(shí)間的遞推關(guān)系如下:n=1當(dāng)n=時(shí)n=n/+1當(dāng)n>時(shí)則該算法的時(shí)間復(fù)雜度為()。ABCABCDOgn)On)Ongn)某遞歸算法的執(zhí)行時(shí)間的遞推關(guān)系如下:n=1當(dāng)n=時(shí)n=n/+n當(dāng)n>時(shí)則該算法的時(shí)間復(fù)雜度為()。ABCABCDOgn)On)Ongn)

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(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ì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論