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

《動(dòng)態(tài)規(guī)劃算法實(shí)驗(yàn)報(bào)告.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、實(shí)驗(yàn)標(biāo)題1、矩陣連乘2、最長(zhǎng)公共子序列3、最大子段和4、凸多邊形最優(yōu)三角剖分5、流水作業(yè)調(diào)度6、0-1背包問(wèn)題7、最優(yōu)二叉搜索樹(shù)實(shí)驗(yàn)?zāi)康恼莆談?dòng)態(tài)規(guī)劃法的基本思想和算法設(shè)計(jì)的基本步驟。實(shí)驗(yàn)內(nèi)容與源碼1、矩陣連乘#include#includeusingnamespacestd;constintsize=4;//ra,ca和rb,cb分別表示矩陣A和B的行數(shù)和列數(shù)voidmatriMultiply(inta[][4],intb[][4],intc[][4],intra,intc

2、a,intrb,intcb){if(ca!=rb)cerr<<"矩陣不可乘";for(inti=0;i

3、++)//外維for(inti=1;i<=n-r+1;i++)//上三角{intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k

4、i+1==j){cout<<"(A"<>w;intp[w],s[w][w];cout<<"輸入矩陣A1維數(shù)：";cin>>p[0]>>p[1];for(inti=2;i<=w;i++){intm=p[i-1];cout<<"輸入矩陣A"<

5、>p[i-1]>>p[i];if(p[i-1]!=m){cout<#include#defineN100usingnamespacestd;//str1存儲(chǔ)字符串x，str2存儲(chǔ)字符串ycharstr1[N],str2[N];//lcs存儲(chǔ)最長(zhǎng)公共子序列charlcs[N];//c[i][j]存儲(chǔ)str1[1

6、...i]與str2[1...j]的最長(zhǎng)公共子序列的長(zhǎng)度intc[N][N];//flag[i][j]==0為str1[i]==str2[j]//flag[i][j]==1為c[i-1][j]>=s[i][j-1]//flag[i][j]==-1為c[i-1][j]

7、i][0]=0;for(i=0;i<=n;i++)c[0][i]=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;flag[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];flag[i][j]=1;}else{c[i][j]=c[i][j-1];flag[i][j]=-1;}}returnc[m][n];}//求出最長(zhǎng)公共子序列char*ge

8、tLCS(char*x,char*y,intlen,char*lcs){inti=strlen(x);intj=strlen(y);while(i&&j){if(flag[i][j]==0){lcs[--len]=x[i-1];i--;j--;}elseif(flag[i][j]==1)i--;elsej--;}returnlcs;}intmain(){inti;cout<<"請(qǐng)輸入字