递归,分治法.doc

武夷学院实验报告 课程名称： 算法设计与分析 项目名称: 递归与分治法 姓名 专业：计科 班级： 1 学号：_ 同组成员__无 实验预习： 实验目的：利用递归与分治法解决简单问题，加深对分治算法的理解与掌握。 实验内容： 利用递归与分治法解决Strassen矩阵乘法问题。 实验原理： 我们知道当数据量一大时，我们往往会把大的数据分割成小的数据，各个分别处理。遵此思路，如果丢给我们一个很大的两个矩阵呢，是否可以考虑分治的方法循序渐进处理各个小矩阵的相乘，因为我们知道一个矩阵是可以分成更多小的矩阵的。 实验条件：具有Visual Studio2013的计算机系统；Internet环境。 算法设计： 整个算法的大致思想是：在函数Mul(int?n,int?**A,int?**B,int?**M)中，调用Divide(n,A,A11,A12,A21,A22);和Divide(n,B,B11,B12,B21,B22);将A和B都分为四个（n/2）*(n/2)的子矩阵。然后递归调用?????????Sub(n,B12,B22,T1);T1=B12-B22? ????????Mul(n,?A11,T1?,M1);M1=A11(B12-B22)?????????Add(n,A11,A12,T2);? ????????Mul(n,T2,B22,M2);M2=(A11+A12)B22?????????Add(n,A21,A22,T1);? ????????Mul(n,T1,B11,M3);M3=(A21+A22)B11?????????Sub(n,B21,B11,T1);? ????????Mul(n,?A22,T1?,M4);M4=A22(B21-B11)?????????Add(n,A11,A22,T1);?????????Add(n,B11,B22,T2);? ????????Mul(n,T1,T2,M5);M5=(A11+A22)(B11+B22)?????????Sub(n,A12,A22,T1);?????????Add(n,B21,B22,T2);? ????????Mul(n,T1,T2,M6);M6=(A12-A22)(B21+B22)?????????Sub(n,A11,A21,T1);?????????Sub(n,B11,B12,T2);? ????????Mul(n,T1,T2,M7);M7=(A11-A21)(B11+B12)??? ????????Add(n,M5,M4,T1);?????????Sub(n,T1,M2,T2);? ????????Add(n,T2,M6,M11);M11=M5+M4-M2+M6?? ????????Add(n,M1,M2,M12);M12=M1+M2?? ????????Add(n,M3,M4,M21);M21=M3+M4?? ????????Add(n,M5,M1,T1);?????????Sub(n,T1,M3,T2);? ????????Sub(n,T2,M7,M22);M22=M5+M1-M3-M7?? ????????Unit(n,M,M11,M12,M21,M22);? 将上面得到的四个矩阵组合成一个n*n矩阵。则这个n*n矩阵就是AB的结果C。? 实验过程记录： #include stdafx.h #include iostream #include ctime #include Windows.h using namespace std; templatetypename T class Strassen_class{ public: void ADD(T** MatrixA, T** MatrixB, T** MatrixResult, int MatrixSize ); void SUB(T** MatrixA, T** MatrixB, T** MatrixResult, int MatrixSize ); void MUL( T** MatrixA, T** MatrixB, T** MatrixResult, int MatrixSize ); void FillMatrix( T** MatrixA, T** MatrixB, int length);//A,B矩阵赋值 void PrintMatrix(T **MatrixA,int MatrixSize);//打印矩阵 void Strassen(int N, T **MatrixA, T **Ma