攀枝花学院实验报告
实验课程：计算机算法实验 实验项目：矩阵连乘 实验日期：2013.4.9
系：数学与计算机学院 班级：软件工程 姓名：冯斌 学号：201010804004
指导教师：银星 成绩：
【实验目的：】
1. 利用动态规划掌握矩阵连乘算法，计算矩阵连乘最优次序。
2. 掌握用备忘录方法计算矩阵连乘最优次序。
3. 掌握vc++6.0环境下程序的编写和调试。
【实验设备器材：】
1. pc机一套
2. vc++6.0相应编译软件
【实验原理：】
【实验内容：】
1. 编写相应算法源程序
2. 在vc++6.0环境下调试通过
3. 运行程序计算最优次序。
程序代码如下：
#include <iostream>
using namespace std;
#define N 100
int n,q;
int m[N][N],s[N][N],p[N+1];
void matrixChain()
{ //动态规划计算最优值算法
for(int i=1;i<=n;i++)
{
m[i][i]=0;
}
for(int r=2;r<=n;r++)
{ //对角线循环
for(int i=1;i<=n-r+1;i++)
{ //行循环
int j = r+i-1; //列的控制,找m[i][j]的最小值，先初始化一下，令k=i
m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i; //k从i+1到j-1循环找m[i][j]的最小值
for(int k = i+1;k<j;k++)
{
int temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(temp<m[i][j])
{
m[i][j]=temp; //s[][]用来记录在子序列i-j段中，在k位置处断开能得到最优解
s[i][j]=k;
}
}
}
}
}
int Recur(int i, int j) //直接递归计算最优值
{
if (i == j){
return 0;
}
int u = Recur(i,i)+Recur(i+1,j)+p[i-1]*p[i]*p[j]; //递归
s[i][j] = i;
for (int k=i+1; k<j; k++)
{
int t=Recur(i,k)+Recur(k+1,j)+p[i-1]*p[k]*p[j];//从k处断开，分别求得每次的数乘次数
if (t<u) //返回t,k中较小的值，并记录断点处k
{
u=t;
s[i][j]=k;
}
}
return u;
}
int Look(int i,int j) //备忘录计算最优值
{
if (m[i][j]>0)
{
return m[i][j];
}
if (i == j)
return 0;
int u=Look(i, i)+Look(i+1,j)+p[i-1]*p[i]*p[j];
s[i][j]=i;
for (int k=i+1; k<j;k++)
{
int t=Look(i,k)+Look(k+1,j)+p[i-1]*p[k]*p[j]; //递归
if (t<u)
{
u=t; //从k处断开，分别求得每次的数乘次数
s[i][j]=k; //返回t,k中较小的值，并记录断点处k
}
}
m[i][j]=u;
return u;
}
void Traceback(int i,int j)
{ //输出矩阵结合方式，加括号输出
if(i == j) //只有一个矩阵，直接输出
{
cout<<"A"<<i;
}
else if(i+1 == j) //两个矩阵，加括号输出
{
cout<<"(A"<<i<<"A"<<j<<")";
}
else
{
cout<<"(";
Traceback(i,s[i][j]); //递归，从最得到最优解的地方s[i][j]处断开
Traceback(s[i][j]+1,j);
cout<<")";
}
}
void main()
{
cout<<"输入矩阵个数：n=";
cin>>n;
cout<<"输入第一个矩阵行数和第一个到第n个矩阵的列数：";
for(int i=0;i<=n;i++)
{
cin>>p[i];
}
cout<<endl;
cout<<"请选择解决矩阵连乘问题的方法："<<endl;
cout<<"1.动态规划算法"<<endl;
cout<<"2.直接递归算法"<<endl;
cout<<"3.备忘录算法"<<endl;
cout<<"0.退出..."<<endl;
cout<<endl;
cout<<"请选择算法：";
cin>>q;
cout<<endl;
while(q!=0){
switch(q){
case 1:
matrixChain();
cout<<"动态规划算法解决矩阵连乘问题："<<endl;
cout<<"最优计算次序为：";
Traceback(1,n);
cout<<endl;
cout<<"矩阵连乘的最优数乘次数为："<<m[1][n]<<endl; //最终解值为m[1][n]
break;
case 2:
Recur(0,n);
cout<<"直接递归算法解决矩阵连乘问题："<<endl;
cout<<"最优计算次序为：";
Traceback(1,n);
cout<<endl;
cout<<"矩阵连乘的最优数乘次数为："<<m[1][n]<<endl; //最终解值为m[1][n]
break;
case 3:
Look(1,n);
cout<<"备忘录算法解决矩阵连乘问题："<<endl;
cout<<"最优计算次序为：";
Traceback(1,n);
cout<<endl;
cout<<"矩阵连乘的最优数乘次数为："<<m[1][n]<<endl; //最终解值为m[1][n]
break;
case 0:
q=0;
break;
}
cout<<endl;
cout<<"请选择解决矩阵连乘问题的方法："<<endl;
cout<<"1.动态规划算法"<<endl;
cout<<"2.直接递归算法"<<endl;
cout<<"3.备忘录算法"<<endl;
cout<<"0.退出..."<<endl;
cout<<"请选择算法：";
cin>>q;
cout<<endl;
}
cout<<endl;
}
程序调试运行结果：
实验总结：
通过本次实验，对于在vc++6.0的编译，以及各种算法的实现有了更深入的了解和掌握，通过对矩阵连乘动态规划法以及备忘录等方法的实现，对它们的原理有了更多的了解，在以后的编程过程中，是很宝贵的经验。在本次实验中，借助了很多的资料帮助，自己在以后的学习中，还有很多方面需要提高。
第二篇：实验六 矩阵连乘和最长公共子序列问题算法设计
宁夏师范学院数学与计算机科学学院
《算法分析与设计》实验报告
实验序号：6 实验项目名称：矩阵连乘和最长公共子序列问题算法设计
