算法设计与分析作业三

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

9、()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,in

13、t 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;

15、i<MAX;i+)for(int j=0;j<MAX;j+)bij=-1;int x=DynamicMemory(t,n,M,b);if(x=INFINITY)printf(" 无解 !n");elseprintf(" 找零钞票总数：%dn",x);int r=M;int k=n;while(r>0)if(r<tk)pk+=0;k=k-1;else if(bkr=bkr-tk+1)pk+=1;r=r-tk;elsepk+=0;k=k-1;for(k=n;k>=1;k-)if(pk!=0)printf(" 面额为 %

16、d 的钞票数： %dn",tk,pk);五、结果分析其中专业理论知识内容包括：保安理论知识、消防业务知识、职业道德、法律常识、保安礼仪、救护知识。作技能训练内容包括：岗位操作指引、勤务技能、消防技能、军事技能。二培训的及要求培训目的安全生产目标责任书为了进一步落实安全生产责任制，做到“责、权、利”相结合，根据我公司2015 年度安全生产目标的内容，现与财务部 签订如下安全生产目标：一、目标值：1 、全年人身死亡事故为零，重伤事故为零，轻伤人数为零。2 、现金安全保管，不发生盗窃事故。3 、每月足额提取安全生产费用，保障安全生产投入资金的到位。4 、安全培训合格率为 100% 。二、本

17、单位安全工作上必须做到以下内容：1 、对本单位的安全生产负直接领导责任，必须模范遵守公司的各项安全管理制度，不发布与公司安全管理制度相抵触的指令，严格履行本人的安全职责，确保安全责任制在本单位全面落实，并全力支持安全工作。2 、保证公司各项安全管理制度和管理办法在本单位内全面实施，并自觉接受公司安全部门的监督和管理。3 、在确保安全的前提下组织生产，始终把安全工作放在首位，当“安全与交货期、质量”发生矛盾时，坚持安全第一的原则。4 、参加生产碰头会时，首先汇报本单位的安全生产情况和安全问题落实情况；在安排本单位生产任务时，必须安排安全工作内容，并写入记录。5 、在公司及政府的安全检查中杜绝各类违章现象。6 、组织本部门积极参加安全检查，做到有检查、有整改，记录全。7 、以身作则，不违章指挥、不违章操作。对发现的各类违章现象负有查禁的责