《2023年矩阵连乘实验报告.docx》由会员分享，可在线阅读，更多相关《2023年矩阵连乘实验报告.docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、华北电力大学科技学院实验报告实验名称 矩阵连乘问题课程名称 计算机算法设计与分析专业班级:。软件12K188。学生姓名:吴旭学 号：，成 绩：指导老师：。刘老师实验日期：2023.11.1 4环节。完毕实验后，我认为建立递归关系是很关键的一步，同时也 是整个动态规划算法的精髓。掌握了递归的思想，就可以完毕很多 不必要的反复计算。具体到矩阵连乘问题，关键是解决断开点k的位置和最少数乘 次数。总体来说,这次实验不仅让我基本掌握递归的思想，并且进一步 提高了自己的自学能力和编程能力，代码运用C语言写出，可以很好 的体会C语言和C+的不同点和相同点。我也体会到,想要理解一个 新的算法，必须要通过自己不
2、断的编写程序，不断的思考才干真正的 领悟,因此我会不断朝着这个方向努力。一、实验内容矩阵连乘问题，给定个矩阵AiA,.,An,其中Ai与Ai+I是可乘的，i=l, 2 , 3., nl。考察这个矩阵的连乘Ai,A2,，二、重要思想由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不 同的计算顺序。这种计算顺序可以用加括号的方式来拟定。若一个 矩阵连乘积的计算顺序完全拟定，也就是说该连乘积已经完全加括 号，则可依此顺序反复调用2个矩阵相乘的标准算法计算出矩阵连 乘积。完全加括号的矩阵连乘积可递归的定义为：(1)单个矩阵是完全加括号的；(2)矩阵连乘积A是完全加括号的，则A可表达为2个完全加括号
3、的 矩阵连乘积B和C的乘积并加括号，即A=(BC)。运用动态规划法解矩阵连乘积的最优计算顺序问题。按以下几 个环节进行分析最优解的结构设计求解具体问题的动态规划算法的第1步是刻画该问题的最 优解的结构特性。为方便起见，将矩阵连乘积简记为Ai: j 。考察 计算A 1 : n 的最优计算顺序。设这个计算顺序矩阵在Ak和Ak+i之 间将矩阵链断开，lkWn,则其相应的完全加括号方式为(AiA k) (Ak+i.An)o依此顺序,先计算Al:k和Ak+1 :n,然后将计算结果相乘得到Al:n01、 建立递归关系设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积 的最优计算顺序问题，设计算Ai
4、:j, iWiMjMn,所需的最少数乘 次数为m Ei j,原问题的最优值为当i =j时，A i:j=A i为单一矩阵，无需计算，因此 mi i =0,i=l,2, .no当ivj时，可运用最优子结构性质来计算m mi j=m ik+mk+l j +pi-ipkPjo由于在计算时并不知道断开点k的位 置，所以k尚未定。2、 计算最优值根据计算mi j的递归式，容易写一个递归算法计算mlno 动态规划法解决此问题，可依据递归式以自底向上的方式进行计算, 在计算过程中保存已解决的子问题答案。每个子问题只计算一次，而 在后面需要时只要简朴查一下，从而避免大量的反复计算，最终得到 多项式时间的算法m
5、atrixCh a i n。(见实验代码部分)构造最优解算法matrixCh a in只计算出最优值，并没有给出最优解。但是matr i x C h ain已经记录了构造最优解所需的所有信息。S i j中的 数表白，计算矩阵链Ai:j的最佳方式应在矩阵Ak和Ak+i之间断开， 最优加括号方式为(Ai:k)(Ak+l:j)o依次构造最优解。(算法见实验代码部分）三、实验结果输入矩阵的个数注：小于100： 4”输入A1的件35 嘛入A2的彳彳：15 端入A3的牛5XXMWX* 歹 | J ： 10卜输入A4的件10*-M*M*-M*| ：20其子如下：最少技乘次数为7125Press any ke
6、y to continue四、结果验证对实验结果进行验证,4个矩阵分别是Ai35*l 5 ,A21 5*5,A35*10, A4 1 0*2 0。依递归式有：0 + 2500 + 35 x 15 x 20 =Ml 4 =min +1000 + 35 x 5 x 20 = 7125 .4375 + 0 + 35 x 10 x 20 = 11375= 7 125且 k=3o计算结果对的，证明所编写的程序可对的算出最优解。五、实验代码#incl u de# d cfinc N 1 00/定义最大连乘的矩阵个数是1 00void m a t rix C h a i n (int p ,i n t m
7、N+ 1 N + 1, i nt sN+ 1 N+1)/* 用二维数组来存储Ai*.Aj的最少数乘次数，用来存储使A i . Aj获得最少数乘次数相应的断开位置k,需要注意 的是此处的N+1非常关键，虽然只用到的行列下标只从1到N,但是下标。相应的元素默认也属于该数组，所以数组的长度就应当为N+1*/ (A n t n=N;/ /定义m, s数组的都是n*n的.不用行列下标为()的元素，但涉及在 该数组中f o r (int i =1 ； i V=n;i+ + )m/ *将矩阵m的对角线位置上元素所有置0,此时应是r=1的情况，表达先计算第一层对角线上个元素的值切f or(i n t r =
8、2 ;r= n ； r+)/ r表达斜对角线的层数，从2取到n(gfor (int i=l;i=n-r+ 1 ;i+)/i表达计算第r层斜对角线上第i行元素的值00 |-int j=i + r-l;/ j表达当斜对角线层数为r,行下标为i时的列下标 a mi j =m i + 1 |j+p i -1 *p i * p U；计算当断开位置为 i 时相 应的数乘次数si j=i；/断开位置为i。 for (int k=i+l;k j ;k+)00 (。“int t=m i kj+m k +1J jj+ p k ；/*计算断开位置 k 为 从i至Ijj (不涉及i和j)的所有取值相应的。(A i *
9、.*Ak ) *(Ak+ 1 *. Aj)的数乘次数* /:t ； /将Ai*. . A j的最少数乘次数存入mi将 si j =k;/将相应的断开位置k存入si j00 000。 000 。void trac e b a ck (in t i, i nt j,int sN+l ) /用递归来实现输出得到 最小数乘次数的表达式(if( i =j)。叩rintf(“A%d，i)；o e Ise。printf();tr a ce b a c k( i , s i j, s );trac e back (si j+l, j, s);printf (H);)vo i d m a in()(intn;/
10、用来存储矩阵的个数Mntq2*N; /*用q数组来存储最原始的输入(各矩阵的行和列)，重要目的是 为了检查这N个矩阵是否满足连乘的条件* /i nt pN+l,f la g= 14用pi- 1 ,p i 数组来存储A的阶数,flag用 来判断这N个矩阵是否满足连乘* /int mN+lN+ 1 ;/用m i j 二维数组来存储Ai* Aj的最 小数乘次数int sN+l N+l ;/用s来存储使Ai A j获得最小数乘次数相应的断开位置kOprinlf(输入矩阵的个数(注：小于100):“);scant (d”,&n);for(in t i=0;i=2*nI; i + + )/各矩阵的阶数的输
11、入先存入数组q中接受 检查ooif(i%2=0)00 |o p rintf(nM);。 printf (*输入 A%d 的行:”,(i/2)+ 1 );00 |。空 I se 。op r i nt f (”*列:”)；oscanf(H%d;&qi)；for( i =1; i =2*n2； i+)/矩阵连乘条件的检查。i f (i%2!=0&q i !=q i+1)00 |fl a g=0;。b rea k ；0)0)fb r (in t j=l; j =n- 1 ; j +)if(flag!=O)P 0=q ();。叩n= q f 2 *n-l;m a trixCh a i n(p, m , s); p r in t f(式子如下:n);q t race b ack ( 1 , n , s);。printf (*n )；。叩r i n tf(最少数乘次数为dn,ml |n)；Ielse叩r in t(这1个矩阵不能连乘！ n”，n);)六、实验心得通过本次实验，我较为透彻的理解了动态规划算法的几个基本