2.2 分治法
2.2.1 分治法的设计思想
分治者，分而治之也。分治法（divideandconquermethod）的设计思想是将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。由分治法产生的子问题往往是原问题的较小模式，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到能够直接求解，这自然导致递归。分治与递归经常同时应用在算法设计之中，并由此产生许多高效的算法。
一般来说，分治法的求解过程由以下三个阶段组成：
（1）划分：把规模为n的原问题划分为k个规模较小的子问题。
（2）求解：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。
（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。
人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k=2），这种使子问题规模大致相等的做法是出自一种平衡（bal-ancing）子问题的启发式思想。另外，在用分治法设计算法时，最好使各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地求解公共的子问题，此时虽然也可以用分治法，但一般用动态规划法较好。图2-2所示是分治法的典型情况。
图2-2 分治法的典型情况
例如，对于给定的整数a和非负整数n，采用分治法计算an的值，如果n=1，可以简单地返回a的值；如果n＞1，可以把该问题分解为两个子问题：计算前└n/2」
个a的乘积和后「n/2┐个a的乘积，再把这两个乘积相乘得到原问题的解。所以，应用分治技术得到如下递推关系式：
同应用蛮力法把1和a相乘n次相比，这是一个更高效的算法吗？由于把原问题an分解为两个子问题a└n/2」和a「n/2┐，这两个子问题需要分别求解，根据1.4.3节通用分治递推式的定理，其时间复杂度为O（nlog2n），而蛮力法计算an的值，其时间复杂度为O（n）。因此，不是所有的分治法都比简单的蛮力法更有效，但是，正确使用分治法往往比使用其他算法设计方法的效率更高，事实上，分治法孕育了计算机科学中许多重要的和有效的算法。在本书中，二叉树的遍历、图的深度优先遍历、快速排序、归并排序等都是分治法的应用实例。
2.2.2 算法设计实例——数字旋转方阵
【问题】 输出如图2-3（a）所示N×N（1≤N≤10）的数字旋转方阵。
图2-3 数字旋转方阵示例
【想法】 用二维数组data[N][N]表示N×N的方阵，观察方阵中数字的规律，可以从外层向里层填数，如图2-3（b）所示。在填数过程中，每一层的起始位置很重要。设变量size表示方阵的大小，则初始时size=N，填完一层则size=size-2；设变量begin表示每一层的起始位置，变量i和j分别表示行号和列号，则每一层初始时i=begin，j=begin。将每一层的填数过程分为A、B、C、D四个区域，每个区域需要填写size-1个数字，且填写区域A时列号不变行号加1，填写区域B时行号不变列号加1，填写区域C时列号不变行号减1，填写区域D时行号不变列号减1。显然，递归的边界条件是size等于0或size等于1。
【算法】 设递归函数Full实现填数过程，算法用伪代码描述如下 ：
算法：Full（number，begin，size）
输入：当前层左上角要填的数字number，左上角的坐标begin，方阵的阶数size
输出：数字旋转方阵
1.如果size等于0，则算法结束；
2.如果size等于1，则data[begin][begin]=number，算法结束；
3.初始化行、列下标i=begin，j=begin；
4.重复下述操作size-1次，填写区域A：
4.1 data[i][j]=number；number++；
4.2 行下标i++；列下标不变；
5.重复下述操作size-1次，填写区域B：
5.1 data[i][j]=number；number++；
5.2 行下标不变；列下标j++；
6.重复下述操作size-1次，填写区域C：
6.1 data[i][j]=number；number++；
6.2 行下标i--；列下标不变；
7.重复下述操作size-1次，填写区域D：
7.1 data[i][j]=number；number++；
7.2 行下标不变，列下标j--；
8.调用函数Full在size-2阶方阵中左上角begin+1处从数字number开始填数；
【程序】 由于递归函数Full在调用过程中需要对同一个数组data[N][N]填数，为避免传递参数，将数组data[N][N]设为全局变量，程序如下：
#include＜stdio.h＞ //使用库函数printf和scanf
#defineN10 //定义符号常量N
intdata[N][N]={0}； //定义全局数组data[N][N]并初始化为0
voidFull（intnumber，intbegin，intsize）； //函数声明，填写旋转方阵
voidOutPrint（intsize）； //函数声明，输出旋转方阵
//空行，以下是主函数
intmain（）
{
intn；
printf（＂请输入方阵的阶数（小于10）：＂）； //输出提示信息
scanf（＂%d＂，&n）；
Full（1，0，n）； //函数调用，从1开始填写n阶方阵，左上角的下标为（0，0）
OutPrint（n）； //函数调用，输出n阶方阵
return0； //将0返回操作系统，表明程序正常结束
}
//空行，以下是其他函数定义
voidFull（intnumber，intbegin，intsize）
{ //从number开始填写size阶方阵，左上角的下标为（begin，begin）
inti，j，k；
if（size==0） //递归的边界条件，如果size等于0，则无须填写
return；
if（size==1） //递归的边界条件，如果size等于1
{
data[begin][begin]=number； //则只须填写number
return；
}
i=begin；j=begin； //初始化左上角下标
for（k=0；k＜size-1；k++） //填写区域A，共填写size-1个数
{
data[i][j]=number；number++； //在当前位置填写number
i++； //行下标加1
}
for（k=0；k＜size-1；k++） //填写区域B，共填写size-1个数
{
data[i][j]=number；number++； //在当前位置填写number
j++； //列下标加1
}
for（k=0；k＜size-1；k++） //填写区域C，共填写size-1个数
{
data[i][j]=number；number++； //在当前位置填写number
i--； //行下标减1
}
for（k=0；k＜size-1；k++） //填写区域D，共填写size-1个数
{
data[i][j]=number；number++； //在当前位置填写number
j--； //列下标减1
}
Full（number，begin+1，size-2）； //递归调用，左上角下标为begin+1
return； //结束函数Full的执行
}
voidOutPrint（intsize） //函数调用，输出size阶方阵
{
inti，j；
for（i=0；i＜size；i++） //输出第i行
{
for（j=0；j＜size；j++） //输出第j列
printf（＂%4d＂，data[i][j]）；
printf（＂\n＂）； //输出一行后输出换行符
}
return； //结束函数OutPrint的执行
}