用分治法求解循环日程安排问题。设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求的比赛日程表:
(1)每个选手必须与其他n-1个选手各赛一次。
(2)每个选手一天只能赛一次。
(3)循环赛在n-1天之内结束。
输入样例:
输入K值。
输出样例:
输出比赛日程表。
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(""); } } }
|