算法设计与分析实验报告华北电力大学

《算法设计与分析实验报告华北电力大学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华北电力大学实验报告

2、

3、实验名称算法设计与分析实验课程名称算法设计与分析

4、

5、专业班级：计科1203学生姓名：学号：成绩：指导教师：牛为华实验日期：2014年10月实验一、矩阵连乘一、实验目的及要求1、了解并掌握动态规划算法解矩阵连乘问题的原理；2、通过上机实验，对矩阵连乘的知识进行巩固；3、用程序实现矩阵连乘。二、实验原理1、两个矩阵相乘，第一个矩阵的列数=第二个矩阵的行数；2、三个矩阵相乘时：A1*A2*A3=((A1*A2)*A3)A1*A2*A3=(A1*(A2*A3))不同的运算顺序，所需的乘

6、法次数就不一样；在算分设计与分析中，我们知道，乘法的次数越多，消耗的空间就越大，所需的时间就越多。3、当多个矩阵相乘时：我们假设Mi，j就是第i个矩阵到第j个矩阵的矩阵连乘，即Mi，j=MiMi+1……Mj选中一个k值，i<=k<=j，使得：Mi，k-1=MiMi+1…Mk-1，Mk，j=MkMk+1…Mj用数组C[i][j]表示第i个矩阵到第j个矩阵的矩阵连乘最优解，有：三、问题分析及算法设计思路1、计算最优值算法：建立两张表（，一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3

7、个矩阵…、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另一张表存储最优断开位置。2、输出矩阵结合方式算法：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程完成。分三种情况：（1）只有一个矩阵，则只需打印出A1；（2）有两个矩阵，则需打印出（A1A2）；（3）对于矩阵数目大于2，则应该调用递归过程两次，构造出最优加括号方式。四、程序代码#includeusingnamesp

8、acestd;#defineN100intn,q;intm[N][N],s[N][N],p[N+1];//计算最优值和最优解，最优值存储在m[i][j]，最优解存储在s[i][j]voidmatrixChain(){for(inti=1;i<=n;i++){m[i][i]=0;}for(intr=2;r<=n;r++){for(inti=1;i<=n-r+1;i++){intj=r+i-1;m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for

9、(intk=i+1;k

10、][j]+1,j);cout<<")";}}voidmain(){usingnamespacestd;cout<<"输入矩阵个数:";cin>>n;cout<<"输入第一个矩阵行数和第一个到第n个矩阵的列数：";cout<>p[i];}cout<

11、;//最终解值为m[1][n]cout<

12、物品和一背包。物品i的重量是wi，其价值为vi，背包的所能够容纳的重量为c。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？三、问题分析及算法设计思路在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入物品i的一部分。0-1背包问题具有最优子结构性质，可以据此定义递归关系，建立递归方程，并以自底向上的方式计算最优值，根据计算最优值时的得到的信息，构造最优解。设所给0-1背包问题的子问