算法实验报告.doc

算法实验报告 任课教师： 马传香 学院： 计算机与信息工程学院 班级： 计科一班 姓名： 王怡宁 学号： 2011221104210019-实验一：大整数乘法-实验二：Strassen矩阵乘法-实验三：矩阵连乘-实验四：背包问题-实验五：多机调度 实验一：大整数乘法一问题描述通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而，在某些情况下，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内进行处理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。请设计一个有效的算法，可以进行两个n位大整数的乘法运算。二算法描述设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。下面我们用分治法来设计一个更有效的大整数乘积算法。 将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，由此，X=A2n/2+B ，Y=C2n/2+D。这样，X和Y的乘积为：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD(1)如果按式(1)计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法(分别对应于式(1)中的加号)，此外还要做2次移位(分别对应于式(1)中乘2n和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2个n位整数相乘所需的运算总数，则由式(1)，我们有: (2)由此可得T(n)=O(n2)。因此，用(1)式来计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式:XY=AC2n+(A-B)(D-C)+AC+BD2n/2+BD (3)虽然，式(3)看起来比式(1)复杂些，但它仅需做3次n/2位整数的乘法(AC，BD和(A-B)(D-C)，6次加、减法和2次移位。由此可得:(4)用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。利用式(3)，并考虑到X和Y的符号对结果的影响，我们给出大整数相乘的完整算法MULT如下:function MULT(X，Y，n); X和Y为2个小于2n的整数，返回结果为X和Y的乘积XYbegin S:=SIGN(X)*SIGN(Y); S为X和Y的符号乘积 X:=ABS(X); Y:=ABS(Y); X和Y分别取绝对值 if n=1 then if (X=1)and(Y=1) then return(S) else return(0) else begin A:=X的左边n/2位; B:=X的右边n/2位; C:=Y的左边n/2位; D:=Y的右边n/2位; ml:=MULT(A,C,n/2); m2:=MULT(A-B,D-C,n/2); m3:=MULT(B,D,n/2); S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3); return(S); end;end;上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次数。下面的例子演示了算法的计算过程。三用c+实现#include #include #include using namespace std; int n,x,y,rt;/全局变量 void input() coutn; coutendl请输入两个乘数的值:endl; coutx; couty; int calculate(int a,int b) /计算数值函数-循环体 int temp1,temp2; long s; int x1,x0,y1,y0; if(n1) /可以分治算法的条件 temp1=(int)pow(10,n/2); temp2=(int)pow(10,n); x1=a/temp1; /x值的前半部分 x0=a-x1*temp1; /x值的后半部分 y1=b/temp1;/y值的前半部分 y0=b-y1*temp1;/y值的后半部分 n=n/2; /经过一次分治后,数的位数减半 s=calculate(x1,y1)*temp2+(calculate(x1+x0,y1+y0)-calculate(x1,y1)-calculate(x0,y0)*temp1+calculate(x0,y0); else return a*b; return s; void print()/输出函数 cout乘数x=xty=yendl; cout结果rt=rtendl; void main()/主函数 char c; do system(cls);/清屏函数 input(); rt=calculate(x,y); print(); cout是否继续?(y/n)c; while(c=y|c=Y); 四实验结果 实验二：Strassen矩阵乘法一实验目的1. 理解 Strassen 矩阵乘法的分治思想Strassen 矩阵乘法的分治法设计模式是：半分+混合2. 改进 Strassen 矩阵乘法对内存的需求若按 Strassen 矩阵乘法的直接表述实现，则空间复杂度将是O(3n2)，本实验将试图改进这个方面。3. Strassen 矩阵乘法的性能问题改进 Strassen 矩阵乘法的内存需求，并不一定能改进Strassen 矩阵乘法的效率，本实验将试图测试一些较大规模(n=1024)的n 阶方阵的Strassen 矩阵乘，探讨其效率问题。二算法描述procedure STRASSEN(n,A,B,C); begin if n=2 then MATRIX-MULTIPLY(A，B，C) else begin 将矩阵A和B依(1)式分块; STRASSEN(n/2,A11,B12-B22,M1); STRASSEN(n/2,A11+A12,B22,M2); STRASSEN(n/2,A21+A22,B11,M3); STRASSEN(n/2,A22,B21-B11,M4); STRASSEN(n/2,A11+A22,B11+B22,M5); STRASSEN(n/2,A12-A22,B21+B22,M6); STRASSEN(n/2,A11-A21,B11+B12,M7); end; end; 其中MATRIX-MULTIPLY(A，B，C)是按通常的矩阵乘法计算C=AB的子算法。 Strassen矩阵乘积分治算法中，用了7次对于n/2阶矩阵乘积的递归调用和18次n/2阶矩阵的加减运算。由此可知，该算法的所需的计算时间T(n满足如下的递归方程: 按照解递归方程的套用公式法，其解为T(n)=O(nlog7)O(n2.81)。由此可见，Strassen矩阵乘法的计算时间复杂性比普通矩阵乘法有阶的改进。三用c+实现#include const int N=8; /常量N用来定义矩阵的大小void main() void STRASSEN(int n,float AN,float BN,float CN); void input(int n,float pN); void output(int n,float CN); /函数声明部分 float ANN,BNN,CNN; /定义三个矩阵A,B,C cout现在录入矩阵ANN:endlendl; input(N,A); coutendl现在录入矩阵BNN:endlendl; input(N,B); /录入数组 STRASSEN(N,A,B,C); /调用STRASSEN函数计算 output(N,C); /输出计算结果void input(int n,float pN) /矩阵输入函数 int i,j; for(i=0;in;i+) cout请输入第i+1行endl; for(j=0;jpij; void output(int n,float CN) /据矩阵输出函数 int i,j; cout输出矩阵:endl; for(i=0;in;i+) coutendl; for(j=0;jn;j+) coutCij ; coutendlendl; void MATRIX_MULTIPLY(float AN,float BN,float CN) /按通常的矩阵乘法计算C=AB的子算法(仅做2阶) int i,j,t; for(i=0;iC for(j=0;j2;j+) Cij=0; /计算完一个Cij，Cij应重新赋值为零 for(t=0;tZ int i,j; for(i=0;in;i+) for(j=0;jZ int i,j; for(i=0;in;i+) for(j=0;jn;j+) Zij=Xij-Yij; void STRASSEN(int n,float AN,float BN,float CN) /STRASSEN函数（递归） float A11NN,A12NN,A21NN,A22NN; float B11NN,B12NN,B21NN,B22NN; float C11NN,C12NN,C21NN,C22NN; float M1NN,M2NN,M3NN,M4NN,M5NN,M6NN,M7NN; float AANN,BBNN,MM1NN,MM2NN; int i,j;/,x; if (n=2) MATRIX_MULTIPLY(A,B,C);/按通常的矩阵乘法计算C=AB的子算法(仅做2阶) else for(i=0;in/2;i+) / for(j=0;jn/2;j+) A11ij=Aij; A12ij=Aij+n/2; A21ij=Ai+n/2j; A22ij=Ai+n/2j+n/2; B11ij=Bij; B12ij=Bij+n/2; B21ij=Bi+n/2j; B22ij=Bi+n/2j+n/2; /将矩阵A和B式分为四块 MATRIX_SUB(n/2,B12,B22,BB); STRASSEN(n/2,A11,BB,M1);/M1=A11(B12-B22) MATRIX_ADD(n/2,A11,A12,AA); STRASSEN(n/2,AA,B22,M2);/M2=(A11+A12)B22 MATRIX_ADD(n/2,A21,A22,AA); STRASSEN(n/2,AA,B11,M3);/M3=(A21+A22)B11 MATRIX_SUB(n/2,B21,B11,BB); STRASSEN(n/2,A22,BB,M4);/M4=A22(B21-B11) MATRIX_ADD(n/2,A11,A22,AA); MATRIX_ADD(n/2,B11,B22,BB); STRASSEN(n/2,AA,BB,M5);/M5=(A11+A22)(B11+B22) MATRIX_SUB(n/2,A12,A22,AA); MATRIX_SUB(n/2,B21,B22,BB); STRASSEN(n/2,AA,BB,M6);/M6=(A12-A22)(B21+B22) MATRIX_SUB(n/2,A11,A21,AA); MATRIX_SUB(n/2,B11,B12,BB); STRASSEN(n/2,AA,BB,M7);/M7=(A11-A21)(B11+B12) /计算M1,M2,M3,M4,M5,M6,M7（递归部分） MATRIX_ADD(N/2,M5,M4,MM1); MATRIX_SUB(N/2,M2,M6,MM2); MATRIX_SUB(N/2,MM1,MM2,C11);/C11=M5+M4-M2+M6 MATRIX_ADD(N/2,M1,M2,C12);/C12=M1+M2 MATRIX_ADD(N/2,M3,M4,C21);/C21=M3+M4 MATRIX_ADD(N/2,M5,M1,MM1); MATRIX_ADD(N/2,M3,M7,MM2); MATRIX_SUB(N/2,MM1,MM2,C22);/C22=M5+M1-M3-M7 for(i=0;in/2;i+) for(j=0;jn/2;j+) Cij=C11ij; Cij+n/2=C12ij; Ci+n/2j=C21ij; Ci+n/2j+n/2=C22ij; /计算结果送回CNN 4 实验结果 实验三：矩阵连乘1 问题描述给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2,n-1。要算出这n个矩阵的连乘积A1A2An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。2 算法分析 1按照2个矩阵乘积的标准算法，若一个pq的矩阵A和一个st的矩阵B相乘（当然s和q要相等），要进行三重循环，总共需要pqr次数乘，显然这是一个比较的的数。 2通过简单分析，我们易知给连乘矩阵完全加括号方式对应一种矩阵连乘的计算次序，而这种计算次序会改变计算矩阵连乘的计算量，再试想如果是n个矩阵进行连乘那将会要太多次数乘，所以有必要做一个算法找出怎样合理的给连乘矩阵完全加括号以找出最少计算量的计算方法。3穷举搜索法是最容易想到的方法，但是它本身是一个计算量非常大的算法，对于n个矩阵的连乘问题，不同的计算次序是随n的增大呈指数增长的。4尝试用动态规划算法解决上面问题：首先由于A【1：n】（表示1到n个矩阵连乘）如果是最优解，那么它包含的A【1：k】和A【k1：n】也是最优解，即矩阵连乘求最优解符合动态规划中的最优子结构性质；再次由于A【i：j】的最少数乘次数m【i】【j】可以表示为m【i】【j】m【i】【k】m【k1】【j】pj1pkpj（其中k是断开点），所以它也可以设计成一个具有递归关系的算法。5具体实现：按照m【1】【n】的递归性以自底向上的方式进行计算，在计算中用m【】【】数组记录已经计算过的自问题的答案，m【i】【j】表示A【i：j】的最少数乘次数，并且用数组s【】【】来表示对应的m【】【】数组值的最优断开点。程序由两个函数组成：1）、void MatrixChain(int p,int n)用来产生数组m和s，是关键部分；2）、int Traceback(int i,int j)是用来找出s数组中记录的最优断开点的函数。程序中我把m和s数组都给了输出，方便观察、研究。三用c语言实现#include /#include /#include #define LENGTH 6void MatrixChainOrder(int p,int mLENGTH,int sLENGTH) int n=LENGTH; int i,j,k,r,t; for(i=0;in;i+) mii=0;for( r=1;rn;r+) for(i=0;in-r;i+) j=i+r; mij=mii+mi+1j+pi*pi+1*pj+1; sij=i; for(k=i+1;kj;k+) t=mik+mk+1j+pi*pk+1*pj+1; printf(t=%d;,m%d%d=%dn,t,i,j,mij); if(tmij) mij=t; sij=k; int main() int p = 30,35,15,5,10,20,25; int mLENGTHLENGTH; int sLENGTHLENGTH; int i,j,k; MatrixChainOrder(p,m,s); printf(最少数乘次数：n); for(i = 0;iLENGTH;i+) for(j = 0 ;j=i ;j+ ) printf( ); for(k = i; kLENGTH;k+) printf(%8d,mik); printf(n); printf(断开位置：n); for(i = 0;iLENGTH;i+) for(j = 0 ;j=i ;j+ ) printf( ); for(k = i; kLENGTH;k+) printf(%4d,sik); printf(n); return 0;四实验结果 实验四：背包问题1 问题描述本课设是一个对实际问题的研究,背包的总质量一定,n件物品的质量也是一定的，通过用栈的回塑来用不同质量物品装满整个背包。将n件物品一一装进背包中，每装一件，用所装入物品的总质量与背的最大质量进行比较，当所装入的物品总质量小于背包的的最大质量时，继续此程序。当装入背包的物品总质量大于背包的总质量时，背包取出一个物品，并继续反复往背包中装入物体过程。如此往复，直到所装物体总质量等于背包的重量为止。此时输出所有可能情况。若不能装满此背包，则输出此问题无解。2 算法分析 首先需选出最优的量度标准。不妨先取目标函数作为量度标准，即每装入一件物品就使背包获得最大可能的效益值增量。在这种量度标准下的贪心方法就是按效益值的非增次序将物品一件件放到背包中去。如果正在考虑中的物品放不进去，则可只取其一部分来装满背包。但这最后一次的方法可能不符合使背包每次获得最大效益增量的量度标准，这可以换一种能获得最大增量的物品，将它（或它的一部分）放入背包，从而使最后一次装包也符合量度标准的要求。3 用c+实现#includeusingnamespacestd;voidbeibao(double*w,double*v,double*x,doublen,double*C)inti,j,temp;for(i=0;in-1;i+)for(j=i+1;jn;j+)if(vi/wivj/wj)temp=vi;vi=vj;vj=temp;temp=wi;wi=wj;wj=temp;for(i=0;in;i+)xi=0;for(i=0;*C!=0;i+)if(wi*C)xi=wi;*C=*C-wi;elsexi=*C;*C=*C-*C;voidmain()inti;double*w,*v,n,C;double*x;cout请输入物品数n;w=newdouble(n);/动态分配内存v=newdouble(n);x=newdouble(n);cout请输入背包的容量C;cout请分别输入n个物品的重量:endl;for(i=0;iwi;cout请分别输入n个物品的价值:endl;for(i=0;ivi;beibao(w,v,x,n,&C);cout装入的物品为:endl;for(i=0;in;i+)if(xi!=0)cout其装的重量为：xi其价值为：vi;coutn,时，只要将机器ide0,ti)时间去见分配给作业j即可，当mn时，首先将n个作业从大到小排序，然后依次顺序将作业分配给空闲的处理机算法伪代码将数组tn从大到小排序，对应的作业序号存储在数组pn中；将数组dm初始化为零3：for（i0;i=m;i+)3.1:si=pi:将m个作业分配给m个机器3.2di=ti;for(i=m+1;i=n;i+)4.1j=数组dm中最小值对应的下标；/j为最先空闲的机器序号4.2sj=sj+pi;/将作业分配给最先空闲的的机器j4.3dj=dj+dt;/机器j将在dj后空闲*/3 用c+实现#include #include using namespace std;void Dsc_Or