实验一、矩阵连乘问题与答案

《实验一、矩阵连乘问题与答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验一、矩阵连乘问题问题描述与实验目的：给定n个矩阵A1，A2，…，An，其中，Ai与Aj+1是可乘的，i=1，2，…，n-l。你的任务是要确定矩阵连乘的运算次序，使计算这n个矩阵的连乘积A1A2…An时总的元素乘法次数达到最少。例如：3个矩阵A1，A2，A3，阶分别为10×100、100×5、5×50，计算连乘积A1A2A3时按（A1A2）A3所需的元素乘法次数达到最少，为7500次。输入测试数据有若干组，每组测试数据有2行。每组测试数据的第1行是一个整数n，（0

2、不超过100，相邻两个整数之间空一格，他们表示n个矩阵A1，A2，…，An，的阶pi-1´pi，i=1，2，…，n。输入直到文件结束。输出对输入中的每组测试数据，输出2行。先在一行上输出“Case#”，其中“#”是测试数据的组号（从1开始），再在第2行上输出计算这n个矩阵的连乘积A1A2…An时最少的总的元素乘法次数，再空一格，接着在同一行上输出矩阵连乘的添括号形式。注意：最外层括号应去掉。实验结果：输入样例3101005504501040305输出样例Case17500(A1A2)A3Case210500A1(A2(A3A4))实验报

3、告要求:1．先分析要点、写出动态方程2．提供能正确运行的程序。要有一般性，即可同时处理若干组数据，每组2行。3．设计、调试中的问题及实验体会。#include#include#defineMAXLEN50usingnamespacestd;voidLCSLength(char*x,char*y,intm,intn,intc[][MAXLEN],intb[][MAXLEN]){inti,j;for(i=0;i<=m;i++)c[i][0]=0;for(j=1;j<=n;j++)c[0][i]=0;f

4、or(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;}else{c[i][j]=c[i][j-1];b[i][j]=-1;}}}}voidLCS(intb[][MAXLEN],char*x,inti,intj){if(i==0

5、

6、j==0)return;if(b[i][j]==0){LCS(b,x,i-1

7、,j-1);cout<>t;while(f>m>>n;for(i=0;i>x[i];}for(i=0;i>y[i];}if(

8、m