算法实验之矩阵连乘-实验报告.doc

算法实验之矩阵连乘-实验报告.doc

《算法实验之矩阵连乘-实验报告.doc》由会员分享，可在线阅读，更多相关《算法实验之矩阵连乘-实验报告.doc（3页珍藏版）》请在冰点文库上搜索。

攀枝花学院实验报告册

课程名称计算机算法设计与分析

院系数学与计算机学院

班级2012级信息与计算科学

姓名杨腾佼

学号201210802025

授课教师鄢莉

教务处制

《算法设计与分析》实验报告（三）

学号：

201210802025姓名：

杨腾佼班级：

信本成绩：

实验名称：

矩阵连乘问题

实验地点：

6a-2

所使用的开发工具及环境：

Visualc++6.0,windows7

一、实验目的

熟悉掌握动态规划法设计技术

二、实验要求

1、按教材所授内容要求，完成“矩阵连乘问题”算法。

得到一个完整正确的程序。

2、问题规模：

不少于20

3、输出最终结果。

三、算法实现

#include

#include

#defineMAX_MATRIXNUM100

#defineMAX_VALUE32767

Intp[MAX_MATRIXNUM+1],m[MAX_MATRIXNUM+1][MAX_MATRIXNUM+1],s[MAX_MATRIXNUM+1][MAX_MATRIXNUM+1];

staticvoidmatrix_chain（intnum）;

staticvoidtraceback（inti,intj）;

intmain（intargc,char**argv）{

inti,num;

printf（"Inputmatrixnum:

"）;

scanf（"%d",&num）;

getchar（）;

printf（"Inputmatrixsubscript:

"）;

for（i=0;i<=num;i++）{

scanf（"%d",&p[i]）;}

getchar（）;

matrix_chain（num）;

traceback（1,num）;

printf（"\n"）;

return0;

}

staticvoidmatrix_chain（intnum）{

inti,j,l,k,n,temp;

n=num;

for（i=1;i<=n;i++）{

m[i][i]=0;

}

for（l=2;l<=n;l++）{

for（i=1;i<=n-l+1;i++）{

j=i+l-1;

m[i][j]=MAX_VALUE;

for（k=i;k

temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

if（temp

m[i][j]=temp;

s[i][j]=k;

}

}}

}

printf（"Thelowestcomputetimes=%d\n",m[1][num]）;

}

staticvoidtraceback（inti,intj）{

if（i==j）{

printf（"A%d",i）;

}

if（i

printf（"（"）;

traceback（i,s[i][j]）;

traceback（s[i][j]+1,j）;

printf（"）"）;

}

}

运行结果如下：

四、算法思想

矩阵乘法满足结合律，所以计算矩阵的连乘积可以有不同的计算次序，若一个矩阵的计算次序完全确定，那么矩阵连乘积可以递归地定义为：

单个矩阵是完全加括号的；矩阵连乘积A是完全加括号的，则A可以表示成2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）

五、实验结论

本次实验是动态规划的一个应用，矩阵连乘问题主要就是确定矩阵连乘的次序，使得矩阵连乘的次数最少。

指导教师签名：

2014年12月11日