分治法---基础算法

有许多算法在结构上是递归的：为了解决一个给定问题， 算法要一次或多次地调用其自身来解决相关的子问题。这些算法通常采用分治策略:将原问题分成n 个规模较小而结构与原问题相似的子问题。递归地解这些子问题，然后合并其结果就得到原问题的解。 n＝2时的分治法又称二分法。

用分治法求解一个问题，所需的时间是由子问题的个数， 大小以及把这个问题分解为子问题所需的工作总量来确定。一般来说，二分法(即把任意大小的问题尽可能地等分两个子问题)较为有效。

分治法在每一层递归上都有三个步骤:

分解:将原问题分解成一系列子问题;

解决:递归地解各子问题。若子问题足够小，则直接解;

合并:将子问题的结果合并成原问题的解;

【例1】合并排序

对序列A〔1〕，A〔2〕，……，A〔n〕进行合并排序。

算法分析:

合并排序的算法就是二分法

分解:将n个元素各含n/2个元素的子序列;

解决:用合并排序法对两个子序列递归地排序;

合并:合并两个已排序的子序列以得到排序结果;

在对子序列排序时，当其长度为1时递归结束。单个元素被视为是已排好序的。合并排序的关键步骤在于合并步骤中产生的两个已排好序的子序列

A〔P..Q〕和A〔Q+1..R〕

将它们合并成一个已排好序的子序列〔P..R〕。我们引入一个辅助过程merge(A,P,Q,R)来完成这一合并工作，其中A是数组，P，Q ，R是下标。这个过程如果用玩扑克来比喻，就可以看作桌上有两堆牌，每一堆都是排好序的，最小的牌在最上面， 我们希望把这两堆牌合并成排好序的一堆加以输出。基本步骤包括:先取面朝上的两堆牌的顶上两张中较小的一张，将它取出面朝下地放到输出堆中。重复这个步骤直到某一输入堆为空。 这时把另一个输入堆中余下的牌面朝下放入即可。

Procedure Merge(Var A: ListType; p, q, r : Integer);
          {将两个已排好序的子序列A[p..q]和A[q+1..r]合并成一个已排好序的序列A[p..r]}
          Var
            i, j, t : Integer;{左子序列指针;右子序列指针;合并后的序列的指针}
            Lt      : ListType;{暂存合并的序列}
          Begin
            t := p; i := p; j := q + 1;
            While t <= r Do Begin{若合并未完成,则循环}
              If (i <= q) And ((j > r) Or (A[i] <= A[j]))  Then Begin
             {若左序列剩有元素并且右序列元素全部合并或者左序列的首元素小于等于右序列的首元素,
              则左序列的首元素进入合并序列,左序列的首指针+1}
                Lt[t] := A[i]; Inc(i)
              End{then}
              Else Begin{否则左序列的首元素进入合并序列,右序列的首指针+1}
                Lt[t] := A[j]; Inc(j)
              End;{else}
              Inc(t){合并序列的指针+1}
            End;{while}
            For i := p to r Do A[i] := Lt[i]{合并后的序列赋给A}
          End;{Merge)

现在就可以把merge过程作为合并排序的一个子过程来用了。下面是merge_sort(A,P,R)对数组A〔P..R〕进行排序。若P ≥R，该子数组至多只有一个元素， 当然就是已排序的。否则，分解步骤就计算出一个中间下标Q，而将A〔P..R〕分成A〔P..Q〕和A〔Q+1..R 〕。若数组A〔P..R〕的元素个数K＝R－P+1为偶数，则两个数组各含K/2个元素;否则A〔P..Q〕含[k/2]+1( k/2 )元素、A〔Q+1，R〕含[k/2]( k /2 )个元素。

Procedure Merge_Sort(Var A : ListType; p, r : Integer);
          Var
            q : Integer;
          Begin
            If p <> r Then Begin{若子序列A中不止一个元素}
              q := (p + r - 1) div 2;{计算中间下标q}
              Merge_Sort(A, p, q);{继续对左子序列A[p..q]递归排序}
              Merge_Sort(A, q + 1, r);{继续对右子序列A[q+1..r]递归排序}
              Merge(A, p, q ,r){对左子序列和右子序列合并排序}
            End{then}
          End;{Merge_sort}

