實驗一、矩陣連乘問題與答案

1、實驗一、矩陣連乘問題問題描述與實驗?zāi)康模?給定n個矩陣A1，A2，An，其中，Ai與Aj+1是可乘的，i=1，2，n-l。你的任務(wù)是要確定矩陣連乘的運算次序，使計算這n個矩陣的連乘積A1A2An時總的元素乘法次數(shù)達(dá)到最少。例如：3個矩陣A1，A2，A3，階分別為10100、1005、550，計算連乘積A1A2A3時按（A1A2）A3所需的元素乘法次數(shù)達(dá)到最少，為7500次。輸入測試數(shù)據(jù)有若干組，每組測試數(shù)據(jù)有2行。每組測試數(shù)據(jù)的第1行是一個整數(shù)n，（0n20），第2行是n+1個正整數(shù)p0、p1、p2、pn，這些整數(shù)不超過100，相鄰兩個整數(shù)之間空一格，他們表示n個矩陣A1，A2，An，的階pi

2、-1pi，i=1，2，n。輸入直到文件結(jié)束。輸出對輸入中的每組測試數(shù)據(jù)，輸出2行。先在一行上輸出“Case #”，其中“#”是測試數(shù)據(jù)的組號（從1開始），再在第2行上輸出計算這n個矩陣的連乘積A1A2An時最少的總的元素乘法次數(shù)，再空一格，接著在同一行上輸出矩陣連乘的添括號形式。注意：最外層括號應(yīng)去掉。實驗結(jié)果：輸入樣例310 100 5 50450 10 40 30 5輸出樣例Case 17500 (A1A2)A3Case 210500 A1(A2(A3A4)實驗報告要求: 1先分析要點、寫出動態(tài)方程2提供能正確運行的程序。要有一般性，即可同時處理若干組數(shù)據(jù)，每組2行。3設(shè)計、調(diào)試中的問題及

3、實驗體會。#include#include#define MAXLEN 50using namespace std;void LCSLength(char *x,char *y,int m,int n,int cMAXLEN,int bMAXLEN)int i,j;for(i=0;i=m;i+) ci0=0;for(j=1;j=n;j+) c0i=0;for(i=1;i=m;i+) for(j=1;j=cij-1) cij=ci-1j; bij=1; else cij=cij-1; bij=-1; void LCS(int bMAXLEN,char *x,int i,int j)if(i=0|j=0) return;if(bij=0) LCS(b,x,i-1,j-1); coutxi-1t; while(fmn; for(i=0;ixi; for(i=0;iyi;if(mn)LCSLength(y,x,n,m,c,b);coutCase +kendl; coutcnm ; coutLCS(X,Y):;LCS(b,y,n,m); else LCSLength(x,y,m,n,c,b); coutCase +ken