循环调度的分治算法实现实验报告gxl
页面
PAGE 2
深圳大学实验报告
课程名称：算法设计与分析
实验项目名称：分治算法
-矩阵乘法的Strassen算法和时间复杂性分析
或--循环调度的分布式算法实现
或多项式积问题的方差算法和时间复杂性分析
学院：
专业，班级：
指导教师：
报告员：学校编号：
实验时间：
实验报告提交时间：
教务处制
实验的目的和实验内容
1.1实验目的
通过本设计实验，了解递归算法以及分割统治算法的基本思想。 了解Strassen矩阵乘法的理论分析或循环比赛时间表的分布式算法及编程实现。 掌握多项式积的方差方法。 可以设计、分析递归算法和分布式算法。
这门课的实验目的是验证、加强和补充课堂上讲授的理论知识。 学生独立设计算法，初步具备对给定算法进行复杂性分析的能力，为后续课程和实际工作奠定基础。
1.2实验主题(三道题中的任意一道) ) ) ) )。
主题1 )设计并编程实现矩阵相乘的Strassen算法，进行算法的时间复杂性分析。 其中，考虑到n为2的幂的情况，乘积矩阵C=A*B，a=(AIJ ) n*n，b=(bij ) n*n )1)取n=8实现方差递归； )2)考虑到n是偶数而不是2的幂，设计结合传统方法的Strassen算法的矩阵乘法算法，采用n=12实现方差递归(可在多个方案中实现)； 矩阵a、b元素自动生成，限定矩阵元素在0-10之间。
主题2 )设计满足以下要求的循环比赛时间表() ) ) ) )。
(1)每名选手必须与其他n-1名选手各进行一次比赛。
)2)每个运动员一天只能打一次比赛。
)3) n为奇数时，每班n天，n为偶数时，每班n-1天。
主题3 )设计多项式乘积问题的方差算法，进行算法的时间复杂性分析
1.3实验要求：
主题1具体要求：
(1)矩阵次数n由用户输入)注意n为2k以外时的处理)；
)2) n阶矩阵a、b调用随机函数自动生成，限定矩阵元素在0-10之间；
(3)输出a、b及C=A*B
其中，输出传统定义的矩阵乘积结果和Strassen矩阵乘积结果，验证分治算法的正确性；
(4)直接计算)对矩阵积、Strassen矩阵积进行运行时间统计，分别标记为T1、T2，并给出对比和时间复杂性分析。
主题2具体要求：
)1)选手数n由用户输入(注意n为奇数时和偶数时的处理差异)；
)2)验证n=2k的比赛时间表
)3)完成n=2k 1和n=2k的不同处理，输出如下表所示的比赛时间表。 这里，k是【5、7】之间的整数；
1
2
3
4
5
6
7
8
9
10
2
1
5
3
7
4
8
9
10
6
3
8
1
2
4
5
9
10
6
7
4
5
9
1
3
2
10
6
7
8
5
4
2
10
1
3
6
7
8
9
6
7
8
9
10
1
5
4
3
2
7
6
10
8
2
9
1
5
4
3
8
3
6
7
9
10
2
1
5
4
9
10
4
6
8
7
3
2
1
5
10
9
7
5
6
8
4
3
2
1
表分治法n=10的比赛时间表
主题3具体要求：
针对教材第114页的第21题数据，完成两个多项式乘积的分布式算法：
多项式pn(x )的n和QM ) x )的m由用户输入；
直接输出多项式积和分治算法多项式积的计算结果，验证分治算法的正确性；
对直接计算多项式积、分段托管算法多项式积进行运行时间统计，分别标记为T1、T2，并给出对比和时间复杂性分析。
对于p4(x )=x4x3x2- x1和q5(x )=X53x-10，根据要求从(1) )到(3)完成两个多项式乘积的分割算法。
开发环境
VC 6.0编程软件
算法概述
总体思路：通过分而治之的策略，将一切分成两半，n名选手可以由n/2名选手设计的比赛时间表决定。 通过递归地将选手分成两部分，分割成只剩下两个选手。
n为奇数时，可以虚拟增加一名选手，对N 1名选手的时间表进行编程，最忽略虚拟选手参加的比赛。 对分割时的N/2情况也进行特殊处理，与没有参加上一个N/2回合比赛的选手参加下一场比赛。
解决模型
编程说明(例如，你