ACM程序設(shè)計(jì)競(jìng)賽例題[1]

1、備戰(zhàn)ACM資料習(xí)題10-1背包問(wèn)題在0 / 1背包問(wèn)題中，需對(duì)容量為c 的背包進(jìn)行裝載。從n 個(gè)物品中選取裝入背包的物品，每件物品i 的重量為wi ，價(jià)值為pi 。對(duì)于可行的背包裝載，背包中物品的總重量不能超過(guò)背包的容量，最佳裝載是指所裝入的物品價(jià)值最高。 程序如下：#include <stdio.h>void readdata();void search(int);void checkmax();void printresult();int c=35, n=10; /c： 背包容量；n：物品數(shù)int w10, v10; /wi、vi：第i件物品的重量和價(jià)值int a10, max

2、; /a數(shù)組存放當(dāng)前解各物品選取情況；max：記錄最大價(jià)值 /ai=0表示不選第i件物品，ai=1表示選第i件物品int main()readdata(); /讀入數(shù)據(jù)search(0); /遞歸搜索printresult();void search(int m)if(m>=n)checkmax(); /檢查當(dāng)前解是否是可行解，若是則把它的價(jià)值與max比較elseam=0; /不選第m件物品search(m+1); /遞歸搜索下一件物品am=1; /不選第m件物品search(m+1); /遞歸搜索下一件物品void checkmax()int i, weight=0, value=0;

3、for(i=0;i<n;i+)if(ai=1) /如果選取了該物品weight = weight + wi; /累加重量value = value + vi; /累加價(jià)值if(weight<=c) /若為可行解if(value>max) /且價(jià)值大于maxmax=value; /替換maxvoid readdata()int i;for(i=0;i<n;i+)scanf("%d%d",&wi,&vi); /讀入第i件物品重量和價(jià)值void printresult()printf("%d",max);2裝載問(wèn)題有兩艘

4、船，載重量分別是c1、 c2，n個(gè)集裝箱，重量是wi (i=1n)，且所有集裝箱的總重量不超過(guò)c1+c2。確定是否有可能將所有集裝箱全部裝入兩艘船。提示：求出不超過(guò)c1的最大值max，若總重量max < c2則能裝入到兩艘船。3堡壘問(wèn)題（ZOJ1002）如圖城堡是一個(gè)4×4的方格，為了保衛(wèi)城堡，現(xiàn)需要在某些格子里修建一些堡壘。城堡中的某些格子是墻，其余格子都是空格，堡壘只能建在空格里，每個(gè)堡壘都可以向上下左右四個(gè)方向射擊，如果兩個(gè)堡壘在同一行或同一列，且中間沒(méi)有墻相隔，則兩個(gè)堡壘都會(huì)把對(duì)方打掉。問(wèn)對(duì)于給定的一種狀態(tài)，最多能夠修建幾個(gè)堡壘。程序主要部分如下：int main()r

5、eaddata(); /讀入數(shù)據(jù)search(0); /遞歸搜索printresult();void search(int m)int row, col;row=m/n; /求第m個(gè)格子的行號(hào)col=m%n; /求第m個(gè)格子的列號(hào)if(m>=n*n)checkmax(); /檢查當(dāng)前解是否是可行解，若是則把它的價(jià)值與max比較elsesearch(m+1); /該位置不放堡壘遞歸搜索下一個(gè)位置if(canplace(m) /判斷第m個(gè)格子是否能放堡壘place(m); /在第m個(gè)格子上放置一個(gè)堡壘search(m+1); /遞歸搜索下一個(gè)位置takeout(m); /去掉第m個(gè)格子上放置

6、的堡壘58皇后問(wèn)題在一個(gè)×的棋盤(pán)里放置個(gè)皇后，要求這8個(gè)皇后兩兩之間互相都不“沖突”。#include <stdio.h>#include <math.h>void search(int);void printresult(); /打印結(jié)果int canplace(int,int); /判斷該位置能否放置皇后void place(int,int); /在該位置能否放置皇后void takeout(int,int); /把該位置放置皇后去掉int a8; /ai存放第i個(gè)皇后的位置int main()search(0); /遞歸搜索void search(int

7、 m)int i;if(m>=8) /當(dāng)已經(jīng)找出一組解時(shí)printresult(); /輸出當(dāng)前結(jié)果elsefor(i=0;i<8;i+) /對(duì)當(dāng)前行0到7列的每一個(gè)位置if(canplace(m,i) /判斷第m個(gè)格子是否能放堡壘place(m,i); /在(m,i)格子上放置一個(gè)皇后search(m+1); /遞歸搜索下一行takeout(m,i); /把(m,i)格子上的皇后去掉int canplace(int row, int col)int i;for(i=0;i<row;i+)if(abs(i-row)=abs(ai-col)|ai=col)return(0);r

8、eturn(1);void place(int row, int col)arow=col;void takeout(int row, int col)arow=-1;void printresult()int i,j;for(i=0;i<8;i+)for(j=0;j<8;j+)if(ai=j)printf(" A ");elseprintf(" . ");printf("n");printf("n");6素?cái)?shù)環(huán)問(wèn)題把從1到20這20個(gè)數(shù)擺成一個(gè)環(huán)，要求相鄰的兩個(gè)數(shù)的和是一個(gè)素?cái)?shù)。分析：用回溯算法，考察

