简介

使用分治法解决循环赛日程表问题，解决问题规模大于等于2的情况（奇数及偶数）

  • 每个选手必须与其他n-1个选手各赛一场
  • 每个选手一天只能赛一次
  • 循环赛一共进行n-1天

代码

  • 特殊情况：n = 2k
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    n = mp = None


    def combine(n):
        for i in range(n):
            for j in range(n):
                mp[i][j + n] = mp[i][j] + n
                mp[i + n][j] = mp[i][j + n]
                mp[i + n][j + n] = mp[i][j]


    def divide(n):
        if n == 1:
            mp[0][0] = 1
            return
        divide(n // 2)
        combine(n // 2)


    n = int(input())
    mp = [[0] * n for v in range(n)]
    divide(n)
    for r in mp:
        print(str(r[0]) + "号选手:", r[1:])
  • 奇数&偶数情况
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    mp = a = None


    def Codd(n):
        m = n // 2
        for i in range(1, m + 1):
            a[i] = a[m + i] = m + i
        for i in range(1, m + 1):
            for j in range(1, m + 2):
                if mp[i][j] > m:
                    mp[i][j] = a[i]
                    mp[m + i][j] = (a[i] + m) % n
                else:
                    mp[m + i][j] = mp[i][j] + m
            for j in range(2, m + 1):
                mp[i][m + j] = a[i + j - 1]
                mp[a[i + j - 1]][m + j] = i


    def Ceve(n):
        m = n // 2
        for i in range(1, m + 1):
            for j in range(1, m + 1):
                mp[i][j + m] = mp[i][j] + m
                mp[i + m][j] = mp[i][j + m]
                mp[i + m][j + m] = mp[i][j]


    def divide(n):
        if n == 1:
            mp[1][1] = 1
            return
        if n & 1:
            divide(n + 1)
        else:
            divide(n // 2)
            Codd(n) if n // 2 > 1 and n // 2 & 1 else Ceve(n)


    n = int(input())
    SIZE = n + (n & 1) + 1
    mp = [[0] * SIZE for v in range(SIZE)]
    a = [0] * SIZE
    divide(n)
    print("   ", end="")
    for i in range(1, SIZE - 1):
        print(i, end="  ")
    print()
    for r in mp[1:n + 1]:
        print(r[1], r[2:SIZE])