我们只要调用merge_sort(A，1，N)便可对整个序列A〔1〕……A〔n〕进行合并排序。如果我们自底向上(此处“底”为n是2的幂时)来看这个过程的操作时，算法将两个长度为1的序列合并成排好序的长度为2的序列，继而合并成长度为4的序列……，依次类推。 随着算法自底向上执行，被合并的排序序列长度逐渐增加，一直进行到将两个长度为n／2 的序列合并成最终排好序的长度为n的序列。下图列出了对序列(5，2，4，6，1，3，2，6)进行合并排序的过程。

( 图1.4-1 )

当然，排序算法很多，但合并排序法也有其本身的特点──当输入的规模足够大时，合并排序的运行时间要比最坏情况下的插入排序好。分治算法不仅可应用于排序，而且还可应用于许多重要的场合，甚至有些问题看起来非得采用分治法求解不可。

【例2】导线和开关

如(图1.4-2)所示，具有3根导线的电缆把A区和B区连接起来。在A区3根导线标以1，2，3;在B区导线1和3被连到开关3，导线2连到开关1。

一般说来，电缆含m(1≤m≤90)根导线，在A区标以1，2，...m。在B区有m个开关， 标为1，2，...m。每一根导线都被严格地连到这些开关中的某一个上;每一个开关上可以连有0根或多根导线。

( 图1.4-2 )

测量

你的程序应作某些测量来确定，导线和开关怎样连。 每个开关或处于接通或处于断开状态，开关的初始状态为断开。我们可用一个探头(probe)P在A区进行测试: 如果探头点到某根导线上，当且仅当该导线连到处接通状态的开关时，灯L才会点亮。

你的程序从标准输入(standard input)读入一行以得到数字m; 然后可以通过向标准输出(standard output)写入一行以发出命令(共3种命令)。每种命令的开头是一个大写字母:

○测试导线命令T:T后面跟一个导线标号;

○改变开关状态命令C:C后面跟一个开关标号;

○完成命令D:D后面跟的是一个表列(LIST)，该表列中的第ｉ个元素代表与导线ｉ相 连的开关号。

在命令T和C之后，你的程序应从标准输入(standard input)读入一行。 若开关状态能使灯亮，则命令T的回答应是Y;反之，回答应是N。命令C的作用是改变开关的状态( 若原来是接通则变为断开;若原来是断开则变为接通)。对C命令的回答是作为一种反馈信号。

你的程序可以给出一系列命令，将T命令与C命令以任意顺序混合使用。最后给出命令D，并结束。你的程序给出的命令总数应不大于900。

注意

为了在此任务中能正确使用标准输入(standard input)和标准输出(standard output)。若你使用pascal，请不要使用其中的CRT单元(unit CRT)。

举例

(图1.4-3)给出了一个实例，对应于(图1.4-2)，这是一个有8条命令的对话。

┌──────────┐ ┌─────────┐
│  Standard Output   │ │  Standard Input  │
├──────────┤ ├─────────┤
│                    │ │  3               │
│  C 3               │ │  Y               │
│  T 1               │ │  Y               │
│  T 2               │ │  N               │
│  T 3               │ │  Y               │
│  C 3               │ │  N               │
│  C 2               │ │  Y               │
│  T 2               │ │  N               │
│  D 3 1 3           │ │                  │
└──────────┘ └─────────┘

算法分析:

这是一道通过人机对话解答的程序题。程序执行时，由计算机发出T或C命令。 用户通过键盘输入应答信号。人与计算机间几次交互信息后，最终由计算机给出命令D并显示导线和开关怎样连接的。对于编程序者来说，要解决的问题是如何设计命令顺序， 使得用户在依次应答后，程序能自动给出问题的解。

1.T命令和C命令的作用