9、所有可能的排列。程序如下：#include <stdio.h>#include <math.h>void search(int);void init(); /初始化void printresult(); /打印結(jié)果int isprime(int); /判斷該數(shù)是否是素?cái)?shù)void swap(int,int); /交換am和aiint a21; /a數(shù)組存放素?cái)?shù)環(huán)int main()init();search(2); /遞歸搜索int isprime(int num)int i,k;k=sqrt(num);for(i=2;i<=k;i+)if(num%i=0)retu

10、rn(0);return(1);void printresult()int i;for(i=1;i<=20;i+)printf("%3d",ai);printf("n");void search(int m)int i;if(m>20) /當(dāng)已經(jīng)搜索到葉結(jié)點(diǎn)時(shí)if(isprime(a1+a20) /如果a1+a20也是素?cái)?shù)printresult(); /輸出當(dāng)前解return;elsefor(i=m;i<=20;i+) /(排列樹(shù))swap(m,i); /交換am和aiif(isprime(am-1+am) /判斷am-1+am是否是素

11、數(shù)search(m+1); /遞歸搜索下一個(gè)位置swap(m,i); /把a(bǔ)m和ai換回來(lái)void swap(int m, int i)int t;t=am;am=ai;ai=t;void init()int i;for(i=0;i<21;i+)ai=i;7迷宮問(wèn)題給一個(gè)20×20的迷宮、起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)，問(wèn)從起點(diǎn)是否能到達(dá)終點(diǎn)。輸入數(shù)據(jù)：.表示空格；X表示墻。程序如下：#include <stdio.h>#include <math.h>void search(int,int);int canplace(int,int);void readdata(

