作業(yè)計(jì)算機(jī)算法與設(shè)計(jì)

計(jì)算機(jī)算法設(shè)計(jì)與分析大作業(yè)1057120 唐榜亮 信計(jì)1班答：⑴遞歸算法的特點(diǎn)：遞歸算法是一種直接或者間接地調(diào)用自身算法的過(guò)程， 它往往使算法的描述簡(jiǎn)而且易于理解。遞歸算法解決問(wèn)題的特點(diǎn)：①遞歸就是在過(guò)程或函數(shù)里調(diào)用自身。②在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱(chēng)為遞歸出口。③遞歸算法解題通常顯得很簡(jiǎn)潔，但遞歸算法解題的運(yùn)行效率較低。所以一般不提倡用遞歸算法設(shè)計(jì)程序。④在遞歸調(diào)用的過(guò)程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開(kāi)辟了棧來(lái)存儲(chǔ)。遞歸次數(shù)過(guò)多容易造成棧溢出等。⑵動(dòng)態(tài)規(guī)劃的特點(diǎn)：動(dòng)態(tài)規(guī)劃方法是處理分段過(guò)程最優(yōu)化問(wèn)題的一類(lèi)及其有效的方法，。在使用動(dòng)態(tài)規(guī)劃算法自頂向下求解時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題反復(fù)計(jì)算多次。但對(duì)每一個(gè)問(wèn)題只計(jì)算一次，而后將其解保存在一個(gè)表格中，當(dāng)再次要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地調(diào)用一下已有的結(jié)果。通常，不同的子問(wèn)題個(gè)數(shù)隨著輸入問(wèn)題的規(guī)模呈多項(xiàng)式增長(zhǎng)，因此，動(dòng)態(tài)規(guī)劃算法通常只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。⑶貪心算法的特點(diǎn)：優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測(cè)度作最優(yōu)選擇，而不考慮各種可能的整體情況，它省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間，它采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，通過(guò)每一步貪心選擇，可得到問(wèn)題的一個(gè)最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的。題相應(yīng)的算法以及具體程序在做一些分析和說(shuō)明。1）對(duì)遞歸算法：例：2-6排列的字典序問(wèn)題字典序值012345排列123132213231312321{1,2,...,n}有個(gè)不同的排列。將這字典序值012345排列123132213231312321nn{1,2,...,n}的一個(gè)排列，計(jì)算出這個(gè)排列的字典序值，以及按字典序排列的下一個(gè)排列。input.txtn1行是n個(gè)元素{1,2,...,n}的一個(gè)排列。結(jié)果輸出：將計(jì)算出的排列的字典序值和按字典序排列的下一個(gè)排列輸出到文件output.txt。文件的第一行是字典序值，第二行是按字典序排列的下一個(gè)排列。輸入文件示例 輸出文件示例Input.txt output.txt8 827726458173 26458317分析與解答：①由排列計(jì)算字典序值設(shè)給定的{1,2,...,n}的排列為，其字典序值為rank(,n)。按字典序的定義顯然有rank(,n)設(shè)r是在以[1]開(kāi)頭的所有排列中的序號(hào)，則r也是[[2],[3]...[n]]作為集合{1,2,...,n}/{[1]}中排列的字典序值。如果將[[2],[3]...[n]]中每個(gè)大于[1]的元素都減1，則得到集合{1,2,...,n-1}的一個(gè)排列，其字典序值也是r。由此得到計(jì)算rank(,n)的遞歸式如下：rank,nn111 1其中， 1 初始條件為rank1,10據(jù)此可設(shè)計(jì)計(jì)算rank(,n)的算法permRank如下：intpermRank(intn,int*pi){for(intj=1,r=0;j<=n;j++)rho[j]=pi[j];for(j=1;j<=n;j++){r+=(rho[j]-1)*f[n-j];for(inti=j+1;i<=n;i++)if(rho[i]>rho[j])rho--;}returnr;}其中，f[j]存儲(chǔ)預(yù)先計(jì)算出的j!的值。②由字典序值計(jì)算排列對(duì)于每個(gè)整數(shù)，0r1，都有惟一的階層分解：rn1d*,0di i

i。設(shè)rrank,n)，則顯然有d 1。n1

i1進(jìn)一步，由rrd (n1)!rank(n可遞歸找到排列。最后令n1[i1]可得到排列。據(jù)此可設(shè)計(jì)計(jì)算排列使rranknpermUnrank如下。voidpermUnrank(intn,intpi){pi[n]=1;for(intj=1;j<n;j-1){intd=(r%f[j-1])/f[j];r=d*f[j];pi[n-j]=d+1;for(inti=n-j;i<-n;j++)if(pi[i]>d)pi[i]++;}}③出排列計(jì)算下一個(gè)樸烈，首先找到下標(biāo)，使得[i[i1],且[i1[i2[n]；其次找到下標(biāo)j，使得[ij]且對(duì)所有jkn有[i]和j]；然后交換j和[i；最后將子排列[[i1],[i2],,[n]]反轉(zhuǎn)。按此思想設(shè)計(jì)的算法permSuce如下：voidpermSuce(intn,int*pi,int&flag){pi[0]=0;inti=n-1;while(pi[i+1]<pi[i])i--;if(i0)flag=0;else{flag=1;intj=n;while(pi[j]<pi[i])j++;Swap(pi[i],pi[j]);for(inth=j-1;hn;h++)rha[h]=pi[h];for(h=i+1;hn;h++)pi[h]=rha[n+i=1-h];}}對(duì)動(dòng)態(tài)規(guī)劃：例：設(shè)計(jì)一個(gè)n時(shí)間的算法，找出由n子序列。用數(shù)組n記錄以a[i],0in為結(jié)尾元素的最長(zhǎng)遞增子序列a的最長(zhǎng)遞增子序列的長(zhǎng)度為max{b[i]}滿(mǎn)足最優(yōu)子結(jié)0in構(gòu)性質(zhì)，可以遞歸地定義為1,b[imax{10kia[k]a[i]據(jù)此將計(jì)算b[i]轉(zhuǎn)化為i個(gè)規(guī)模更小的子問(wèn)題。按此思想設(shè)計(jì)的動(dòng)態(tài)規(guī)劃算法描述如下：int[]Sdyna(){inti,j,k;for(i=1,b[0]=1;i<n;i++){for(j=0,k=0;j<i;j++)if(a[j]a[i]&&k<b[j])k=b[j];b[i]=k-1;}returnmaxL(n);}intmaxL(intn){for(inti=0,temp=0;i<n;i++)if(b[i]>temp)temp=b[i];returntemp;}對(duì)貪心算法：a~h8Fibonacci將結(jié)果推廣到n個(gè)字符恰好是前nFibonacci