循环日程安排问题（分治法）

日程安排问题（分治法）"/>

循环日程安排问题（分治法）

函数接口定义：
void Plan(int a[][N],int k);
裁判测试程序样例：
#include
#include <math.h>
#include
using namespace std;
#define N 100

void Plan(int a[][N],int k);

int main()
{ int i,j,a[N][N],k,size;
cin>>k;
size=pow(2,k);
Plan(a,k);
for(i=1;i<=size;i++){
for(j=1;j<=size;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;

}

/* 请在这里填写答案 */

输入样例：

输入K值。

3

输出样例：

输出比赛日程表。

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

idea

• 满足需求的日程表规律：若日程表划分为四个相同规模的四部分，则对角的两部分相同，左右相邻的两部分相差子部分边长大小
  =>属于可以划分为子问题的类型，当只有一个选手时为递归出口
  右上角 = 左上角 + 子部分边长（相邻关系）
  左下角 = 右上角（对角关系）
  右下角 = 左上角 （对角关系）

solution

void Plan(int a[][N],int k){if(k == 0){a[1][1] = 1;return ;};Plan(a, k - 1);int n = 1;for(int i = 0; i < k; i++)n *= 2;int size = n / 2;for(int i = 1; i <= size; i++){for(int j = 1; j <= size; j++){a[i][j + size] = a[i][j] + size;a[i + size][j] = a[i][j + size];a[i + size][j + size] = a[i][j];}}
}