12、); /讀入數(shù)據(jù)void printresult(); /打印結(jié)果int a2020; /a數(shù)組存放迷宮int s,t;int main()int row, col;readdata();row=s/20;col=s%20;search(row,col); /遞歸搜索printresult();void search(int row, int col)int r,c;arowcol=1;r=row; /左c=col-1;if(canplace(r,c) /判斷(r,c)位置是否已經(jīng)走過(guò)search(r,c); /遞歸搜索(r,c)r=row+1; /下c=col;if(canplace(r,c

13、) /判斷(r,c)位置是否已經(jīng)走過(guò)search(r,c); /遞歸搜索(r,c)r=row; /右c=col+1;if(canplace(r,c) /判斷(r,c)位置是否已經(jīng)走過(guò)search(r,c); /遞歸搜索(r,c)r=row-1; /上c=col;if(canplace(r,c) /判斷(r,c)位置是否已經(jīng)走過(guò)search(r,c); /遞歸搜索(r,c)void printresult()int i,j;for(i=0;i<20;i+)for(j=0;j<20;j+)printf("%3d",aij);printf("n")

14、;void readdata()int i,j;for(i=0;i<20;i+)for(j=0;j<20;j+)scanf("%d",&aij);int canplace(int row, int col)if(row>=0&&row<20&&col>=0&&col<20&&arowcol=0)return 1;elsereturn 0;1.Floodfill給一個(gè)20×20的迷宮和一個(gè)起點(diǎn)坐標(biāo)，用廣度優(yōu)先搜索填充所有的可到達(dá)的格子。提示：參考第2題。2.電

15、子老鼠闖迷宮如下圖12×12方格圖，找出一條自入口（2，9）到出口（11，8）的最短路本題給出完整的程序和一組測(cè)試數(shù)據(jù)。狀態(tài)：老鼠所在的行、列。程序如下：#include<stdio.h>void readdata(); /讀入數(shù)據(jù)void init(); /初始化int search(); /廣搜，并在每一個(gè)可到達(dá)的每一個(gè)空格出填上最小步數(shù)int emptyopen(); /判棧是否為空：空：1；非空：0。int takeoutofopen(); /從棧中取出一個(gè)元素，并把該元素從棧中刪除int canmoveto(int,int,int*,int*,int); /判能

16、否移動(dòng)到該方向，并帶回坐標(biāo)(r,c)int isaim(int row, int col); /判斷該點(diǎn)是否是目標(biāo)int used(int,int); /判斷該點(diǎn)是否已經(jīng)走過(guò)void addtoopen(int,int); /把該點(diǎn)加入到open表int a1212; /a存放迷宮，0表示空格，-2表示墻。 /廣搜時(shí)，未找到目標(biāo)以前到達(dá)的空格，填上到達(dá)該點(diǎn)的最小步數(shù)int n; /n為迷宮邊長(zhǎng)，注：若大于12，必須修改一些參數(shù)，如a的大小int open20,head,tail,openlen=20; /open表int s,t; /起點(diǎn)和終點(diǎn)int main()int number;read

17、data(); /讀取數(shù)據(jù)init(); /初始化number=search(); /廣搜并返回最小步數(shù)printf("%d",number); /打印結(jié)果int search()int u, row, col, r, c, i, num;while(!emptyopen() /當(dāng)棧非空u=takeoutofopen(); /從棧中取出一個(gè)元素，并把該元素從棧中刪除row=u/n; /計(jì)算該點(diǎn)的坐標(biāo)col=u%n;num=arowcol; /取得該點(diǎn)的步數(shù)for(i=0;i<4;i+)if(canmoveto(row,col,&r,&c,i) /判能否

18、移動(dòng)到該方向，并帶回坐標(biāo)(r,c)if(isaim(r,c) /如果是目標(biāo)結(jié)點(diǎn)return(num+1); /返回最小步數(shù)if(!used(r,c) /如果(r,c)還未到達(dá)過(guò)arc=num+1; /記錄該點(diǎn)的最小步數(shù)addtoopen(r,c); /把該點(diǎn)加入到open表int emptyopen()if(head=tail)return(1);elsereturn(0);int takeoutofopen()int u;if(head=tail)printf("errer: stack is empty");return(-1);u=openhead+;head=hea

19、d%openlen;return(u);int canmoveto(int row, int col, int *p, int *q, int direction)int r,c;r=row;c=col;switch(direction)case 0: c-; /左break;case 1: r+; /下break;case 2: c+; /右break;case 3: r-; /上*p=r;*q=c;if(r<0|r>=n|c<0|c>=n) /如果越界返回0return(0);if(arc=0) /如果是空格返回1return(1);return(0); /其余情況

20、返回0int isaim(int row, int col)if(row*n+col=t)return(1);elsereturn(0);int used(int row, int col)if(arowcol=0) / 0表示空格return(0);elsereturn(1);void addtoopen(int row, int col)int u;u=row*n+col;opentail+= u;tail=tail%openlen;void readdata()int i,j,row,col;char str20;scanf("%d",&n);scanf(&q

21、uot;%d%d",&row,&col); /起點(diǎn)坐標(biāo)s=row*n+col;scanf("%d%d",&row,&col); /終點(diǎn)坐標(biāo)t=row*n+col;gets(str);for(i=0;i<n;i+)gets(str);for(j=0;j<n;j+)if(strj='.')aij=0; /0表示空格elseaij=-2; /2表示墻void init()head=0;tail=1;open0=s;測(cè)試數(shù)據(jù)如下：12 10 7 1 8XXXXXXXXXXXXX.X.XXXX.X.XX.XX.X.

22、XX.XXX.XX.X.X.XX.XXXXXXXXXXX.X.X.XX.XXX.XXXXX.X.XXXX.XXXX.X.XXXXXXXX.XXXXXXXXXXXXXXX注：測(cè)試數(shù)據(jù)可在運(yùn)行時(shí)粘貼上去（點(diǎn)擊窗口最左上角按鈕，在菜單中選則“編輯”/“粘貼”即可）。想一想：此程序都存在哪些問(wèn)題，如果openlen太小程序會(huì)不會(huì)出錯(cuò)，加入代碼使程序能自動(dòng)報(bào)出此類錯(cuò)誤。3.跳馬給一個(gè)200×200的棋盤(pán)，問(wèn)國(guó)際象棋的馬從給定的起點(diǎn)到給定的終點(diǎn)最少需要幾步。Sample Input 0 0 1 1 Sample output 4狀態(tài)：馬所在的行、列。程序如下：#include<stdio.

23、h>void readdata(); /讀入數(shù)據(jù)void init(); /初始化int search(); /廣度優(yōu)先搜索int emptyopen(); /判棧是否為空：空：1；非空：0。long takeoutofopen(); /從棧中取出一個(gè)元素，并把該元素從棧中刪除int canmoveto(int,int,int*,int*,int); /判能否移動(dòng)到該方向，并帶回坐標(biāo)(r,c)int isaim(int row, int col); /判斷該點(diǎn)是否是目標(biāo)int used(int,int); /判斷該點(diǎn)是否已經(jīng)走過(guò)void addtoopen(int,int); /把該點(diǎn)加

24、入到open表int a200200,n=200; /a存放棋盤(pán)，n為迷宮邊長(zhǎng)long open2000,head,tail,openlen=2000; /open表1367long s,t; /起點(diǎn)和終點(diǎn)int search()long u;int row, col, r, c, i, num;while(!emptyopen() /當(dāng)棧非空u=takeoutofopen(); /從棧中取出一個(gè)元素，并把該元素從棧中刪除row=u/n; /計(jì)算該點(diǎn)所在的行col=u%n; /計(jì)算該點(diǎn)所在的列num=arowcol; /取得該點(diǎn)的步數(shù)for(i=0;i<8;i+)if(canmoveto

25、(row,col,&r,&c,i) /判能否移動(dòng)到該方向，并帶回坐標(biāo)(r,c)if(isaim(r,c) /如果是目標(biāo)結(jié)點(diǎn)return(num+1); /返回最小步數(shù)if(!used(r,c) /如果(r,c)還未到達(dá)過(guò)arc=num+1; /記錄該點(diǎn)的最小步數(shù)addtoopen(r,c); /把該點(diǎn)加入到open表return -1;int main() /為了讓search()顯示在一頁(yè)內(nèi)和main函數(shù)換了以下 /一般的算法程序main函數(shù)寫(xiě)在最上面讀起來(lái)更方便int number;readdata(); /讀取數(shù)據(jù)init(); /初始化number=search();

26、/廣搜并返回最小步數(shù)printf("%d",number); /打印結(jié)果int emptyopen()if(head=tail)return(1);elsereturn(0);long takeoutofopen()long u;if(head=tail)printf("errer: stack is empty");return(-1);u=openhead+;head=head%openlen;return(u);int used(int row, int col)if(arowcol=0)return(0);elsereturn(1);void a

27、ddtoopen(int row, int col)int u;if(head-tail)%openlen=1)printf("open table overflow");u=row;u=u*n+col;opentail+= u;tail=tail%openlen;void readdata()long row,col;scanf("%ld%ld",&row,&col); /起點(diǎn)坐標(biāo)s=row*n+col;scanf("%ld%ld",&row,&col); /終點(diǎn)坐標(biāo)t=row*n+col;void

28、init()head=0;tail=1;open0=s;int isaim(int row, int col)if(row*n+col=t)return(1);elsereturn(0);思考：參考第4題，改為用結(jié)構(gòu)體表示狀態(tài)寫(xiě)此程序。4.獨(dú)輪車獨(dú)輪車的輪子上有5種顏色，每走一格顏色變化一次，獨(dú)輪車只能往前推，也可以在原地旋轉(zhuǎn)，每走一格，需要一個(gè)單位的時(shí)間，每轉(zhuǎn)90度需要一個(gè)單位的時(shí)間，轉(zhuǎn)180度需要兩個(gè)單位的時(shí)間?，F(xiàn)給定一個(gè)20×20的迷宮、一個(gè)起點(diǎn)、一個(gè)終點(diǎn)和到達(dá)終點(diǎn)的顏色，問(wèn)獨(dú)輪車最少需要多少時(shí)間到達(dá)。狀態(tài)：獨(dú)輪車所在的行、列、當(dāng)前顏色、方向。另外為了方便在結(jié)點(diǎn)中加上到達(dá)該點(diǎn)的

29、最小步數(shù)。程序如下：#include<stdio.h>struct colornodeint row; /該狀態(tài)的行int col; / 列int color; / 顏色int direction; / 方向int num; / 最小步數(shù);int search(); /廣搜返回目標(biāo)結(jié)點(diǎn)的最小步數(shù)void readdata(); /讀入數(shù)據(jù)void init(); /初始化struct colornode moveahead(struct colornode u); /返回u向前走一格得到的結(jié)點(diǎn)int used(struct colornode v); /判斷該結(jié)點(diǎn)是否是到達(dá)過(guò)的結(jié)點(diǎn)

30、void addtoopen(struct colornode v); /加入到open表int islegal(struct colornode v); /如果該結(jié)點(diǎn)是合法的結(jié)點(diǎn)(未越界且是空格)int isaim(struct colornode v); /判斷該結(jié)點(diǎn)是否是目標(biāo)結(jié)點(diǎn)struct colornode takeoutofopen(); /從open表中取出一個(gè)結(jié)點(diǎn)并把該結(jié)點(diǎn)從open表中刪除struct colornode turntoleft(struct colornode u); /u向左轉(zhuǎn)得到新結(jié)點(diǎn)vstruct colornode turntoright(struct

31、 colornode u); /u向左轉(zhuǎn)得到新結(jié)點(diǎn)vstruct colornode s,t; /s:起始結(jié)點(diǎn)；t目標(biāo)結(jié)點(diǎn)struct colornode open200; /open表int head,tail,openlen=200; /open表相關(guān)數(shù)據(jù)int direct42=0,-1,1,0,0,1,-1,0;/向左、下、右、上四個(gè)方向轉(zhuǎn)時(shí)，行列的增加值int a2020,n=20; /a數(shù)組表示迷宮；n為迷宮邊長(zhǎng)int b202054; /b數(shù)組表示搜索時(shí)的所有狀態(tài)(0：未訪問(wèn)；1：已訪問(wèn))int main()int number;readdata();init();number=

32、search();printf("%dn",number);int search() /廣搜返回目標(biāo)結(jié)點(diǎn)的最小步數(shù)struct colornode u,v;while(head!=tail)u=takeoutofopen();v=moveahead(u); /u向前走一格得到新結(jié)點(diǎn)vif(islegal(v) /如果該結(jié)點(diǎn)是合法的結(jié)點(diǎn)(未越界且是空格)if(isaim(v) /判是否是目標(biāo)結(jié)點(diǎn)return(v.num);if(!used(v) /如果是未到達(dá)過(guò)的結(jié)點(diǎn)addtoopen(v); /加入到open表v=turntoleft(u); /u向左轉(zhuǎn)得到新結(jié)點(diǎn)vif(!

33、used(v)addtoopen(v);v=turntoright(u); /u向右轉(zhuǎn)得到新結(jié)點(diǎn)vif(!used(v)addtoopen(v);int used(struct colornode v) /判斷該結(jié)點(diǎn)是否是到達(dá)過(guò)的結(jié)點(diǎn)if(bv.rowv.colv.colorv.direction=0)return(0);elsereturn(1);void addtoopen(struct colornode v) /加入到open表opentail+=v;tail=tail%openlen;bv.rowv.colv.colorv.direction=1;struct colornode t

34、akeoutofopen() /從open表中取出一個(gè)結(jié)點(diǎn)并把該結(jié)點(diǎn)從open表中刪除struct colornode v;v=openhead+;head=head%openlen;return(v);void init() /初始化int i,j,k,l;for(i=0;i<n;i+) /所有狀態(tài)初始化for(j=0;j<n;j+)for(k=0;k<5;k+)for(l=0;l<4;l+)bijkl=0;head=0;tail=0;addtoopen(s); /把起始點(diǎn)加入到open表void readdata() /讀入數(shù)據(jù)char str50;int i,j;

35、for(i=0;i<n;i+)gets(str);for(j=0;j<n;j+)if(strj='.') /讀入數(shù)據(jù)'.'表示空格aij=0; /存儲(chǔ)時(shí) 0：表示空格elseaij=1; / 1：表示墻scanf("%d%d%d%d",&s.row,&s.col,&s.color,&s.direction); /讀入起始結(jié)點(diǎn)信息scanf("%d%d%d",&t.row,&t.col,&t.color); /讀入目標(biāo)結(jié)點(diǎn)信息int isaim(struct

36、 colornode v) /判斷該結(jié)點(diǎn)是否是目標(biāo)結(jié)點(diǎn)if(v.row=t.row&&v.col=t.col&&v.color=t.color)return 1;elsereturn 0;int islegal(struct colornode v) /如果該結(jié)點(diǎn)是合法的結(jié)點(diǎn)(未越界且是空格)if(v.row<0|v.row>=n|v.col<0|v.col>=n) /若越界return 0;if(av.rowv.col=0) /0：表示空格return 1;return 0;struct colornode moveahead(stru

37、ct colornode u) /返回u向前走一格得到的結(jié)點(diǎn)struct colornode v;v.row=u.row+directu.direction0;v.col=u.col+directu.direction1;v.color=(u.color+1)%5;v.direction=u.direction;v.num=u.num+1;return(v);struct colornode turntoleft(struct colornode u) /u向左轉(zhuǎn)得到新結(jié)點(diǎn)vstruct colornode v;v=u;v.direction=(v.direction+1)%4;v.num=v

38、.num+1;return(v);struct colornode turntoright(struct colornode u) /u向左轉(zhuǎn)得到新結(jié)點(diǎn)vstruct colornode v;v=u;v.direction=(v.direction+3)%4;v.num=v.num+1;return(v);測(cè)試數(shù)據(jù)：XXXXXXXXXXXXXXXXXXXX.XXXX.X.XXXX.X.XX.XX.XXX.XX.X.XX.XXX.XX.X.XX.XX.XXX.XX.X.XX.XXX.X.X.XX.X.X.XX.X.X.X.X.X.XXXX.X.XXX.XXXX.X.XXXXXXX.XXXXXX.

39、XX.X.X.X.XX.X.X.XXXXXXX.XXXXXXXX.XX.X.X.X.X.X.XXXX.X.XXX.XXXX.X.XXXX.X.XXXXX.XXXX.X.X.X.XX.XXX.XXXX.XX.1 1 1 1 4 8 11最長(zhǎng)公共子序列一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說(shuō)，若給定序列X=<x1, x2, xm>，則另一序列Z=<z1, z2, zk>是X的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列 <i1, i2, ik>，使得對(duì)于所有j=1,2,k有答如下：a) 最長(zhǎng)公共子序列的結(jié)構(gòu)若用窮舉搜索法，耗時(shí)太長(zhǎng)，算法需要指數(shù)

40、時(shí)間。易證最長(zhǎng)公共子序列問(wèn)題也有最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)序列X=<x1, x2, , xm>和Y=<y1, y2, , yn>的一個(gè)最長(zhǎng)公共子序列Z=<z1, z2, , zk>，則：i.若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列； ii.若xmyn且zkxm ，則Z是Xm-1和Y的最長(zhǎng)公共子序列； iii.若xmyn且zkyn ，則Z是X和Yn-1的最長(zhǎng)公共子序列。 其中Xm-1=<x1, x2, , xm-1>，Yn-1=<y1, y2, , yn-1>，Zk-1=<z1, z2, , zk-1&

41、gt;。最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。b) 子問(wèn)題的遞歸結(jié)構(gòu)由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出X=<x1, x2, , xm>和Y=<y1, y2, , yn>的最長(zhǎng)公共子序列，可按以下方式遞歸地進(jìn)行：當(dāng)xm=yn時(shí)，找出Xm-1和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上x(chóng)m(=yn)即可得X和Y的一個(gè)最長(zhǎng)公共子序列。當(dāng)xmyn時(shí)，必須解兩個(gè)子問(wèn)題，即找出Xm-1和Y的一個(gè)最長(zhǎng)公共子序列及X和Yn-1的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者即為X和Y的一個(gè)最長(zhǎng)公共子序列。由此遞歸結(jié)構(gòu)容易看到最長(zhǎng)公共子序列問(wèn)題具有子問(wèn)題重疊性質(zhì)。例如，在計(jì)算

42、X和Y的最長(zhǎng)公共子序列時(shí)，可能要計(jì)算出X和Yn-1及Xm-1和Y的最長(zhǎng)公共子序列。而這兩個(gè)子問(wèn)題都包含一個(gè)公共子問(wèn)題，即計(jì)算Xm-1和Yn-1的最長(zhǎng)公共子序列。我們來(lái)建立子問(wèn)題的最優(yōu)值的遞歸關(guān)系。用ci,j記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中Xi=<x1, x2, , xi>，Yj=<y1, y2, , yj>。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列，故ci,j=0。建立遞歸關(guān)系如下：c) 計(jì)算最優(yōu)值由于在所考慮的子問(wèn)題空間中，總共只有(m*n)個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。計(jì)算最長(zhǎng)公共子序列長(zhǎng)度的動(dòng)

43、態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=<x1, x2, , xm>和Y=<y1, y2, , yn>作為輸入。輸出兩個(gè)數(shù)組c0.m ,0.n和b1.m ,1.n。其中ci,j存儲(chǔ)Xi與Yj的最長(zhǎng)公共子序列的長(zhǎng)度，bi,j記錄指示ci,j的值是由哪一個(gè)子問(wèn)題的解達(dá)到的，這在構(gòu)造最長(zhǎng)公共子序列時(shí)要用到。最后，X和Y的最長(zhǎng)公共子序列的長(zhǎng)度記錄于cm,n中。程序如下：#include<stdio.h>#include<string.h>int lcs_length(char x, char y);int main()char x100,y10

44、0;int len;while(1)scanf("%s%s",x,y);if(x0='0') /約定第一個(gè)字符串以0開(kāi)始表示結(jié)束break;len=lcs_length(x,y);printf("%dn",len);int lcs_length(char x, char y )int m,n,i,j,l100100;m=strlen(x);n=strlen(y);for(i=0;i<m+1;i+)li0=0;for(j=0;j<n+1;j+)l0j=0;for(i=1;i<=m;i+)for(j=1;j<=n;j+

45、)if(xi-1=yj-1) /i,j從1開(kāi)始，但字符串是從0開(kāi)始lij=li-1j-1+1;else if(lij-1>li-1j)lij=lij-1;elselij=li-1j;return lmn;由于每個(gè)數(shù)組單元的計(jì)算耗費(fèi)(1)時(shí)間，算法lcs_length耗時(shí)(mn)。思考：空間能節(jié)約嗎？2計(jì)算矩陣連乘積在科學(xué)計(jì)算中經(jīng)常要計(jì)算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數(shù)等于矩陣B的行數(shù)。若A是一個(gè)p×q的矩陣，B是一個(gè)q×r的矩陣，則其乘積C=AB是一個(gè)p×r的矩陣。由該公式知計(jì)算C=AB總共需要pqr次的數(shù)乘。其標(biāo)準(zhǔn)計(jì)算公式為： 現(xiàn)在的問(wèn)題是，給定n個(gè)矩陣A1,A2,An。其中Ai與Ai+1是可乘的，i=1,2,n-1。要求計(jì)算出這n個(gè)矩陣的連乘積A1A2An。遞歸公式： 程序如下：#include<stdio.h>int main()int p101,i,j,k,r,t,n;int m101101; /為了跟講解時(shí)保持一致數(shù)組從1開(kāi)始int s101101; /記錄從第i到第j個(gè)矩陣連乘的斷開(kāi)位置scanf("%d",&n);for(i=0;i<=n;i+) s