資源描述:
《動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)報(bào)告.doc》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、實(shí)驗(yàn)課程:算法分析與設(shè)計(jì)實(shí)驗(yàn)名稱:實(shí)驗(yàn)3動(dòng)態(tài)規(guī)劃算法(綜合性/設(shè)計(jì)性)實(shí)驗(yàn)?zāi)繕?biāo):1、熟悉最長公共子序列問題的算法;2、初步掌握動(dòng)態(tài)規(guī)劃算法;實(shí)驗(yàn)任務(wù):若給定序列X={x1,x2,…,xm},則另一序列Z={z1,z2,…,zk},是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對(duì)于所有j=1,2,…,k有:zj=xij。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相應(yīng)的遞增下標(biāo)序列為{2,3,5,7}。給定2個(gè)序列X和Y,當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)
2、,稱Z是序列X和Y的公共子序列。給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最長公共子序列。?實(shí)驗(yàn)設(shè)備及環(huán)境:PC;C/C++的編程環(huán)境VisualC++。實(shí)驗(yàn)主要步驟:(1)明確實(shí)驗(yàn)?zāi)繕?biāo)和具體任務(wù);(2)理解實(shí)驗(yàn)所涉及的動(dòng)態(tài)規(guī)劃算法;(3)編寫程序并實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法;(4)設(shè)計(jì)實(shí)驗(yàn)數(shù)據(jù)并運(yùn)行程序、記錄運(yùn)行的結(jié)果;實(shí)驗(yàn)數(shù)據(jù)及運(yùn)行結(jié)果、實(shí)驗(yàn)結(jié)果分析及結(jié)論:(學(xué)生填寫)#include#includevoidLcsLength(char*x,cha
3、r*y,intm,intn,intc[][100],intb[][100]){puts(x);puts(y);inti,j;for(i=0;i<=m;i++)c[i][0]=0;for(j=1;i<=n;j++)c[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=1;}el
4、se{c[i][j]=c[i][j-1];b[i][j]=-1;}}}voidPrintLCS(intb[][100],char*x,inti,intj){if(i==0
5、
6、j==0)return;if(b[i][j]==0){PrintLCS(b,x,i-1,j-1);printf("%c",x[i-1]);}elseif(b[i][j]==1)PrintLCS(b,x,i-1,j);elsePrintLCS(b,x,i,j-1);}voidmain(){charx[100]={"ABCBDAB"};chary[100
7、]={"BDCABA"};intc[100][100];intb[100][100];intm,n;m=strlen(x);n=strlen(y);LcsLength(x,y,m,n,c,b);printf("最長子序列為:");PrintLCS(b,x,m,n);printf("");printf("最長子序列長度為:%d",c[m][n]);}實(shí)驗(yàn)結(jié)果:結(jié)果分析:在寫規(guī)劃方程時(shí),只要對(duì)兩條路徑走到同一個(gè)點(diǎn)的情況稍微處理一下,減少可選的決策個(gè)數(shù):從這個(gè)例子中可以總結(jié)出設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的一個(gè)技巧:狀態(tài)轉(zhuǎn)移一般。