分治法——循環賽日程表

1、問題描述：
有n=2^k個遠動員選手，設計比賽日程表實現：
（1）每個選手必須與n-1個選手比賽
（2）每個選手一天只比賽一場
（3）比賽共進行n-1天
輸入：n人
輸出：n行n-1列，第i行第j列表示第i個選手第j天遇到的對手，不包含第一列表示為選手編號

舉例：2人
? ? ?1 ? 2
? ? ?2 ? 1

2、問題分析
通過化大為小，分而治之的思想，將多人的比賽日程縮小為2人的日程。以此倒推所有人的日程。
注意多人日程規律：
以四人為例：
1 2 |?3 4
2 1 | 4 3
----------
3 4 |?1 2
4 3 | 2 1
這樣一個矩陣分為四個區，左上和右下一樣，左下和右上一樣，且右上是左上對應的數字加了n/2.

3、代碼實現

#include <stdio.h>
#include <string.h>

#define N 128
int matrix[N][N] = {0};

void fun(int n)
{
    int i;
    int j;
    if (n<=0)
    {
        return;
    }
    if (n>2)
    {
        fun(n/2);
        for (i=1;i<=n/2;i++)
        {
            for (j=n/2+1;j<=n;j++)
            {
                matrix[i][j] = matrix[i][j-n/2] + n/2;
            }
        }
        for (i=n/2+1;i<=n;i++)
        {
            for (j=1;j<=n/2;j++)
            {
                matrix[i][j] = matrix[i-n/2][j+n/2];
            }
        }
        for (i=n/2+1;i<=n;i++)
        {
            for (j=n/2+1;j<=n;j++)
            {
                matrix[i][j] = matrix[i-n/2][j-n/2];
            }
        }
    }
    else
    {
        matrix[1][1] = 1;
        matrix[1][2] = 2;
        matrix[2][1] = 2;
        matrix[2][2] = 1;
    }
}

void main()
{
    fun(8);
    
    int i,j;
    for (i=1;i<=8;i++)
    {
        for (j=1; j<=8; j++)
        {
            printf("%d ",matrix[i][j]);
        }
        printf("\n");
    }
}

http://blog.chinaunix.net/uid-26874207-id-4206383.html?utm_source=jiancool