问题:设有n=2^k个选手参加循环赛,要求设计一个满足以下要求比赛日程表:
1)每个选手必须与其它n-1个选手各赛一次;
2)每个选手一天只能赛一次。
这题刚开始乍一看是全排列,可是想多了,全排列的话太太复杂,递归是最好的方法,比较容易理解
这种解法是把求解2^k个选手的比赛日程问题划分为2^1,2^2,......,2^k个选手的比赛日程问题。也就是说,要求2^k个选手的比赛日程,就要分为两部分,分别求出2^(k-1)个选手的比赛日程,然后再进行合并。当然,这种解法只能求选手个数是2的次幂的情况。
在每次迭代求解的过程中,可以看作4部分:
1)求左上角子表:左上角子表是前2^(k-1)个选手的比赛前半程的比赛日程。
2)求左下角子表:左下角子表是剩余的2^(k-1)个选手的比赛前半程比赛日程。这个子表和左上角子表的对应关系式,对应元素等于左上角子表对应元素加2^(k-1)。
3)求右上角子表:等于左下角子表的对应元素。
4)求右下角子表:等于左上角子表的对应元素。
package test3; import java.util.*; public class Main { static int table[][] ; public static void f(int row,int col,int n){ if(n==1) return; int half = n/2; table[row+half][col+half]=table[row][col]; table[row][col+half]=table[row+half][col]=table[row][col]+half; f(row,col,half); f(row,col+half,half); f(row+half,col,half); f(row+half,col+half,half); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); table=new int[n][n]; table[0][0]=1; f(0,0,n); for(int []x:table){ for(int y:x) System.out.print(y+" "); System.out.println(); } } }