2018-04-02练习

循环比赛日程表

【题目描述】

设有N个选手进行循环比赛,其中N=2M,要求每名选手要与其他N-1名选手都赛一次,每名选手每天比赛一次,循环赛共进行N-1天,要求每天没有选手轮空。

【输入】

输入:M。

【输出】

输出:表格形式的比赛安排表。一行各数据间用一个空格隔开。

【输入样例】

3

【输出样例】

1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1
刚看到题时,就感觉有点懵B,完全不知道如何下手,于是,我在excel表上枚举了当M为3和4时表格的情况,才慢慢有点思路,但是有些无法运用到分治算法之中

思路:根据观察,可将表格分为四部分,分别为ABCD,A与C完全相同,B与D完全相同,
附上M=3时
附上M=4时


只用求2部分,又可以根据每1个数字在斜线上的规律,可得出

的递归公式,顺便说一下,在一本通里我找到了这样的简便次方公式,妈妈再也不用担心我只会用for了!

 代码如下:

发现1:后来看书上发现了1个惊人的规律:右上角的表格由左上角的每1个元素+4组成!!!这样的话,问题就演变成几乎只要求左上角的表格就行了,so amazing!

发现2:将

1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1

分为4部分后,左上角等于右下角,再在A部分(左上角)再分为四部分,左上角依然等于右下角~~~~~得出了一个惊人的递归分割。

改进代码如下:

写的不好,神犇勿喷,谢谢!

原文地址:https://www.cnblogs.com/jr-ag/p/8698301.html