一、算法思路

1、思路

分治算法的思想是：对于一个规模位N的问题，若该问题可以容易解决（比如规模N较小），则直接解决，否则将其分解为M个规模较小的子问题，这些子问题互相独立，并且与原问题形式相同，递归的解决这些子问题，然后将各子问题的解合并得到原问题的解

2、分治法适用范围

一般具有以下特征的问题可以使用分治算法求解：

（1）求解问题可以分解为若干个规模较小的相同问题

（2）求解问题的规模分解到一定程度，就能够很容易地求解

（3）合并子问题的解可以得到问题的解

（4）由求解问题所分解的各个子问题是互相独立的

3、分治法的步骤

（1）分解：将要求解的问题划分为规模较小的同类问题

（2）求解：当子问题划分的足够小的时候，用比较简单的方法求解，得到子问题的解

（3）合并：按求解问题的要求，将子问题的解逐层合并，即可构成最终的解

二、分治法实例：比赛日程的安排

1、问题描述

某学校举行乒乓球比赛，在初赛阶段设置为循环赛，设有n位选手参赛，初赛共进行n-1天，每位选手要与其他每一位选手进行一场比赛，然后按积分排名选拔进入决赛的选手。根据学校作息时间，要求每位选手每天必须比赛一场，不能轮空。按此要求为比赛安排具体日程，即决定每天各选手对阵的对手

2、分析

设有n=2^k个选手参加循环赛，那么需要要求设计一个满足以下要求比赛日程表：

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

2）每个选手一天只能赛一次

3、图解

（1）2个选手的情况

如果只有两个选手，那么第0列看作选手编号（我们从0开始对列编号，我们的第0列可以看作每个选手第0天在和自己打），第1列就是在第一天，每个选手要比赛的选手号

（2）如果选手的个数为2^2=4，那么日程安排如下图

如果有4个选手，分别设计4/2=2个选手的比赛日程表，1-2选手前一天的比赛日程表如上图表格左上角的深蓝色子表格部分，3-4选手前一天的比赛日程表如上图表格左下角的子表格。据此，后两天的日程表可以将左上角的子表按其对应位置抄到右下角的子表，左下角的子表可以按其对应位置抄到右上角的子表。（同时，我们注意到，这是表的行列均为参赛选手数2^2 = 4，在用分治法求行、列均为（2^2）/2的长度的子表时，首先确定左上角的子表，左下角的子表可以由左上角的子表加（2^2）/2得到）

（3）如果选手的个数为2^3=8，那么日程安排表如下：

选手人数为8时，左上角的子表是选手1至选手4的前三天的比赛日程，左下角是选手5至选手8前三天的比赛日程。据此后四天的比赛日程，就是分别将左上角子表按其对应位置抄到右下角，将左下角的子表按其对应位置抄到右上角。这样就完成了比赛日程的安排

这种解法是把求解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）求右下角子表：等于左上角子表的对应元素

代码实现如下：

#include <stdio.h>

#include <stdlib.h>

int main(void)

{

int a[9][9];

int x,y,i,j,t;

for(x=0;x<9;x++){

for(y=0;y<9;y++){

a[x][y]=0;

}

}

int n=2;

a[1][1]=1;

a[1][2]=2;

a[2][1]=2;

a[2][2]=1;

for(t=1;t<3;t++){

/*使用分治法填充日程表*/

int 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][j-temp]+temp;

/*扩展右下角*/

for(i=temp+1;i<=n;i++){

for(j=temp+1;j<=n;j++)

a[i][j]=a[i-temp][j-temp];

}

}

//打印结果

for(i=0;i<9;i++){

for(j=0;j<9;j++){

printf("%d ",a[i][j]);

}

printf("\n");

}

return 0;

}