循环赛日程表的分治算法实现实验报告gxlWord文档下载推荐.docx
《循环赛日程表的分治算法实现实验报告gxlWord文档下载推荐.docx》由会员分享，可在线阅读，更多相关《循环赛日程表的分治算法实现实验报告gxlWord文档下载推荐.docx（7页珍藏版）》请在冰点文库上搜索。
实验时刻：
实验报告提交时刻：
教务处制
一、实验目的与实验内容
1．1实验目的
通过本设计性实验，理解递归算法以及分治算法的基本思想。
理解Strassen矩阵乘法的理论分析或循环赛日程表的分治算法以及编程实现。
掌握多项式乘积的分治方法。
能对递归算法以及分治算法进行设计、分析。
本课程实验目的是验证、巩固和补充课堂讲授的理论知识。
培养学生初步具备独立设计算法和对给定算法进行复杂性分析的能力，为后继课程和实际工作打下基础。
1．2实验题目（三题任选一）
题目1：
设计一个矩阵相乘的Strassen算法编程实现并做算法的时间复杂性分析。
其中：
乘积矩阵C=A*B，A=（aij）n*n，B=（bij）n*n
（1）考虑n为2的幂次方的情形，取n=8实现分治递归；
（2）考虑n不是2的幂次方，n为偶数的情形，设计一个传统方法与的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
表分治法n=10的比赛日程表
题目3具体要求：
对教材114页第21题的数据，完成两个多项式乘积的分治算法：
（1）多项式Pn（X）的n与Qm（X）的m由用户输入；
（2）输出直接计算多项式乘积和分治算法多项式乘积的结果，验证分治算法的正确性；
（3）对直接计算多项式乘积、分治算法多项式乘积进行执行时间统计，分别记为T1，T2，并给出对比和时间复杂性分析。
（4）对P4（X）=X4–X3+X2-X+1与Q5（X）=X5–3X+-10，按要求
（1）∼（3）完成两个多项式乘积的分治算法。
二、开发环境
VC编程软件
三、算法简述
总体思路：
按分治策略，将所有分为两半，n个选手可以通过n/2个选手设计的比赛日程表来决定。
递归地用一分为二的略对选手进行分割，直到只剩下两个选手。
对于N为奇数的情况可以虚拟多一个选手，使其编程N+1个选手的日程表，最然后忽略虚拟运动员参与的比赛。
对于分割时候N/2的情况也做特殊处理,前n/2轮比赛空选手与下一个未参赛的选手进行比赛。
四、模型求解
4.1程序设计（方案）说明（如：
你如何实现矩阵划分、矩阵结果的合并）
4.2主要源代码（主要函数功能、变量、语句进行注释）
（1）分治法
voidtourna（intn）
{
if（n==1）{a[1][1]=1;
return;
}
tourna（n/2）;
copy（n）;
（2）n为偶数的情况Copy（）函数：
A.将左上角递归计算出的小块的所有数字按其相对位置抄到右下角，B.将右上角的小块的所有数字加n/2后按其相对位置抄到左下角，将左下角的小块中的所有数字按其相对位置抄到右上角
voidcopy（intn）
intm=n/2;
for（inti=1;
i<
=m;
i++）
for（intj=1;
j<
j++）{
a[i][j+m]=a[i][j]+m;
//小块的数值抄到右下角
a[i+m][j]=a[i][j+m];
//右上抄到左下
a[i+m][j+m]=a[i][j];
//左下抄到右上
（3）一般性描述：
n为偶数;
n是奇数时增加一个虚拟选手n+1，将问题转换为n是偶数的情形。
voidtournament（intn）
if（n==1）{a[1][1]=1;
}//分割到最后
if（odd（n））{tournament（n+1）;
}//奇数的情况加上虚拟选手
tournament（n/2）;
//分割
makecopy（n）;
//这个函数copy分n为偶数很n为奇数的情况
（4）判断奇偶
boolodd（intn）
{
returnn&
1;
}
（5）makecopy（）与copy相似，并区分奇偶情况
voidmakecopy（intn）{
if（n/2>
1&
&
odd（n/2））copyodd（n）;
//对n/2为奇数的情况的处理
elsecopy（n）;
//偶数的情况
（6）copyodd（n）实现n/2为奇数的时候的复制
n/2奇数的一种处理方法：
前n/2轮比赛空选手与下一个未参赛的选手进行比赛
voidcopyodd（intn）
for（inti=1;
i++）{
b[i]=m+i;
b[m+i]=b[i];
for（i=1;
=m+1;
if（a[i][j]>
m）{
a[i][j]=b[i];
a[m+i][j]=（b[i]+m）%n;
else
a[m+i][j]=a[i][j]+m;
}
for（j=2;
a[i][m+j]=b[i+j-1];
a[b[i+j-1]][m+j]=i;
4.3程序使用说明（如：
矩阵阶数n由用户输入）
4.4模型的解（含运行结果截图）
当n=偶数时
当n=奇数时
测试及结果分析
（如：
1.对传统定义矩阵乘积、Strassen矩阵乘积给出计算结果对比；
2.进行执行时间统计的对比并讨论算法性能的比较）
五、实验总结及自我评价（可含个人心得体会）
（对实验中遇到的问题、难点及解决方法进行总结：
自己在实验中的有哪些体会；
对个人能力的评价。
）
整个赛程，当N为偶数的时候，N-1天能够结束。
而当N为奇数的时候，只能在至少N天结束。
比如N=3的时候，每场必须有两个人，则每天只能有一场比赛，假设是1和2比赛，则3号运动员没有对象比赛，所以一天最多一场比赛，这个比赛需要的比赛场数C=3场，则整个比赛需要的天数为C/1=3天。
题目存在疑点。
六、参考文献
算法设计与实验题解主编：
王晓东电子工业出版社
指导教师批阅意见：
成绩评定：
指导教师签字：
年月日
备注：
注：
一、报告内的项目或内容设置，可按如实际情形加以调整和补充。
二、教师批改学生实验报告时刻应在学生提交实验报告时刻后10日内。
升级会员 