分治法求矩阵乘法课程论文.docVIP

西北农林科技大学信息工程学院 《算法分析与设计》综合训练实习报告 题 目： 矩阵乘法 学 号 2012013330 姓 名 杨康 专业班级 软件工程121 指导教师 李宏利 实践日期 2014年6月23日 - 6月27日 目 录 一、综合训练目的与要求 1 二、综合训练任务描述 1 三、算法设计 1 四、详细设计及说明 11 五、调试与测试 11 六、实习日志 13 七、实习总结 14 八、附录：核心代码清单 14 一、综合训练目的与要求 本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完《算法分析》课程后进行的综合练习。本课综合训练的目的和任务： 1. 巩固和加深学生对算法分析课程基本知识的理解和掌握； 2. 培养利用算法知识解决实际问题的能力； 3. 掌握利用程序设计语言进行算法程序的开发、调试、测试的能力； 4. 掌握书写算法设计说明文档的能力； 5. 提高综合运用算法、程序设计语言、数据结构知识的能力。 二、综合训练任务描述 使用Strassen算法实现矩阵乘法 （1） 要求掌握分治法； （2） 设计一个界面，显示计算结果； （3） 编程语言不限； 三、算法设计 (1) 文字描述 a、分治法： 概念：采取各个击破的技巧来解决一个规模较大的问题，该技巧是很多高效算法的基础。 思想：“分而治之”。把一个复杂的问题分成两个或更多的相同子问题，再把子问题分成更小的子问题，直到最后各个子问题可以简单地直接求解，对各个子问题的解进行合并，即得原问题的解。 b、分治法的求解步骤 步骤1：分解。 将问题进行分解为若干个规模较小、相互独立、与原问题形式相同的子问题。 步骤2：治理。 步骤2-1：求解各个子问题 若子问题规模较小而容易被解决则直接求解，否则再继续分解为更小的子问题，直到容易解决为止。 步骤2-2：合并 将以求得的各个子问题的解合并为原问题的解。 框图 根据对课题的分析，我所创建的框图如图1所示： 图1 伪代码 ------------------------------------------------------------------------ 分治法实现矩阵相乘 ------------------------------------------------------------------------ #includeiostream #includemath.h #includefstream #includestdlib.h using namespace std; ifstream infile(data1.txt,ios::in); void Input(int n,int **A) { //infilen; for(int i=0; in; i++) for(int j=0; jn; j++) infileA[i][j]; } void Output(int n,int **A) { for(int i=0; in; i++) { for(int j=0; jn; j++) coutA[i][j]\t; coutendl; } coutendl; } void Divide(int n,int **A,int **A11,int **A12,int **A21,int **A22) { int i,j; for(i=0; in; i++) for(j=0; jn; j++) { A11[i][j]=A[i][j]; A12[i][j]=A[i][j+n]; A21[i][j]=A[i+n][j]; A22[i][j]=A[i+n][j+n]; } } void Unit(int n,int **A,int **A11,int **A12,int **A21,int **A22) { int i,j; for(i=0; in; i++) for(j=0; jn; j++) { A[i][j]=A11[i][j]; A[i][j+n]=A12[i][j]; A[i+n][j]=A21[i][j]; A[i+n][j+n]=A22[i][j];