算法:7-1 循环日程安排问题

算法:7-1 循环日程安排问题

小颜同学 Lv4

用分治法求解循环日程安排问题。设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求的比赛日程表:
(1)每个选手必须与其他n-1个选手各赛一次。
(2)每个选手一天只能赛一次。
(3)循环赛在n-1天之内结束。

输入样例:

输入K值。

1
3

输出样例:

输出比赛日程表。

1
2
3
4
5
6
7
8
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
1
2
3
4
5
代码长度限制									    16 KB

时间限制 400 ms

内存限制 64 MB

代码演示:

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
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
int n,temp,i,j,t;
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
//选手的个数
int sum = (int) Math.pow(2,k);
int a[][] = new int[sum+1][sum+1];
n=2;
a[1][1]=1;
a[1][2]=2;
a[2][1]=2;
a[2][2]=1;
for (t=1; t<k; t++) {
temp=n;
n=n*2;
for (i=temp+1; i<=n; i++) {
for (j = 1; j <= temp; j++){
a[i][j] = a[i - temp][j] + temp;
}
}
for (i=1; i<=temp; i++) {
for (j = temp + 1; j <= n; j++) {
a[i][j] = a[i + temp][(j + temp) % n];
}
}
for (i=temp+1; i<=n; i++) {
for (j = temp + 1; j <= n; j++) {
a[i][j] = a[i - temp][j - temp];
}
}
}
for (int l = 1; l <= sum; l++) {
for (int m = 1; m <= sum; m++) {
System.out.print(a[l][m]+" ");
}
System.out.println("");
}
}
}
  • 标题: 算法:7-1 循环日程安排问题
  • 作者: 小颜同学
  • 创建于: 2022-10-26 12:03:00
  • 更新于: 2023-12-18 09:06:28
  • 链接: https://www.wy-studio.cn/2022/10/26/算法:7-1-循环日程安排问题/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
 评论
此页目录
算法:7-1 循环日程安排问题