河北工业大学算法实验 下载本文

内容发布更新时间 : 2024/12/26 4:22:15星期一 下面是文章的全部内容请认真阅读。

河北工业大学算法实验

算法分析与设计

: 班级: 姓名: 学号:

实验报告

计算机科学与软件学院 计131班 张硕 133020 1 / 21

学院

河北工业大学算法实验

实验一 利用分治算法,编程实现循环赛日程表安排问题

一、实验内容

1.实现《网球循环赛》问题的分治算法,并进行算法时间复杂性分析。 2.对实现的分治算法进行改进;

3.对上述改进后算法进行时间复杂性分析,通过实验结果分析对比,得出自己的结论和总结。

4. 设计的程序要满足正确性,代码中有关键的注释,书写格式清晰,简洁易懂,效率较高,利用C++的模板,设计的程序通用性好,适合各种合理输入,并能对不合理输入做出正确的提示。 二、实验目的

1.深刻理解并掌握“分治算法”的设计思想; 2.提高应用“分治算法”设计技能;

3.理解这样一个观点:用递归方法编写的问题解决程序具有结构清晰,可读性强等优点,且递归算法的设计比非递归算法的设计往往要容易一些,所以当问题本身是递归定义的,或者问题所涉及到的数据结构是递归定义的,或者是问题的解决方法是递归形式的时候,往往采用递归算法来解决。 三、程序清单 (1)递归: #include int p[128][128]; void fenpei(int a) {

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<<\ \

for(int i=1;i

cout<

3 / 21