循环日赛表的分治实现

                                 循环日赛表的分治实现

 

 

 

 实现循环赛日程表。

设 有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：

   （1）每个选手 必须与其它n-1个选手各赛一次

   （2）每个选手一天只能赛一场

   （3）循环赛进行n-1天

 

基本思路：

  按分治策略，将所有的的选手分为两组，N和选手的比赛日程表就可以通过N/2个选手设计的日程来决定。递归的对选手进行分割，直到只剩下2个选手时，比赛的日程表就变得简单。这时只要让这两个选手进行比较近好了。

 

实现思路：

   我们可以创建一个二维数组来存放数据，int [][]table=new int[num][num];

   在第一行和第一列放入数据来初始化数组

 

然后对数组进行递归处理
 将左上角的数据写到右下角的数据，将右上角的数据写到左下角的数据。

看代码吧

private void sort(int x, int y, int step) {
	
		//如果递归到只剩下一步，即只剩下两个对手，返回
		if(step==1)return;
		
		step/=2;
		
		//对左上右下的这条对角线上的数据进行递归
		sort(x, y, step);
	
		//对右上左下的数据进行递归
		sort(x,y+step,step);
		
		for(int i=0;i<step;i++)
			//对每个分区进行赋值
			for(int j=0;j<step;j++){
				//右下角的数据等于左上角的数据
				table[x+step+i][y+step+j]=table[x+i][y+j];
			    //左下角的数据等于右上角的数据
				table[x+step+i][y+j]=table[x+i][y+step+j];
			
			}
	}

   

 下面是运行的效果

 

java文件见附件（全部代码） 

 

 

 

 

<!--EndFragment-->