分治策略

　　任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题规模越小，解题所需的计算时间往往也越少，从而也越容易计算。想解决一个较大的问题，有时是相当困难的。分治法的思想就是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

　　分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的解。

　　1、解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的：
　　　
　　解决子问题所需的工作总量（由 子问题的个数、解决每个子问题的工作量 决定）
合并所有子问题所需的工作量

　　2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法

　　3、分治的具体过程：
　　 begin 　｛开始｝
　　　 if ①问题不可分 then ②返回问题解 　
　　　　 else begin
　　　　　　 　　③从原问题中划出含一半运算对象的子问题1；
　　　　　　 　　④递归调用分治法过程，求出解1；
　　　　　　 　　⑤从原问题中划出含另一半运算对象的子问题2；
　　　　　　 　　⑥递归调用分治法过程，求出解2；
　　　　　　 　　⑦将解1、解2组合成整修问题的解； 　
　　　　　　　end;
　　 end; {结束}

二、例题分析

　　 1、[金块问题]老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。

分析:问题可以简化为：在含n（n是2的幂（n>=2））个元素的集合中寻找极大元和极小元。

明显的方法是逐个的进行比较查找。

需要n-1次比较得到max，而再经过n-2次比较得到min，共进行2*n-3次比较可以找出极大元和极小元。

　　用分治法可以较少比较次数地解决上述问题：
　　 如果集合中只有1个元素，则它既是最大值也是最小值；
　　 如果有2个元素，则一次maxnum(i,j) 一次minnum(i,j)就可以得到最大值和最小值；
　　 如果把集合分成两个子集合，递归的应用这个算法分别求出两个子集合的最大值和最小值，最后让子集合1的最大值跟子集合2的最大值比较得到整个集合的最大值；让子集合1的最小值跟子集合2的最小值比较得到整个集合的最小值。

可得解题思想：

｛maxmin｝
　①if 问题不可分：n=2
　②问题的解求得（两个元素时）：对两元素进行比较;return;
　③for i:=1 to n div 2 do b[i]:=a[i]
　④maxmin(n div 2,b,max1,min1)，其中max1和min1为解1
　⑤for i:=1 to n div 2 do b[i]:=a[i+ n div 2]
　⑥maxmin(n div 2,b,max2,min2)，其中max2和min2为解2
　⑦max:=maxnum(max1,max2);
　　min:=minnum(min1,min2);
{maxmin}

其中对函数maxnum的求精：
function maxnum(a,b:integer):integer;
　begin
　　if a>b then maxnum:=a else maxnum:=b;
　end;

分析比较次数：
比较运算均在函数maxnum和minnum中进行，
当n=2时，比较次数T(n)=1
当n>2时，比较次数T(n)=2T(n/2)+2
∵n是2的k次幂
∴设n=2^k
　
　

　　2、快速排序

　　快速排序是基于分治策略的一个排序算法。按照分治法的思想分析快速排序：
（1）分解(Divide) 以元素a[p]为基准元素将a[p：q-1]划分为三段a[p：q-1]，a[q]和a[q+1：r]，使得a[p：q-1]中任何一个元素都小于a[q]，a[q+1：r]中任何一个元素大于等于a[q]，下标q在划分中确定。
（2）递归求解(Conquer) 通过递归调用快速排序算法分别对a[p:q-1] 和a[q+1:r]进行排序。
（3）合并(Merge) 由于a[p:q-1] 和a[q+1:r]的排序都是在原位置进行的，所以不必进行任何合并操作就已经排好序了。

在上面三个步骤中，第一步：分解是关键。一次快速排序确定划分元素的位置，具体参见排序算法----快速排序

　　3、归并排序

　　归并排序也是基于分治策略的另一个算法。归并的思路是把两个已经排好序的数组合并为一个。(源程序)
２－路归并排序示例：

习题:对数字49 38 40 97 76 13 27进行归并排序

procedure mergesort(var r,r1:listtype;s,t:integer);

{r,r1：均为链表，存储排序数据；过程mergesort(r,r1,s,t)完成把链表r中的关键字进行归并排序、并存放到链表r1中，其中s是下界t是上界}
{过程merge(r2,s,m,t,r1)把链表r2中排好序的子链r2[s..m]和子链r2[m+1..t]合并到r1中}

　 4、[循环赛问题]（1999年广东省青少年信息学奥林匹克竞赛 第三题：棒球联赛）
问题描述：广州市体委将举行一次由N支队伍（队伍编号为1..N）参加的少年棒球联赛。联赛总共不能多于N轮（同一时间内若干支队进行一次比赛为一轮），并且每两支队之间必须而且仅必须进行一次比赛。请编程为这次比赛设计一个赛程表。
循环赛问题可以用分治法解决。下面是先假定n=2^k

procedure table(k:integer;a:array[1..u1,1..u2] of integer);
var n,i,j,m,s,t:integer;
begin
　　n:=1;
　　for i:=1 to k do n:=n*2;
　　for i:=1 to n do a[1,i]:=i;
　　m:=1;
　　for s:=1 to k do
　　　begin
　　　　n:=n / 2;
　　　　for t:=1 to n do
　　　　for i:=m+1 to 2*m do
　　　　　for j:=m+1 to 2*m do
　　　　　　begin
　　　　　　　a[i,j+(t-1)*m*2]:=a[i-m,j+(t-1)*m*2-m];
　　　　　　　a[i,j+(t-1)*m*2-m]:=a[i-m,j+(t-1)*m*2];
　　　　　　end;
　　　　　m:=m*2;
　　　end;{for s}

end;

三、练习题

[二分检索]假定在A[1..9]中顺序存放这九个数：-7,-2,0,5,16,43,57,102,291 要求检索291,16,101是否在数组中。

　　给定已排好序的n个元素A1,A2,A3,…，An, 找出元素x是否在A中，如果x在A中，指出它在A中的位置。

递归源程序

{　　二分检索的方法充分利用元素之间的次序关系，采用分治策略可以在最坏情况下用 O（log n）的时间完成任务。 }

program search;

 const

   n=10;

var a:array[1..n] of integer;

    i:integer;

    x:real;

Procedure BinarySearch(low:integer;high:integer;var i:integer);

 var mid:integer;

 begin

  if low>high then i:=0

  else

   begin

    mid:=(low+high) div 2;{将n个元素分成大致相同的两半}

    if x=a[mid] then   {取a[n  div 2]与x做比较}

       begin i:=mid; exit; end  {如果x=a[n div 2]，则找到x，算法结束。}

    else

        if x0 then  writeln(x,' is  the  ',i,'th ',' one in the table.')

  else writeln(x,' is not in the table.')

End.

program search;

 const

   n=10;

var a:array[1..n] of integer;

    i:integer;

    x:real;

非递归源程序

Procedure BinarySearch(low:integer;high:integer;var i:integer);

 var mid:integer;

 begin

    while low<=high do

      begin

          mid:=(low+high) div 2;

         if x=a[mid] then

            begin i:=mid; exit; end

         else

           if x0 then  writeln(x,' is  the  ',i,'th ',' one in the table.')

  else writeln(x,' is not in the table.')

 End.