Round robin schedule problem

1. Problem description

Equipped with k(k=2^m) An athlete , Want to enter Row cycle " . Now we need to design a competition schedule that meets the following requirements ：

•  Each player has to work with others k-1 Each contestant has a competition ;

•  Each player can only play once a day ;

•   The round robin is going on k-1 God .

2. The experiment purpose

Through the practice of the round robin schedule , Familiar with the application of divide and rule .

3. analysis                              

Algorithm analysis ：

According to the divide and conquer strategy , We can divide all the players into two parts , be n Each player's schedule can be approved by n/2 The competition schedule of the players . Recursively divide the players into two parts , Until there are only two players left , It's easy to make a schedule . At this time, just let these two players compete . Pictured above , The list of squares is 8 The competition schedule of the players . The upper left corner and the lower left corner are players 1 To contestants 4 And players 5 To contestants 8 front 3 Day's game schedule . Accordingly , Copy all the numbers in the upper left corner to the lower right corner according to their relative positions , Then copy all the numbers in the small block in the lower left corner to the upper right corner according to their relative positions , In this way, we will arrange the players separately 1 To contestants 4 And players 5 To contestants 8 After 4 Day's game schedule . According to this idea, it is easy to generalize this schedule to the situation with any number of players .

The number of K=2:

The number of K=4:         

The number of K=8:

And so on , It's not hard to see , We can divide and conquer , Now it's broken down from top to bottom , Until it's broken down to the simplest case , That is, the number of people is 2 people , Then we can play in pairs , The table is filled in diagonally , Then fill in the form from the bottom up , It's easy to understand the above circulation table .

4. Source code display

 public static int[][] table(int n){
     //   int n = k<<1;
        int[][] a = new int[n][n];
        // Construct the first row of the schedule data 
        for(int i = 0; i<n;i++)
            a[0][i] = i+1;
        // Use divide and conquer algorithm , Construct the entire schedule 
        for(int r = 1;r<n;r<<=1){
            for(int i =0;i<n;i += 2*r){
                copy(a,r,r+i,0,i,r);
                copy(a,r,i,0,r+i,r);
            }
        }
        return a;
    }
    
    private 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];
            }
        }
        
    }
    public static void main(String[] args) {
        System.out.println(" Please enter the number of participants ：");
		Scanner scan =new Scanner(System.in);
		Integer read = scan.nextInt();
		int num=read.intValue();
		if(num%2!=0) {
			System.out.println(" The number of people entered does not meet the requirements ");
			System.exit(0);
		}
        int[][] a = table(num);
        for(int i=0;i<a.length;i++){
            for(int j = 0;j<a[0].length;j++){
                System.out.print(a[i][j] + "|");
            }
            System.out.println();
        }

    }

}

5. Program results display