算法设计与分析(作业三).

1、算法设计与分析实验报告学院信息科学与技术学院专业班级软件工程3 班学号20122668姓名王建君指导教师尹治本2014 年 10 月实验四矩阵相乘次序一、问题提出用动态规划算法解矩阵连乘问题。 给定 n 个矩阵 A 1,A 2, ,An ，其中 Ai 与 Ai+1 是可乘的， i=1,2, ,n-1。要算出这 n 个矩阵的连乘积 A1A2 A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2 个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩

2、阵连乘积可递归地定义为：（ 1）单个矩阵是完全加括号的；（ 2）矩阵连乘积 A 是完全加括号的，则 A 可表示为 2 个完全加括号的矩阵连乘积 B 和 C 的乘积并加括号，即 A=(BC) 。 例如，矩阵连乘积 A123 4有5种不AA A同的完全加括号的方式： （ A1（ A2（ A3A4），（A 1（A 2A 3）A4），（A1A2）（ A3A4），（ A1（A 2 3）A 4），（ A1A2）A3）A4）。每一种完全加括号A的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个 p×q 矩阵， B 是一个 q×r 矩阵，则计算其乘积C=AB 的

3、标准算法中，需要进行 pqr 次数乘。（ 3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3 个矩阵 A 1,A 2,A 3 连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5× 50。加括号的方式只有两种：（ A1A2）A3），（ A1（A 2A 3），第一种方式需要的数乘次数为 10×100×510× 5× 507500，第二种方式需要的数乘次数为 100× 5× 5010×100× 5075000。第二种加括号方式的计算量时第一种方式计算量的10

4、 倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵A 12n （其中矩阵i-1 × pi， i1,2, ,n），如何确定计算矩,A, ,AAi 的维数为 p阵连乘积 A12 An 的计算次序 （完全加括号方式） ，使得依此次序计算矩阵连乘积A需要的数乘次数最少。二、求解思路本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是：1) 计算最优值算法 MatrixChain() ：建立两张表 （即程序中的 *m和*s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量

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

6、度最高为O（ n ）。四、实验源代码#include<iostream>using namespace std;const int MAX = 100;/p 用来记录矩阵的行列，main 函数中有说明/mij 用来记录第i 个矩阵至第j个矩阵的最优解/s 用来记录从哪里断开的才可得到该最优解int pMAX+1,mMAXMAX,sMAXMAX;int n;/ 矩阵个数int matrixChain()for(int i=0;i<=n;i+) mii=0;for(int r=2;r<=n;r+)/ 对角线循环for(int i=0;i<=n-r;i+)/行循环int

7、 j = r+i-1;/列的控制/找mij的最小值，先初始化一下，令k=imij=mi+1j+pi+1*pi*pj +1;sij=i;/k从i+1到j-1循环找mij的最小值for(int k = i+1;k<j;k+)int temp=mik+mk+1j+pi*pk+1*pj+1;if(temp<mij)mij=temp;/s 用来记录在子序列i-j 段中，在 k位置处/断开能得到最优解sij=k;return m0n-1;/根据 s 记录的各个子段的最优解，将其输出void traceback(int i,int j)if(i=j)cout<<'A'

8、<<i;return;if(i<sij)cout<<'('traceback(i,sij);if(i<sij)cout<<')'if(sij+1<j)cout<<'('traceback(sij+1,j);if(sij+1<j)cout<<')'void traceback()cout<<'('traceback(0,n-1);cout<<')'cout<<endl;int mai

9、n()system("title 软件 3 班 王建君 20122668 动态规划求矩阵连乘次序 "); cout<<" 请输入矩阵的个数： "<<endl;cin>>n;cout<<" 输入矩阵（形如 a*b, 中间用空格隔开） :"<<endl; for(int i=0;i<=n;i+)cin>>pi;/测试数据可以设为8个矩阵分别为/A110*15,A215*20,A320*5,A45*25,A525*20,A620*5,A75*23,A823,8/则

10、 p0-8=10,15,20,5,25,20,5,23,8cout<<" 输出结果如下： "<<endl;matrixChain();traceback(0,n-1);/最终解值为m0n-1;cout<<endl;return 0;五、结果分析测试数据可以设为8个矩阵分别为/A010*15,A115*20,A220*5,A35*25,A425*20,A520*5,A65*23,A723,8 则 p0-8=10,15,20,5,25,20,5,23,8 ，的最佳相乘次序为 (A0(A1A2)(A3A4)A5)(A6A7) 。实验五、找零问题

11、一、问题提出设有 n 种不同面值的硬币，各硬币的面值存于数组t1:n 中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限。当只用硬币面值t1,t2,ti 时，可找出钱数 M 的最少硬币个数记为bij 。若只用这些硬币面值，找不出钱数M 时，记 bij= 。二、求解思路令 bi,j 表示前 i(1 im)种硬币，总额为j(0 jn)的最小硬币数。目标为求由于对第i 种硬币，存在可选1 个或者不选两种可能，故容易建立递推关系：bm,n 。bi,jmin bi-1,j, 1+bi,j-vi, for 1i m, 0j n显然，bi,0=0,1i m如果无解，令bi,j=+ 。特别的，如

12、果i=1 ，令 b-1,j=+；如果 j-v i<0 ， bi,j-v i =+ 三、算法复杂度n- 钞票面额的个数 M- 要找的钱数，子问题不重复计算，时间复杂度降低，时间复杂度 O(nM) 。四、实验源代码#include <stdio.h>#include <stdlib.h>#define INFINITY32767/ 无穷大#define MAX100/*bij=-1bij!=-1子问题未计算，递归计算子问题已计算，直接取计算结果另外 ,也可从 bij 算出各种面额的钞票数*/int DynamicMemory(int t, int i ,int j,i

13、nt bMAX)if(i=1)if(j%t1=0)bij=j/t1;elsebij=INFINITY;returnbij;elseint x;if(bi-1j=-1)x=DynamicMemory(t,i-1,j,b);elsex=bi-1j;if(j<ti)bij=x;return x;elseint y;if(bij-ti=-1)y=DynamicMemory(t,i,j-ti,b);elsey=bij-ti;bij=(x>y+1)?(y+1):x;return bij;void main()system("title软件 3 班 王建君int t10,n,M;/n-

14、 钞票面额的个数20122668 动态规划实现找零问题M- 要找的钱数");t0=0;printf(" 请输入钞票面额的种数:n");scanf("%d",&n);printf(" 请依次输入 %d 种钞票的面额 :n",n);for(int i=1;i<=n;i+)scanf("%d",&ti);printf(" 请输入要找零的钱的总数:n");scanf("%d",&M);int bMAXMAX;int pMAX=0;for(i=0;i<MAX;i+)for(int j=0;j<MAX;j+)bij=-1;int x=DynamicMemory(t,n,M,b);if(x=INFINITY)printf(" 无解 !n