资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

【分治法】循环赛日程表问题 C\C++（附代码、实例）

创作时间:

作者:

@小白创作中心

【分治法】循环赛日程表问题 C\C++（附代码、实例）

引用

CSDN

https://m.blog.csdn.net/lhr056813/article/details/145779776

问题描述

设计一个满足以下要求的比赛日程表：

每位选手必须与其他n-1个选手各赛一次
每位选手一天只能赛一次
循环赛一个进行n-1天
选手人数n = 2^k

问题分析

下图是一种日程表的安排方式

观察上图，我们发现日程表左上角的四行四列和右下角的四行四列完全一致，左下角的四行四列和右上角的四行四列也完全一致

那么我们可以得到一个思路，就是将大日程表一分为二，对两部分分别安排日程，然后再复制到对应的其他位置，获得整个大日程表

下面来看一下该问题是否满足分治法的四个条件：

大问题可以分成规模小的小问题。对日程表进行划分后，只有问题规模变小了，仍然是相同问题
问题小到一定规模后可以很容易的解决。当日程表是1x1的大小时，自己不用和自己安排比赛，也就不用再分再填了
子问题的解可以合成大问题的解。得到子问题的答案后，将子日程表依次复制到对角位置，就得到了大日程表，也就得到了大问题的解
分解出的各子问题互相独立（不重复）

综上所述，该问题满足分治策略的四个条件，可以用分治法解决

所以这个问题的解决方法就是，将对

位选手安排日程表的问题分成对前

n/2

位选手和后

n/2

位选手分别安排日程，再对每部分递归的分割，直到只剩下一个选手

代码

void table(int i, int j, int n) {//i j为表左上角的行号和列号，n为选手个数
    if (n > 1) {
        table(i, j, n / 2);
        table(i + n / 2, j, n / 2);
        copy(i, j, i + n / 2, j + n / 2, n / 2);
        copy(i + n / 2, j, i, j + n / 2, n / 2);
    }
    else
        a[i][j] = i + 1;
}

table

函数为

a[i][j]

到

a[i+n][j+n]

的子表安排日程，如果该表的大小为1x1，就把当前选手编号填进去，如果表的大小大于1x1，就递归的调用自身，为

a[i][j]

到

a[i+n/2][j+n/2]

和

a[i+n/2][j]

到

a[i+n][j+n/2]

的子表安排日程。再将安排好的日程表

copy

到对角部分

void copy(int x1, int y1, int x2, int y2, int n) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            a[i + x2][j + y2] = a[i + x1][j + y1];
}

copy

函数很简单，就是将

x1、y1

长度为n的日程表复制到

x2、y2

实例

#include<stdio.h>
int a[8][8];
void copy(int x1, int y1, int x2, int y2, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a[i + x2][j + y2] = a[i + x1][j + y1];
        }
    }
}
void table(int i, int j, int n) {//i j为表左上角的行号和列号，n为选手个数
    if (n > 1) {
        table(i, j, n / 2);
        table(i + n / 2, j, n / 2);
        copy(i, j, i + n / 2, j + n / 2, n / 2);
        copy(i + n / 2, j, i, j + n / 2, n / 2);
    }
    else
        a[i][j] = i + 1;
}
int main() {
    int n = 8;
    table(0, 0, n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

运行结果

非递归方法

使用非递归的方法解决这个问题，思路是逐步将已得到的日程copy到对角的区域中

对于下图，方法就是先分别将1至8号复制到对角区域，再将橙色区域copy到对角的橙色区域，将黄色区域copy到对角的黄色区域，下半部分同理；再将1-4的大区域copy到对角的浅蓝色区域，5-8copy到对角的深蓝色区域。最后就得到了8x8的日程表

代码

int main() {
    int n;
    n = 8;
    // 初始化第一天的比赛
    for (int i = 0; i < n; i++) {
        a[i][0] = i + 1;
    }
    int len = 1;
    // 使用迭代方法填充日程表
    for (int j = 0; j < n; j += len) {
        for (int i = 0; i < n; i += len * 2) {
            copy(i, 0, i + len, len, len);
            copy(i + len, 0, i, len, len);
        }
        len *= 2;
    }
    // 打印日程表
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

运行结果