分治与递归
实验一：分治与递归
【实验目的】
深入理解分治法的算法思想，应用分治法解决实际的算法问题。
【实验性质】
验证性实验（学时数：2H）
【实验内容与要求】
1、设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：⑴每个选手必须与其他n-1个选手各赛一次；⑵每个选手一天只能赛一次；⑶循环赛一共进行n-1天。按此要求可将比赛日程表设计成有n行和n列的一个表。表中第一列是选手编号，表中第i行和第j列（j>1）处填入第i个选手在第j天所遇到的选手。例如8个选手的日程表安排如右图所示。
要求：请设计算法，并采用C或C++语言编写程序实现上述功能，调试运行并对算法的时间复杂度进行分析。
【算法思想及处理过程】
首先，通过输入参赛人数n，判断n是否合法（是否为2的幂次方），如果不合法则输出错误信息。
然后，输入第一个选手的编号k。
调用roundrob函数，传入参数k和n。roundrob函数的作用是生成对阵表。
首先，判断n是否为2，如果是，则直接生成对阵表。对阵表是一个二维数组a，每个元素表示某个选手与另一个选手的对阵情况。
如果n不是2，递归调用roundrob函数，将n除以2传入，并分成两个子问题，分别解决。
递归结束后，对阵表的前一半行和后一半行进行交换，生成完整的对阵表。
最后，遍历对阵表，并输出每个元素的值。
在主函数中，先判断n是否合法，如果合法则调用roundrob函数生成对阵表，并输出。
如果n不合法，则直接返回。
【程序代码】
#include <stdio.h>
#include<iostream>
using namespace std;
int a[100][100]{};
void roundrob(int k, int n)
{
if (n == 2)
{
a[k][0] = k + 1;
a[k][1] = k + 2;
a[k + 1][0] = k + 2;
a[k + 1][1] = k + 1;
}
else
{
roundrob(k,n / 2);
roundrob(k + n / 2,n / 2);
}
for (int i = k; i < k + n / 2; i++)
{
for (int j = n / 2; j < n; j++)
{
a[i][j] = a[i + n / 2][j - n / 2];
}
}
for (int i = k + n / 2; i < k + n; i++)
{
for (int j = n / 2; j < n; j++)
{
a[i][j] = a[i - n / 2][j - n / 2];
}
}
}
int determine(int n)
{
if (n % 2 == 0)
{
if (n / 2 == 1) return 1;
determine(n / 2);
}
else
{
cout << "输入人数不合法" << endl;
return 0;
}
}
int main()
{
int n;
int k;
cout << "请输入参赛人数" << endl;
cin >> n;
if (determine(n) == 1)
{
cout << "请输入第一个选手编号" << endl;
cin >> k;
k = k - 1;
roundrob(k, n);
int i = 0, j = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
cout << a[i][j] << " ";
}
cout << endl;
}
}
if (determine(n) == 0)
{
return 0;
}
}
【运行结果】
程序运行结果截图。
【算法分析】
代码的时间复杂度为O(n^2)，其中n为参赛人数。代码中使用递归的方式生成了一个二维数组a，数组的大小为n×n。在生成数组a的过程中，有两个嵌套的循环，每个循环的次数都是n/2，因此循环次数总共为n/2 × n/2 = n^2/4，所以时间复杂度为O(n^2)。另外，代码中还有一个determine函数，该函数的时间复杂度为O(logn)，因为每次递归都将n除以2，直到n为偶数。