河北工业大学算法实验
算法分析与设计
: 班级: 姓名: 学号:
实验报告
计算机科学与软件学院 计131班 张硕 133020 1 / 21
学院
河北工业大学算法实验
实验一 利用分治算法，编程实现循环赛日程表安排问题
一、实验内容
1．实现《网球循环赛》问题的分治算法，并进行算法时间复杂性分析。 2．对实现的分治算法进行改进；
3．对上述改进后算法进行时间复杂性分析，通过实验结果分析对比，得出自己的结论和总结。
4. 设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。 二、实验目的
1．深刻理解并掌握“分治算法”的设计思想； 2．提高应用“分治算法”设计技能；
3．理解这样一个观点：用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。 三、程序清单 （1）递归： #include
int b=a/2; if(b>1) {
fenpei(b); for(int i=0;i for(int j=0;j p[i+b][j+b]=p[i][j]; 2 / 21 河北工业大学算法实验 } for(i=0;i p[i+b][j]=p[i][j]+b; } for(i=0;i p[i][j+b]=p[i+b][j]; } } else { p[0][0]=1; p[0][1]=2; p[1][0]=2; p[1][1]=1; } } int main() { int num; cout<<\请输入参赛队伍数：\ cin>>num; fenpei(num); cout<<\ \