【文章內(nèi)容簡(jiǎn)介】 **s,int **w){ int i,j,k,t,l。 for(i=1。i=n+1。i++) { w[i][i1]=a[i1]。 m[i][i1]=0。 } for(l=0。l=n1。l++)//l是下標(biāo)ji的差for(i=1。i=nl。i++) {j=i+l。w[i][j]=w[i][j1]+a[j]+b[j]。m[i][j]=m[i][i1]+m[i+1][j]+w[i][j]。s[i][j]=i。for(k=i+1。k=j。k++) { t=m[i][k1]+m[k+1][j]+w[i][j]。if(tm[i][j]) { m[i][j]=t。s[i][j]=k。}}}}一、 填空題（本題15分，每小題1分） 算法就是一組有窮的 ，它們規(guī)定了解決某一特定類型問題的 。 在進(jìn)行問題的計(jì)算復(fù)雜性分析之前，首先必須建立求解問題所用的計(jì)算模型。3個(gè)基本計(jì)算模型是 、 、 。 算法的復(fù)雜性是 的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。 計(jì)算機(jī)的資源最重要的是 和 資源。因而，算法的復(fù)雜性有 和 之分。 f(n)= 62n+n2，f(n)的漸進(jìn)性態(tài)f(n)= O( ) 貪心算法總是做出在當(dāng)前看來 的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的 。 許多可以用貪心算法求解的問題一般具有2個(gè)重要的性質(zhì)： 性質(zhì)和 性質(zhì)。二、簡(jiǎn)答題（本題25分，每小題5分） 簡(jiǎn)單描述分治法的基本思想。 簡(jiǎn)述動(dòng)態(tài)規(guī)劃方法所運(yùn)用的最優(yōu)化原理。 何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？ 簡(jiǎn)單描述回溯法基本思想。 何謂P、NP、NPC問題三、算法填空（本題20分，每小題5分）n后問題回溯算法(1)用二維數(shù)組A[N][N]存儲(chǔ)皇后位置,若第i行第j列放有皇后,則A[i][j]為非0值,否則值為0。(2)分別用一維數(shù)組M[N]、L[2*N1]、R[2*N1]表示豎列、左斜線、右斜線是否放有棋子，有則值為1,否則值為0。for(j=0。jN。j++) if( 1 ) /*安全檢查*/ { A[i][j]=i+1。 /*放皇后*/ 2 ； if(i==N1) 輸出結(jié)果； else 3 ；。 /*試探下一行*/ 4 ； /*去皇后*/ 5 ；。 }數(shù)塔問題。有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使路徑上的值最大。for(r=n2。r=0。r) //自底向上遞歸計(jì)算for(c=0。 1 。c++) if( t[r+1][c]t[r+1][c+1]) 2 ；else 3 ；Hanoi算法Hanoi(n,a,b,c)if （n==1） 1 ；else{ 2 ； 3 ；Hanoi(n1,b, a, c)。}Dijkstra算法求單源最短路徑d[u]:s到u的距離 p[u]:記錄前一節(jié)點(diǎn)信息Initsinglesource(G,s)for each vertex v∈V[G] do { d[v]=∞。 1 } d[s]=0Relax(u,v,w)if d[v]d[u]+w(u,v)then { d[v]=d[u]+w[u,v]。 2 }dijkstra(G,w,s)1. Initsinglesource(G,s) 2. S=Φ 3. Q=V[G] Q Φ do u=min(Q) S=S∪{u} for each vertex 3 do 4 四、算法理解題（本題10分）根據(jù)優(yōu)先隊(duì)列式分支限界法，求下圖中從v1點(diǎn)到v9點(diǎn)的單源最短路徑，請(qǐng)畫出求得最優(yōu)解的解空間樹。要求中間被舍棄的結(jié)點(diǎn)用標(biāo)記，獲得中間解的結(jié)點(diǎn)用單圓圈○框起，最優(yōu)解用雙圓圈◎框起。五、算法理解題（本題5分）設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：①每個(gè)選手必須與其他n1名選手比賽各一次；②每個(gè)選手一天至多只能賽一次；③循環(huán)賽要在最短時(shí)間內(nèi)完成。（1）如果n=2k，循環(huán)賽最少需要進(jìn)行幾天；（2）當(dāng)n=23=8時(shí)，請(qǐng)畫出循環(huán)賽日程表。六、算法設(shè)計(jì)題（本題15分）分別用貪心算法、動(dòng)態(tài)規(guī)劃法、回溯法設(shè)計(jì)01背包問題。要求：說明所使用的算法策略；寫出算法實(shí)現(xiàn)的主要步驟；分析算法的時(shí)間。七、算法設(shè)計(jì)題（本題10分）通過鍵盤輸入一個(gè)高精度的正整數(shù)n(n的有效位數(shù)≤240)，去掉其中任意s個(gè)數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的n 和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小?！緲永斎搿?78543S=4【樣例輸出】13一、填空題（本題15分，每小題1分）1．規(guī)則 一系列運(yùn)算2. 隨機(jī)存取機(jī)RAM(Random Access Machine)；隨機(jī)存取存儲(chǔ)程序機(jī)RASP(Random Access Stored Program Machine)；圖靈機(jī)(Turing Machine)3. 算法效率4. 時(shí)間、空間、時(shí)間復(fù)雜度、空間復(fù)雜度5．2n6．最好 局部最優(yōu)選擇7. 貪心選擇 最優(yōu)子結(jié)構(gòu)二、簡(jiǎn)答題（本題25分，每小題5分） 分治法的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同；對(duì)這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止；將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。 “最優(yōu)化原理”用數(shù)學(xué)化的語(yǔ)言來描述：假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個(gè)決策D1，D2，…，Dn，如若這個(gè)決策序列是最優(yōu)的，對(duì)于任何一個(gè)整數(shù)k，1 k n，不論前面k個(gè)決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài)，即以后的決策Dk+1，Dk+2，…，Dn也是最優(yōu)的。 某個(gè)問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。 回溯法的基本思想是在一棵含有問題全部可能解的狀態(tài)空間樹上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)點(diǎn)。搜索過程中，每到達(dá)一個(gè)結(jié)點(diǎn)時(shí)，則判斷該結(jié)點(diǎn)為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對(duì)該子樹的搜索，退回到上層父結(jié)點(diǎn)，繼續(xù)下一步深度優(yōu)先搜索過程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹，再進(jìn)行搜索，而是在搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。 P(Polynomial問題)：也即是多項(xiàng)式復(fù)雜程度的問題。NP就是NondeterministicPolynomial的問題，也即是多項(xiàng)式復(fù)雜程度的非確定性問題。NPC(NP Complete)問題，這種問題只有把解域里面的所有可能都窮舉了之后才能得出答案，這樣的問題是NP里面最難的問題，這種問題就是NPC問題。三、算法填空（本題20分，每小題5分）n后問題回溯算法(1) !M[j]amp。amp。!L[i+j]amp。amp。!R[ij+N](2) M[j]=L[i+j]=R[ij+N]=1。(3) try(i+1,M,L,R,A) (4) A[i][j]=0 (5) M[j]=L[i+j]=R[ij+N]=0數(shù)塔問題。（1）c=r(2)t[r][c]+=t[r+1][c]（3）t[r][c]+=t[r+1][c+1]Hanoi算法（1）move(a,c)（2）Hanoi(n1, a, c , b)（3）Move(a,c)（1）p[v]=NIL（2）p[v]=u(3) v∈adj[u]（4）Relax(u,v,w)四、算法理解題（本題10分）1 2 3 4 5 6 7 82 1 4 3 6 5 8 73 4 1 2 7 8 5 64 3 2 1 8 7 6 55 6 7 8 1 2 3 46 5 8 7 2 1 4 37 8 5 6 3 4 1 28 7 6 5 4 3 2 1五、（1）8天（2分）；（2）當(dāng)n=23=8時(shí)，循環(huán)賽日程表（3分）。六、算法設(shè)計(jì)題（本題15分）（1）貪心算法 O（nlog（n））216。 首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。216。 具體算法可描述如下：void Knapsack(int n,float M,float v[],float w[],float x[]){Sort(n,v,w)。int i。for (i=1。i=n。i++) x[i]=0。float c=M。for (i=1。i=n。i++) {if (w[i]c) break。x[i]=1。c=w[i]。}if (i=n) x[i]=c/w[i]。}（2）動(dòng)態(tài)規(guī)劃法 O(nc)m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)01背包問題的最優(yōu)值。由01背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下。void KnapSack(int v[],int w[],int c,int n,int m[][11]){int jMax=min(w[n]1,c)。for (j=0。j=jMax。j++) /*m(n,j)=0 0=jw[n]*/m[n][j]=0。for (j=w[n]。j=c。j++) /*m(n,j)=v[n] j=w[n]*/m[n][j]=v[n]。for (i=n1。i1。i){ int jMax=min(w[i]1,c)。for (j=0。j=jMax。j++) /*m(i,j)=m(i+1,j) 0=jw[i]*/ m[i][j]=m[i+1][j]。for (j=w[i]。j=c。j++)/*m(n,j)=v[n] j=w[n]*/ m[i][j]=max(m[i+1][j],m[i+1][jw[i]]+v[i])。}m[1][c]=m[2][c]。if(c=w[1])m[1][c]=max(m[1][c],m[2][cw[1]]+v[1])。}（3）回溯法 O(2n)cw:當(dāng)前重量 cp:當(dāng)前價(jià)值 bestp：當(dāng)前最優(yōu)值voidbacktrack(inti) //回溯法 i初值1{if(in) //到達(dá)葉結(jié)點(diǎn) { bestp=cp。 return。 } if(cw+w[i]=c) //搜索左子樹 {cw+=w[i]。 cp+=p[i]。 backtrack(i+1)。 cw=w[i]。 cp=p[i]。 } if(Bound(i+1)bestp) //搜索右子樹 backtrack(i+1)。 } 七、算法設(shè)計(jì)題（本題10分）為了盡可能地逼近目標(biāo)，我們選取的貪心策略為：每一步總是選擇一個(gè)使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個(gè)數(shù)字，否則刪除第一個(gè)遞減區(qū)間的首字符。然后回到串首，按上述規(guī)則再刪除下一個(gè)數(shù)字。重復(fù)以上過程s次，剩下的數(shù)字串便是問題的解了。具體算法如下：輸入s, n。wh