動態(tài)規(guī)劃算法實驗報告(已修改)
2025-08-03 00:25 本頁面
【正文】 實驗標題 矩陣連乘 最長公共子序列 最大子段和 凸多邊形最優(yōu)三角剖分 流水作業(yè)調(diào)度 01背包問題 最優(yōu)二叉搜索樹實驗目的掌握動態(tài)規(guī)劃法的基本思想和算法設計的基本步驟。實驗內(nèi)容與源碼 矩陣連乘includeiostreamincludecstdlibusing namespace std。const int size=4。//ra,ca和rb,cb分別表示矩陣A和B的行數(shù)和列數(shù)void matriMultiply(int a[][4],int b[][4],int c[][4],int ra ,int ca,int rb ,int cb ){ if(ca!=rb) cerr矩陣不可乘。 for(int i=0。ira。i++) for(int j=0。jcb。j++) { int sum=a[i][0]*b[0][j]。 for(int k=1。kca。k++) sum+=a[i][k]*b[k][j]。 c[i][j]=sum。 }}void MatrixChain(int *p,int n,int m[][4],int s[][4]){ for(int i=1。i=n。i++) m[i][i]=0。//對角線 for(int r=2。r=n。r++)//外維 for(int i=1。i=nr+1。i++)//上三角 { int j=i+r1。 m[i][j]=m[i+1][j]+p[i1]*p[i]*p[j]。 s[i][j]=i。 for(int k=i+1。kj。k++) { int t=m[i][k]+m[k+1][j]+p[i1]*p[k]*p[j]。 if(tm[i][j]) { m[i][j]=t。 s[i][j]=k。 } } }}void Traceback(int i,int j,int s[][4]){ if(i == j) { coutAi。 } else if(i+1 == j) { cout(AiAj)。 } else { cout(。 Traceback(i,s[i][j],s)。 Traceback(s[i][j]+1,j,s)。 cout)。 }}int main(){ int w。 cout矩陣個數(shù)：。 cinw。 int p[w],s[w][w]。 cout輸入矩陣A1維數(shù)：。 cinp[0]p[1]。 for(int i=2 。 i=w 。 i++) { int m = p[i1]。 cout輸入矩陣Ai維數(shù)：。 cinp[i1]p[i]。 if(p[i1] != m) { coutendl維數(shù)不對，矩陣不可乘！endl。 exit(1)。 } } Traceback(1,w,s)。 return 0。}運行結果 最長公共子序列includecstringincludeiostreamdefine N 100using namespace std。//str1存儲字符串x，str2存儲字符串ychar str1[N],str2[N]。//lcs存儲最長公共子序列char lcs[N]。//c[i][j]存儲str1[1...i]與str2[1...j]的最長公共子序列的長度int c[N][N]。//flag[i][j]==0為str1[i]==str2[j]//flag[i][j]==1為c[i1][j]=s[i][j1]//flag[i][j]==1為c[i1][j]s[i][j1]int flag[N][N]。//求長度int LCSLength(char *x, char *y){ int i,j。 //分別取得x,y的長度 int m = strlen(x)。 int n = strlen(y)。 for(i=1。i=m。i++) c[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[i1]==y[j1]) { c[i][j] = c[i1][j1] +1。 flag[i][j] = 0。 } else if(c[i1][j]=c[i][j1]) { c[i][j] = c[i1][j]。 flag[i][j] = 1。
公司管理相關推薦
鄂ICP備17016276號-1