初始时，B区M个开关断开。此时无论用探头P在A区测哪根导线，灯L也不会亮。因此，程序首先必须使用C命令和用户应答将B区的部分开关闭合。然后发出测试某些导线的T命令，通过用户应答确定这些导线在B区的准确位置或范围。若尚有导线未连接，则再通过C 命令和用户应答来改变某些开关的状态，随后发出T命令……，C命令和T命令交替使用，直到完成导线和开关的连接 。例如 M＝3。初始时

( 图1.4-4 )

对话序号         计算机命令    用户应答      结果
                 1               C3            Y          开关3闭合
                 2               T1            Y          L灯亮，导线1与开关3连接
                 3               T2            N          导线2不与开关3连接
                 4               T3            Y          导线3与开关3连接

( 图1.4-5 )

对话序号         计算机命令      用户应答    结果     
                5                C3              N        开关3断开
                6                C2              Y        开关2闭合
                7                T2              N        导线1与开关3连结

( 图1.4-6 )

由此可见,改变开关状态的C命令在人机对话中最先使用,然后发出T命令测试部分导线。若不能确定每根导线的连接位置，则还得对一些开关使用C命令，改变其开关状态，直到最后一个T命令完成导线与开关的连接为止。注意，用户对C 命令的回答仅是作为开关状态改变的一种反馈信号。即无论用户怎样应答， 开关状态总是由应答前的断开变为应答后的闭合，或者由应答前的闭合变为应答后的断开。

继C命令后使用T命令测试导线。测试导线i的过程中

若仅一个开关闭合且灯亮(即Ti的应答为Y)，则被测导线i与闭合的开关连接;

若仅一个开关断开且灯暗(即Ti的应答为N)，则被测导线i与断开的开关连接;

若多个开关闭合时灯亮(Ti的应答为Y)或者多个开关断开时灯暗(Ti的应答为N)) ，而先前的测试已确定导线i只能与这些开关中的某一个相连，则导线与之相连。

例如:第7次对话，用户应答T2的命令为N，而此时开关1、3断开，看来导线2 即可能与开关1相连，也可能与开关3相连。但是先前第3次对话，用户应答T2命令为N，确认导线2不与开关3连接。无庸置疑，导线2的连接对象仅一个─开关1。

2.用二分法连接

为了使导线和开关间的连接工作有规律地进行，我们不妨采用二分法。

设当前待连接的开关为HEAD.. TAIL，初始时为1..M。将这些开关一分为二:

左区间HEAD..[(HEAD+TAIL－1)/2];

右区间[(HEAD+TAIL－1)/2]+1..TAIL;

连接到左区间开关的导线集合为P1。初始时P1＝〔1..M〕;

连接到右区间开关的导线集合为P2。显然初始时P2＝〔 〕;

左区间或右区间开关状态是同一的，设为STATE。

┌1      区间的所有开关闭合;
                                │
                         STATE＝│
                                │
                                └0      区间所有开关断开;
                         显然初始时STATE＝0;

首先，P2集合设空并发出C命令，将左区间的所有开关取反。然后对P1集合中的每根导线发出T命令。若用户应答N(灯暗)而左区间开关闭合，或者用户应答Y(灯亮)而左区间开关断开，则说明相连的导线不在P1中，应从P1集合移入P2集合。

接下去，设左区间开关为待接开关，与之相连的导线集合为P1，开关状态已由先前的C命令取反。继续上述过程，直至出现下述两种情况之一为止:

①P1的集合为空;

②区间内的开关仅剩一个，将P1集合中所有导线连接到这个开关;最后再将右区间开关设为待连接开关，与之相连的导线集合为P2，开关状态不变。仍按上述方法进行连接。

显然，可以用一个二分法的递归过程来描述导线与开关间的连接:

procedure check(P1，开关区间，state);
            begin  
              if P1 <>〔〕then
              if  区间内剩一个开关
              then P1集合中的所有导线与之相连
              else  begin 
                通过C命令和用户应答将左区间取反;
                P2集合设空;
                对P1集合中的每根导线发出T命令:
                if((用户应答N)and(state=0))or((用户应答Y)and(state=1))   
                  then   导线从P1集合移出，移入P2集合;
                check(P1，左区间，1－state);
                check(P2，右区间，state);
              end;    {else}
            end;     {check}