分治与递归

实验一：分治与递归

【实验目的】

深入理解分治法的算法思想，应用分治法解决实际的算法问题。

【实验性质】

验证性实验（学时数：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为偶数。