问题
一年一度的欧洲冠军杯比赛已经落幕，其在初赛阶段采用循环制，设共有n队参加，初赛共进行n-1天，每队要和其他各队进行一场比赛，然后按照最后积分选拔进入决赛的球队。要求每对每天只能进行一场比赛，并且不能轮空。请按照上述需求安排比赛日程，决定每天各队的对手。
思路1
按照题目所指的就是每个队要和其他各队进行一场比赛，而不是两两PK淘汰一队那种赛制，就是不是16进8，8进4，4进2，2进1那种比赛。于是这就可以列出一张表来来解答。每个队每天只能比赛一场，那说明这个表格的纵向是不能够重复的。每个队要和其他队进行比赛说明表格的横向是不能重复的。这个问题时很抽象的，因为一开始你根本就摸不清什么是小问题，什么又是大问题。网上的说法是很奇怪，似乎作者们早已经知道日程安排表的样子，并且规律摸得很清，然后直接想都没想就写了递归算法来解决此问题，我觉得这不符合常识，因为他们并没有说他们是如何看出这个规律的，并且网上的限制很严重还必须是偶数支队伍的比赛。你要知道队伍的多少实际上是没有奇偶数的限制的。其实只要满足横行和竖行都没有重复的元素就可以了，于是我画了张表格发现斜线都是一样的，于是得出算法实现。
思路2
使用分治策略思想。我觉得这个实用价值实在不大，而是为了应用分治算法而使用分治算法。输入的队伍的数量比如是2的幂次才行，因为如果你仔细看它那张表的话会发现它是把整张表，连同队伍编号那一栏也算进，是横竖两刀把整个表分成了4个部分，其中左上部分和右下部分一样，左下部分和右上部分一样。然后它每个部分也是这样的结构，这就是它所谓的问题和子问题之间的关系。你还要保证第一列是从1到max的。所以它是从2阶小方块慢慢扩大到2n阶方块的。处理的过程是先把左上矩阵计算出来，然后是左下矩阵，然后是复制左下矩阵到右上矩阵，最后是复制左上矩阵到右下矩阵，所以列的话应该用每个矩阵的长度作为起始下标。
使用
package com.company;
public class Main {
public static void main(String[] args) {
// write your code here
Solution.raceSchedule0(8);
}
}
输出
1 2
2 1
1 2
2 1
3 4
4 3
1 2 3 4
2 1 4 3
3 4
4 3
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
5 6
6 5
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
5 6
6 5
7 8
8 7
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
5 6 7 8
6 5 8 7
7 8
8 7
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
5 6 7 8
6 5 8 7
7 8 5 6
8 7 6 5
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
5 6 7 8
6 5 8 7
7 8 5 6
8 7 6 5
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
6 5 8 7
7 8 5 6
8 7 6 5
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
No. D1 D2 D3 D4 D5 D6 D7
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
Process finished with exit code 0
实现
package com.company;
public class Solution {
/**
* 循环赛日程表
* @param ranksNumber
*/
static public void raceSchedule(int ranksNumber) {
if (ranksNumber < 2) {
System.out.println("无需安排");
return;
}
int[][] resultArray = new int[ranksNumber][ranksNumber];
for (int counter = 0;counter < ranksNumber;counter++) {
resultArray[counter][0] = counter + 1;
for (int counter1 = 1;counter1 < ranksNumber;counter1++) {
resultArray[counter][counter1] = resultArray[counter][counter1 - 1] + 1;
if (resultArray[counter][counter1] > ranksNumber)resultArray[counter][counter1] = 1;
}
}
for (int counter = 0;counter < ranksNumber;counter++) {
if (counter == 0)System.out.print("No.\t");
else System.out.print("D" + counter + "\t");
}
System.out.println();
for (int counter = 0;counter < ranksNumber;counter++) {
for (int counter1 = 0;counter1 < ranksNumber;counter1++) {
System.out.print(resultArray[counter][counter1] + "\t");
}
System.out.println();
}
}
/**
* 本算法采用分治策略来解决。
* @param ranksNumber
*/
static public void raceSchedule0(int ranksNumber) {
//判断它是不是2的次幂，并且它还必须至少是2.
if (!isPowerOfTwo(ranksNumber) || ranksNumber < 2) {
System.out.println("输入错误");
return;
}
int[][] scheduleArray = new int[ranksNumber][ranksNumber];
Solution.dAndC(scheduleArray,1,ranksNumber,ranksNumber);
for (int counter = 0;counter < ranksNumber;counter++) {
if (counter == 0)System.out.print("No.\t");
else System.out.print("D" + counter + "\t");
}
System.out.println();
for (int counter = 0;counter < ranksNumber;counter++) {
for (int counter1 = 0;counter1 < ranksNumber;counter1++) {
System.out.print(scheduleArray[counter][counter1] + "\t");
}
System.out.println();
}
}
/**
* 分治策略的迭代部分
* @param scheduleArray
* @param number
* @param length
* @param ranksNumber
*/
static private void dAndC(int[][] scheduleArray,int number,int length,int ranksNumber) {
//如果就2个队伍就很简单了，就是2个斜方向的问题了。
if (length == 2) {
scheduleArray[number - 1][0] = number;
scheduleArray[number][1] = number;
scheduleArray[number - 1][1] = number + 1;
scheduleArray[number][0] = number + 1;
} else {
int halfLength = length / 2;
//迭代处理左上角方阵。
Solution.dAndC(scheduleArray,number,halfLength,ranksNumber);
Solution.printMatrix(scheduleArray,ranksNumber);
//迭代处理左下角方阵。
Solution.dAndC(scheduleArray,number + halfLength,halfLength,ranksNumber);
Solution.printMatrix(scheduleArray,ranksNumber);
//接下来把左下的方阵复制到右上角的方阵去
for (int counter = number - 1;counter < number - 1 + halfLength;counter++)
for (int counter0 = halfLength;counter0 < length;counter0++)
scheduleArray[counter][counter0] = scheduleArray[counter + halfLength][counter0 - halfLength];
Solution.printMatrix(scheduleArray,ranksNumber);
//接下来把左上的方阵复制到右下角的方阵去
for (int counter = number - 1 + halfLength;counter < number - 1 + length;counter++)
for (int counter0 = halfLength;counter0 < length;counter0++)
scheduleArray[counter][counter0] = scheduleArray[counter - halfLength][counter0 - halfLength];
Solution.printMatrix(scheduleArray,ranksNumber);
}
}
/**
* 打印矩阵
* @param scheduleArray
* @param rank
*/
static private void printMatrix(int[][] scheduleArray,int rank) {
for (int counter = 0;counter < rank;counter++) {
for (int counter1 = 0;counter1 < rank;counter1++) {
if (scheduleArray[counter][counter1] == 0)System.out.print(" ");
else System.out.print(scheduleArray[counter][counter1] + " ");
}
System.out.println();
}
System.out.println();
}
/**
* 判断一个数是不是2的幂次
* @param number
* @return
*/
static private boolean isPowerOfTwo(int number) {
int bitFlag = 1;
int bitSum = Integer.SIZE - 1;//不算符号位
int bitIterator = 0;
int oneCounter = 0;
while (bitIterator < bitSum) {
if ((bitFlag & number) != 0) {
oneCounter++;
if (oneCounter > 1)
return false;
}
bitFlag = bitFlag << 1;
bitIterator++;
}
return true;
}
}
网友评论