当前位置:文档之家› 循环赛日程表实验报告

循环赛日程表实验报告

《算法与程序计》

--课程设计报告

一.课程设计名称:

循环赛日程表

二.实验内容

问题描述:

设有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<

}

}

相关主题
相关文档 最新文档