设计要求

·功能设计

设有n位选手参加循环赛，n=2^k，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天比赛一场，不能轮空。 设计一个满足一下要求的循环比赛日程表: 1. 每个选手必须与其他n-1个选手比赛一次 2. 每个选手只能赛一次

3. 当n是奇数时，循环一共进行n天，n是偶数时，循环赛进行n-1天 4. k由用户输入

5. 选手人数n=2的k次方

比赛日程表设计成有n行和n-1列的一个表。

在表中的第i行和第j列处填入第i个选手在第j天所遇到的选手，其中1≤i≤n,1≤j≤n-1。

·设计思想

1.当输入的k值较小时，可直接解决。

当输入的值较大时，将这些分为相互与原问题形式相同，递归的解决。然后把个个分支合并。

2.运用分治法，设计解决上述问题的算法，设计出比赛日程表，在表中的第i行和第j列处填入第i个选手在第j天所遇到的选手（其中1≤i≤n,1≤j≤n-1）。 运用分治法，将原问题划分为较小问题，然后由较小问题的解得出原问题的解。

***分治法:对于一个规模为n的问题，若该问题可以容易的解决（比如说规模n较小），则直接解决，否则将其分解为k个规模较小的子问题，这些子问题相互且与原问题形式相同，递归的解决这些子问题，然后将个子问题的解合并，得到原问题的解。***

&&&分治法的解题步骤（由三个步骤组成）

~划分：将原问题分解为若干个规模较小、相互、与原问题形式相同的子

问题。

~解决：若子问题规模较小，则直接求解；否则递归求解各子问题。

~合并：将各子问题的解合并为原问题的解。

3. 假设n位选手顺序编号为1，2，3……n，比赛的日程表是一个n行n-1列的表格。i行j列的表格内容是第i号选手在第j天的比赛对手。

根据分而治之的原则，可从其中以半选手的比赛日程，导出全体n位选手的的日程，最终细分到只有两位选手的比赛日程出发。

4.将创建一个xunhuan类，有输入k函数，赛事安排函数，输出函数。

※注： 以上分治法是在百度上查的。 ·文件

1.xunhuan.h文件 此文件中包括 private: int k; public:

xunhuan();//构造函数

int get();//输入k值

void arrangement(int n,int N,int k,int a[100][100]);//安排赛事 void print(int n,int a[100][100]);//输出函数

2.main.cpp文件

main 函数的功能

(1)在屏幕上输入k值；

(2)参赛人数n；

运用for循环，计算参赛人数n的值 for (int i=1;i<=k;i++)

(3)调用void arrangement()函数；

n *= 2;

(4)调用print（）函数。 以下为main()函数的流程图

结束 调用print()函数，输出到屏幕 传值 调用void arrangement（）函数 参赛人数n=2^k 输出k值 输入k值 int k; main() 3.xunhuan.cpp文件 ·函数组成

1.输入k值函数int get()

2.安排赛事函数void arrangement() void arrangement()

函数功能：对所有运动员的赛程进行安排，并将其存入数组内。 函数实现：由main（）函数得到k值(以下以k=3为例) 用一个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++)

⑤最后，根据以上for循环对整体的划分和分治法的思想，进行每一个单元格的填充。填充原则是：对角线填充 {

N/=2;

④用一个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]; /*右下角的值等于左上角的值 */

输出函数void print() print（）

函数功能：将安排好的赛事日程，即二维数组a[n][n-1]输出到屏幕。 函数主要功能实现：

函数主要运用一个for循环，将二维数组a[n][n-1]输出到屏幕。

for( int i=1;i<=n;i++)//控制行

二、参考程序 1.xunhuan.h文件

{

cout<cout<a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2]; }

/*左下角的值等于右上角的值 */

}

class xunhuan { private:

int k;

xunhuan();//构造函数 int get();//输入k值

public:

void arrangement(int n,int N,int k,int a[100][100]);//安排赛事 void print(int n,int a[100][100]);//输出函数 };

2.main.cpp文件 # include \"xunhuan.h\" # include \"iostream.h\"

# include \"iomanip.h\" int main() {

xunhuan x; int a[100][100]; i=x.get(); int n=1;

cout<<\"请输入 k\"<int i;

cin >>i;

for (int j=1;j<=i;j++)

n *= 2;

cout<<\"参赛人数\"<x.arrangement(n, N, i, a); x.print(n,a); }

3. xunhuan.cpp文件 #include \"xunhuan.h\" # include \"iostream.h\" # include \"iomanip.h\"

xunhuan::xunhuan() { }

int xunhuan::get() { }

void xunhuan::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;

return k;

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 xunhuan::print(int n,int a[100][100]) { cout<<\"***********************\"<<\"

循

环

赛

\"<<\"***********************\"<cout<cout<<\"日期\";

程

表

日

}

for(int p=1;pcout<for( int i=1;i<=n;i++) { }

cout<cout<cout<三、程序的截图