《算法与程序计》
--课程设计报告
一.课程设计名称:
循环赛日程表
二.实验内容
问题描述:
设有n位选手参加网球循环赛,n=2^k,循环赛共进行n-1天,每位选手要与其他n-1位选手比赛一场,且每位选手每天比赛一场,不能轮空,按一下要求为比赛安排日程,
(1)每位选手必须与其他n-1格选手格赛一场;
(2)每个选手每天只能赛一场;
(3)循环赛一共进行n-1天;
请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行和第j列处填入第i个选手在第j天所遇到的选手,其中1≤i≤n,1≤j≤n-1。
三.实验目的
1.运用分治法,设计解决上述问题的算法,设计出比赛日程表,在表中的第i行和第j列处填入第i个选手在第j天所遇到的选手(其中1≤i≤n,1≤j≤n-1)。
2.掌握分治算法的应用。
四.算法原理
运用分治法,将原问题划分为较小问题,然后由较小问题的解得出原问题的解。
1.分治法:对于一个规模为n的问题,若该问题可以容易的解决(比如说规模n较小),则直接解决,否则将其分解为k个规模较小的子问题,这些子问题相互独立且与原问题形式相同,递归的解决这些子问题,然后将个子问题的解合并,得到原问题的解。
2.分治法的解题步骤(由三个步骤组成)
●划分(divide):将原问题分解为若干个规模较小、相互独立、与
原问题形式相同的子问题。
●解决(conquer):若子问题规模较小,则直接求解;否则递归求
解各子问题。
●合并(conbine):将各子问题的解合并为原问题的解
五.问题分析
假设n位选手顺序编号为1,2,3……n,比赛的日程表是一个n 行n-1列的表格。i行j列的表格内容是第i号选手在第j天的比赛对手。
根据分而治之的原则,可从其中以半选手的比赛日程,导出全体n位选手的的日程,最终细分到只有两位选手的比赛日程出发。
六.设计步骤
1.先设计主函数(main函数),然后设计两个函数,分别是安排赛事进行填制表格的函数(void arrangement(int n,int N,int k,int a[100][100])函数)和输出到屏幕函数(void print(int n,int
a[100][100]))。
2.在主函数(main())里调用void arrangement()函数,对比赛日程进行安排,根据分而治之原则,绘制比赛日程表格,然后调用void print()函数,将安排好的比赛日程输出到屏幕上。
七.关键数据结构
1.运用一个二维数组a[i][j],对安排好的赛事日程进行排列和保存,并在屏幕上输出。
2.使用二维数组的原因:因为根据题目要求,比赛日程表是一个n行n-1列的表格,用a[i][j]代表第i号选手在第j天遇到的对手,所以用一个二维数组表示。
八.程序结构
程序主要由三个函数组成:
(1)main()函数(主函数),
(2)void arrangement()函数(本程序的核心函数),
(3)print函数(输出函数)
3.print()函数
九.关键程序功能及其实现的说明
1. .main()函数
(1)函数功能:在屏幕上输入k值,计算参赛人数n,然后调用void arrangement()函数和print()函数。
(2)函数实现:
①先定义一个k,然后在键盘上输入一个k值,并赋值给k(假设输入3);
②运用for循环,计算参赛人数n的值
for (int i=1;i<=k;i++)
n *= 2;
可得n=8,即有八个人参赛。
③然后调用void arrangement()函数和print()函数,并传值。
2.void arrangement()函数
(1)函数功能:对所有运动员的赛程进行安排,并将其存入数组内。
(2)函数实现:由main()函数得到k值为3,n值为8
①用一个for循环输出日程表的第一行
for(int i=1;i<=N;i++)
a[1][i] = i;
②然后定义一个m值,m初始化为1,m用来控制每一次填充表格时i (i表示行)和j(j表示列)的起始填充位置。
③用一个for 循环将问题分成几部分,对于k=3,n=8,将问题分成3大部分,第一部分为,根据已经填充的第一行,填写第二行,第二部分为,根据已经填充好的第一部分,填写第三四行,第三部分为,根据已经填充好的前四行,填写最后四行。
for (int s=1;s<=k;s++) N/=2;
④用一个for 循环对③中提到的每一部分进行划分
for(int t=1;t<=N;t++)
对于第一部分,将其划分为四个小的单元,即对第二行进行如下划分
同理,对第二部分(即三四行),划分为两部分,第三部分同理 ⑤最后,根据以上for 循环对整体的划分和分治法的思想,进行每一个单元格的填充。填充原则是:对角线填充 for(int i=m+1;i<=2*m;i++) //i 控制行 for(int j=m+1;j<=2*m;j++) //j 控制列 {
a[i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m];/*右下角的值等于左上角的值 */
a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2];/*左下角的值等于右上角的值 */ }
例:由初始化的第一行填充第二行
由s控制的第一部分填完。然后是s++,进行第二部分的填充
1 2 3 4 5 6 7 8
2 1 4
3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6
5 最后是第三部分的填充
⑥这样循环,直到填充完毕,a[][]数组被赋予新值。
3.print()函数
(1)函数功能:将安排好的赛事日程,即二维数组a[n][n-1]输出到屏幕。
(2)函数主要功能实现:
函数主要运用一个for循环,将二维数组a[n][n-1]输出到屏幕。for( int i=1;i<=n;i++)//控制行
{
cout< for(int j=2;j<=n;j++) //控制列 cout< cout< } 十.程序运行结果 十一.体会 程序主要运用了:数据输入、函数调用、函数传值、for循环以及二维数组等主要结构和功能。根据分治算法,将本问题进行了由小规模到大规模的求解设计,程序设计的关键点在于如何对问题进行划分和填充公式的归纳。在划分时,主要运用了两个for循环;在填充时,运用了两个for循环。 通过这次程序设计,加深了对分治算法的认识。解决具体问题时,程序故重要,但一个好的算法更加重要。 本程序的得意之处在于,经过仔细研究,找到了划分的方法,并推导出了表格填充的两个公式。不足之处也在此,即花费了很长时间来推导这个,对算法掌握还不够熟练。 十二.工具软件及运行环境 1.工具软件:Microsoft Visual C++ 6.0 2.运行环境:Win32 Console Application 附: #include #include using namespace std; void print(int n,int a[100][100]); void arrangement(int n,int N,int k,int a[100][100]); int main() { int k; int a[100][100]; int n=1; cout<<"请输入k"< cin >> k; for (int i=1;i<=k;i++) n *= 2;//n=2^k cout<<"参赛人数"< int N=n; arrangement(n, N, k, a); print(n,a); } void arrangement(int n,int N,int k,int a[100][100]) { for(int i=1;i<=N;i++) { a[1][i] = i; } int m =1; for (int s=1;s<=k;s++) { N/=2; for(int t=1;t<=N;t++) { for(int i=m+1;i<=2*m;i++) for(int j=m+1;j<=2*m;j++) { a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m *2-m]; a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)* m*2]; } } m *= 2; } } void print(int n,int a[100][100]) { cout<<"------------------------------"<<"循环赛日程表"<<"------------------------------"< cout< cout<<"日期"; for(int p=1;p cout< cout< for( int i=1;i<=n;i++) { cout< for(int j=2;j<=n;j++) cout< cout< } }