【文章內(nèi)容簡介】 int search() //廣搜返回目標結(jié)點的最小步數(shù){ struct colornode u,v。 while(head!=tail) { u=takeoutofopen()。 v=moveahead(u)。 //u向前走一格得到新結(jié)點v if(islegal(v)) //如果該結(jié)點是合法的結(jié)點(未越界且是空格) { if(isaim(v)) //判是否是目標結(jié)點 return()。 if(!used(v)) //如果是未到達過的結(jié)點 addtoopen(v)。 //加入到open表 } v=turntoleft(u)。 //u向左轉(zhuǎn)得到新結(jié)點v if(!used(v)) addtoopen(v)。 v=turntoright(u)。 //u向右轉(zhuǎn)得到新結(jié)點v if(!used(v)) addtoopen(v)。 }}int used(struct colornode v) //判斷該結(jié)點是否是到達過的結(jié)點{ if(b[][][][]==0) return(0)。 else return(1)。}void addtoopen(struct colornode v) //加入到open表{ open[tail++]=v。 tail=tail%openlen。 b[][][][]=1。}struct colornode takeoutofopen() //從open表中取出一個結(jié)點并把該結(jié)點從open表中刪除{ struct colornode v。 v=open[head++]。 head=head%openlen。 return(v)。}void init() //初始化{ int i,j,k,l。 for(i=0。in。i++) //所有狀態(tài)初始化 for(j=0。jn。j++) for(k=0。k5。k++) for(l=0。l4。l++) b[i][j][k][l]=0。 head=0。 tail=0。 addtoopen(s)。 //把起始點加入到open表}void readdata() //讀入數(shù)據(jù){ char str[50]。 int i,j。 for(i=0。in。i++) { gets(str)。 for(j=0。jn。j++) if(str[j]==39。.39。) //讀入數(shù)據(jù)39。.39。表示空格 a[i][j]=0。 //存儲時 0：表示空格 else a[i][j]=1。 // 1：表示墻 } scanf(%d%d%d%d,amp。,amp。,amp。,amp。)。 //讀入起始結(jié)點信息 scanf(%d%d%d,amp。,amp。,amp。)。 //讀入目標結(jié)點信息}int isaim(struct colornode v) //判斷該結(jié)點是否是目標結(jié)點{ if(==amp。amp。==amp。amp。==) return 1。 else return 0。}int islegal(struct colornode v) //如果該結(jié)點是合法的結(jié)點(未越界且是空格){ if(0||=n||0||=n) //若越界 return 0。 if(a[][]==0) //0：表示空格 return 1。 return 0。}struct colornode moveahead(struct colornode u) //返回u向前走一格得到的結(jié)點{ struct colornode v。 =+direct[][0]。 =+direct[][1]。 =(+1)%5。 =。 =+1。 return(v)。}struct colornode turntoleft(struct colornode u) //u向左轉(zhuǎn)得到新結(jié)點v{ struct colornode v。 v=u。 =(+1)%4。 =+1。 return(v)。}struct colornode turntoright(struct colornode u) //u向左轉(zhuǎn)得到新結(jié)點v{ struct colornode v。 v=u。 =(+3)%4。 =+1。 return(v)。} 測試數(shù)據(jù)：XXXXXXXXXXXXXXXXXXXX.....XXXX......X..............X..X..............X...X..........X..XX....X..X.......X......XXXX...........X.......XXXXXXX....XXXXXX..XX...........X.......X.X..........X..XXXXXXX....X....X..X.......X......XXXX...........X.......X........XXX.....XXXX.....XX.........1 1 1 1 4 8 11． 最長公共子序列一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=x1, x2,…, xm，則另一序列Z=z1, z2,…, zk是X的子序列是指存在一個嚴格遞增的下標序列 i1, i2,…, ik，使得對于所有j=1,2,…,k有答如下：a) 最長公共子序列的結(jié)構(gòu)若用窮舉搜索法，耗時太長，算法需要指數(shù)時間。易證最長公共子序列問題也有最優(yōu)子結(jié)構(gòu)性質(zhì)設序列X=x1, x2, …, xm和Y=y1, y2, …, yn的一個最長公共子序列Z=z1, z2, …, zk，則：i. 若xm=yn，則zk=xm=yn且Zk1是Xm1和Yn1的最長公共子序列； ii. 若xm≠yn且zk≠xm ，則Z是Xm1和Y的最長公共子序列； iii. 若xm≠yn且zk≠yn ，則Z是X和Yn1的最長公共子序列。 其中Xm1=x1, x2, …, xm1，Yn1=y1, y2, …, yn1，Zk1=z1, z2, …, zk1。最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。b) 子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出X=x1, x2, …, xm和Y=y1, y2, …, yn的最長公共子序列，可按以下方式遞歸地進行：當xm=yn時，找出Xm1和Yn1的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。當xm≠yn時，必須解兩個子問題，即找出Xm1和Y的一個最長公共子序列及X和Yn1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。由此遞歸結(jié)構(gòu)容易看到最長公共子序列問題具有子問題重疊性質(zhì)。例如，在計算X和Y的最長公共子序列時，可能要計算出X和Yn1及Xm1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算Xm1和Yn1的最長公共子序列。我們來建立子問題的最優(yōu)值的遞歸關系。用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=x1, x2, …, xi，Yj=y1, y2, …, yj。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故c[i,j]=0。建立遞歸關系如下：c) 計算最優(yōu)值由于在所考慮的子問題空間中，總共只有θ(m*n)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。計算最長公共子序列長度的動態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=x1, x2, …, xm和Y=y1, y2, …, yn作為輸入。輸出兩個數(shù)組c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存儲Xi與Yj的最長公共子序列的長度，b[i,j]記錄指示c[i,j]的值是由哪一個子問題的解達到的，這在構(gòu)造最長公共子序列時要用到。最后，X和Y的最長公共子序列的長度記錄于c[m,n]中。程序如下：includeincludeint lcs_length(char x[], char y[])。int main(){ char x[100],y[100]。 int len。 while(1) { scanf(%s%s,x,y)。 if(x[0]==39。039。) //約定第一個字符串以‘0’開始表示結(jié)束 break。 len=lcs_length(x,y)。 printf(%d\n,len)。 }}int lcs_length(char x[], char y[] ){ int m,n,i,j,l[100][100]。 m=strlen(x)。 n=strlen(y)。 for(i=0。im+1。i++) l[i][0]=0。 for(j=0。jn+1。j++) l[0][j]=0。 for(i=1。i=m。i++) for(j=1。j=n。j++) if(x[i1]==y[j1]) //i,j從1開始，但字符串是從0開始 l[i][j]=l[i1][j1]+1。 else if(l[i][j1]l[i1][j]) l[i][j]=l[i][j1]。 else l[i][j]=l[i1][j]。 return l[m][n]。}由于每個數(shù)組單元的計算耗費Ο(1)時間，算法lcs_length耗時Ο(mn)。思考：空間能節(jié)約嗎？2． 計算矩陣連乘積在科學計算中經(jīng)常要計算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數(shù)等于矩陣B的行數(shù)。若A是一個pq的矩陣，B是一個qr的矩陣，則其乘積C=AB是一個pr的矩陣。由該公式知計算C=AB總共需要pqr次的數(shù)乘。其標準計算公式為： 現(xiàn)在的問題是，給定n個矩陣{A1,A2,…,An}。其中Ai與Ai+1是可乘的，i=1,2,…,n1。要求計算出這n個矩陣的連乘積A1A2…An。遞歸公式： 程序如下：includeint main(){ int p[101],i,j,k,r,t,n。 int m[101][101]。 //為了跟講解時保持一致數(shù)組從1開始 int s[101][101]。 //記錄從第i到第j個矩陣連乘的斷開位置 scanf(%d,amp。n)。 for(i=0。i=n。i++) scanf(%d,amp。p[i])。 //讀入p[i]的值(注意：p[0]到p[n]共n+1項) for(i=1。i=n。i++) //初始化m[i][i]=0 m[i][i]=0。 for(r=1。rn。r++) //r為i、j相差的值 for(i=1。in。i++) //i為行 { j=i+r。 //j為列 m[i][j]=m[i+1][j]+p[i1]*p[i]*p[j]。 //給m[i][j]賦初值 s[i][j]=i。 for(k=i+1。kj。k++) { t=m[i][k]+m[k+1][j]+p[i1]*p[k]*p[j]。 if(tm[i][j]) { m[i][j]=t。 //m[i][j]取最小值 s[i][j]=k。 } } } printf(%d,m[1][n])。}4． 防衛(wèi)導彈一種新型的防衛(wèi)導彈可截擊多個攻擊導彈。它可以向前飛行，也可以用很快的速度向下飛行，可以毫無損傷地截擊進攻導彈，但不可以向后或向上飛行。但有一個缺點，盡管它發(fā)射時可以達到任意高度，但它只能截擊比它上次截擊導彈時所處高度低或者高度相同的導彈。現(xiàn)對這種新型防衛(wèi)導彈進行測試，在每一次測試中，發(fā)射一系列的測試導彈（這些導彈發(fā)射的間隔時間固定，飛行速度相同），該防衛(wèi)導彈所能獲得的信息包括各進攻導彈的高度，以及它們發(fā)射次序。現(xiàn)要求編一程序，求在每次測試中，該防衛(wèi)導彈最多能截擊的進攻導彈數(shù)量，一個導彈能被截擊應滿足下列兩個條件之一：a)它是該次測試中第一個被防衛(wèi)導彈截擊的導彈；b)它是在上一次被截擊導彈的發(fā)射后發(fā)射，且高度不大于上一次被截擊導彈的高度的導彈。輸入數(shù)據(jù)：第一行是一個整數(shù)n，以后的n各有一個整數(shù)表示導彈的高度。輸出數(shù)據(jù)：截擊導彈的最大數(shù)目。分析：定義l[i]為選擇截擊第i個導彈，從這個導彈開始最多能截擊的導彈數(shù)目。由于選擇了第i枚導彈，所以下一個要截擊的導彈j的高度要小于等于它的高度，所以l[i]應該等于從i＋1到n的每一個j，滿足h[j]=h[i]的j中l(wèi)[j]的最大值。程序如下：includeint main(){ int i,j,n,max,h[100],l[100]。 scanf(%d,amp。n)。 for(i=0。in。i++) scanf(%d,amp。h[i])。 l[n1]=1。 for(i=n2。i=0。i) { max=0。 for(j=i+1。jn。j++) if(h[i]h[j]amp。amp。maxl[j]) max=l[j]。 l[i]=max+1。 } printf(%d,l[0])。}12． *田忌賽馬田忌與齊王賽馬，雙方