動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)報(bào)告.doc

ID:57413694

大?。?2.50 KB

頁數(shù):3頁

時(shí)間:2020-08-16

動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)報(bào)告.doc_第1頁
動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)報(bào)告.doc_第2頁
動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)報(bào)告.doc_第3頁
資源描述:

《動(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)移一般。

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無此問題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。
关闭