分治法-循环赛日程表

发表于： 分类于：
字数： 469 阅读：≈ 1分钟 浏览：

算法思想：分治法

实际问题：循环赛日程表

编写语言：Java

问题描述

假设有 n = 2^k 个运动员进行循环赛，要根据以下限制生成一个日程表： 1. 每个选手必须与其他 n - 1 个选手各赛一次 2. 每个选手一天只能赛一次 3. 循环赛一共进行 n - 1 天 生成内容：n行，n - 1列的表b，b(i)(j)表示选手i在j天遇到的对手

Java代码 

public class RoundRobinSchedule
{
    public static void main(String[] args)
    {
        int[][] table = getTable(3);
        for(int i = 0; i < table.length; i++)
        {
            for(int j = 0; j < table[0].length; j++)
                System.out.print(table[i][j] + " ");
            System.out.println();
        }
    }

    public static int[][] getTable(int k)
    {
        int n = 1 << k; //n = 2^k

        //构造第一行数作为初始数据
        int[][] a = new int[n][n];
        for(int i = 0; i < n; i++)
            a[0][i] = i + 1;

        /**
         * 将整个赛程表分为四个部分：
         * 左上角1：(0, i), 右上角2：(0, r + i)
         * 左下角3：(r, i), 右下角4：(r, r + i)
         * r为跨度，思想是将内容 1 复制到内容 4，将内容 2 复制到内容 3
        */
        //r是跨度，长度每次扩大一倍，跨度最小为1
        for(int r = 1; r < n; r <<= 1)
            for(int i = 0; i < n; i += r << 1) //起点每次跨越两倍长度
            {
                copy(a, r, r + i, 0, i, r); //左上角换到右下角
                copy(a, r, i, 0, r + i, r); //右上角换到左下角
            }

        return a;
    }

    public static void copy(int[][] a, int tox, int toy,
                            int fromx, int fromy, int r)
    {
        for(int i = 0; i < r; i++)
            for(int j = 0; j < r; j++)
                a[tox + i][toy + j] = a[fromx + i][fromy + j];
        //System.out.println();
    }
}

运行结果

结果示例