第四章 分治法

第四章分治法

如果给你一个装有16个硬币的袋子，其中有一个是伪造的，并且那个伪造硬币的重量和真硬币的重量不同。你能不能用最少的比较次数找出这个伪造的硬币？为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。

常规的解决方法是先将这些硬币分成两个一组，每一次只称一组硬币，如果运气好的话只要称1次就可以找到，最多称8次就可以找出那枚硬币。这种直接寻找的方法存在着相当大的投机性。这种方法适用于硬币数量少的情况，在硬币数量多的情况下就成为一件费时费力又需要运气的事。

试着改变一下方法：如果我们将一组硬币分成两小组，将原来设计的一次比较两枚硬币变为一次比较两组硬币，我们会发现通过一次比较后，完全可以舍弃全部是真币的一组硬币，选取与原有问题一致的另一半进行下一步的比较，这样问题的规模就明显缩小，而且每一次比较的规模都是成倍减少。如图4_1所示：

图4_1

根据以上分析，我们可以得到以下的结论：

1、参与比较的硬币数量越多，使用该方法来实现就越快，而且投机性大大减少；

2、解决方法关键在于能将大问题分割成若干小问题；

3、小问题与原有问题是完全类似的。

通常我们将这种大化小的设计策略称之为分治法，即“分而治之”的意思。

分治法是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。侧重点在于能各个击破。分治法在设计检索、分类算法或某些速算法中很有效的。最常用的分治法是二分法、归并法、快速分类法等。

例4_1：循环比赛

[问题描述] 设有N个选手的循环比赛。其中N=2M，要求每名选手要与其他N-1名选

手都赛一次。每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。

输入：

N

输出：

表格形式的比赛安排表

[样例输入]

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

［问题分析］以N=3为例，我们可以根据问题要求制定以下一种方案，如图4_2：

图4_2

让我们以表格的中心为拆分点，将表格分成A、B、C、D四个部分，就很容易看出A=D，B=C。而且这个规律同样适用于各小部分。这样对八个队的赛事排列就逐步减化为对4个队的排列，然后又进一步地减化为2个队的排列，最后就成为1个队的排列。

在设计程序时，我们采用由小到大的方法进行扩展，而数组下标的处理是解决该问题的关键。

[过程描述]

求2M的值 N；

将数组A的第一行赋初值；

for s:=1 to k do {S表示层数}

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

End.

例4_2：残缺棋盘问题

[问题描述] 残缺棋盘是一个k2╳k2个方格的棋盘，其中恰好有一个方格残缺，现在要求用三格板覆盖棋盘，在此覆盖中两块三格板不能重叠，三格板也不能覆盖在残缺的方格上。

当k=1时各种可能的残缺棋盘如图4_3所示，其中残缺部分用阴影表示。

图4_3

三格板的四个不同方向如下图4_4所示：

图4_4

第一行输入棋盘总行数，第二行输入残缺的格子坐标。

输出：

覆盖的矩阵图

[样例输入]

4

4 1

[样例输入]

2 2

3 3

2 1 1 3

4 4 1 5

0 4 5 5

[问题分析] 很明显，当K=0时是不需要三格板的，而当K=1时只需要1块三格板就够了。那么关键在于K>1时情况就有些复杂了，以K=2时的某一种情况（如图4_5所示）为例，如果我们按一般的搜索来实现也是可行的，但在时间上会有很多浪费。不妨先归纳一下放三格板时是否有规律可循：

图4_5

如果将第一块三格板放在如图4_5所示的位置上时，让区域居中的原来无阴影的小区域都变成有一个阴影，这样四个相等小区域都缺了一角，问题一下子明朗了。

在本例中需要的数据有：

（1）用一个二维数组board [ I , j ]表示棋盘，其中I 表示棋盘的行，J表示棋盘的列；

（2）一个表示三格板数目的全局变量title ,该变量同时也用来表示每次覆盖的三格板的编号。

递归中所使用的函数为：fugai ( tr , tc , dr , dc , size)

tr 整型，表示区域左上角的行号；

tc 整型，表示区域左上角的列号；

dr 整型，表示残缺格所在的行号；

dc 整型，表示残缺格所在的列号；

size 整型，表示待放置区域的总行数或总列数。

[算法描述]

function fugai (tr,tc,dr,dc,size:integer )；

IF size=1 then 结束；

Title := title + 1 ； { 三格板数目+1 }

Size := size div 2 ； { 区域大小减半 }

IF 残缺格在上部

then if 残缺格在左部

then begin 将右下角设为阴影，填上三格板编号；

分别对四个小区域进行覆盖

End

Else begin 将左下角设为阴影，填上三格板编号；

分别对四个小区域进行覆盖

End

Else if 残缺格在左部

then begin 将右上角设为阴影，填上三格板编号；

分别对四个小区域进行覆盖

End

Else begin 将左上角设为阴影，填上三格板编号；

分别对四个小区域进行覆盖

End

例4_3:数的查找

[问题描述] 对于给定的n个元素的数组a[1 : n ]，要求从中找出第k小的元素。

输入：

第一行是总数N和K，第二行是N个待比较的元素。

输出：

第K小的数在数组中的位置。

[样例输入]

5 3

238 91 56 4

[样例输出]

1

[问题分析] 对于一组混乱无序的数来说，要找到第K小的元素通常要经过两步方可实现：

第一步：将数进行排序；

第二步：确定第K个位置上的数。

传统的排序算法（插入排序法、选择排序法等）大家已经非常熟悉了，但已学过的排序方法无论从速度上，还是从稳定性方面都不是最佳的，因此在实际运用中一般不大用。事实上用归并排序或堆排序的方法来实现排序相对而言是较快较稳的，或者通过避免排序的方法

同样也可以有效地提高查找的效率。

下面是一列由10个元素组成的数组：

[ 7 2 6 8 10 1 6 22 9 4 ]

假设要找出K=3的元素，我们不妨可以这样处理：将7作为一个参照数，将这个元素中比7小的数放在7的左边，比7大或相等的数放在7的右边，这样我们可以得到第一次数组的调整：

[ 4 2 6 6 1 ] 7 [ 10 22 9 8 ]

由此可知：比7小的数有5个，那么7应该是该数组中第6个小的元素。题目要求K=3，那么我们就应该将数的搜索范围缩小到7的左边，以4为参照数，确定4的实际位置为：

[1 2 ] 4 [ 6 6 ]

由此可知：4应该是第3个小的元素，正是题目所要找的数。

选数过程用select（ left , right, k）表示，其中left表示数列最左边第一个数的位置，right表示数列最右边第一个数的位置，k 表示要找的元素排名。

函数template实现确定数列中第一个数的位置，其参数有

right：数列的左边界；

left：数列的右边界；

返回值为：左边界数的实际位置。

算法图示如下：

原始状态：

7 2 6 8 10 1 6 22 9 4

I J

（1）比较先从右边J指针开始，第一次比较后得：

4 2 6 8 10 1 6 22 9 7

I J

（2）此时调整左边I指针的位置直到比7大的数为止，

4 2 6 8 10 1 6 22 9 7

I J

交换得：

4 2 6 7 10 1 6 22 9 8

I J

（3）再从J指针开始直到比7小的数为止，得到结果：

4 2 6 7 10 1 6 22 9 8

I J

交换后得：

4 2 6 6 10 1 7 22 9 8

I J

重复第（1）到第（3）步，得到的结果依次是：

4 2 6 6 7 1 10 22 9 8

I J

4 2 6 6 1 7 10 22 9 8

I J

[程序描述]

Procedure Select ( left , right , k：integer )；

Begin

根据left 和right的值求出数列的总个数n；

排除掉K不允许出现的情况：(k>n) or (k<1)；

temp :=template（right , left）；

{函数template是为了找出数列中left 元素的实际排名位置} if k =1 then begin 输出相应的数；返回 end ；

if k>temp then select(temp+left，right,k–temp) { 从数列的右半边找 } else select(right,temp+left–2,k)；{ 从数列的左半边找 } End；

function template ( right , left :integer )：integer；

var temp ，I ， j ：integer ；

begin

I:=right；

J:=left；

while ( j>i ) do

begin

while ( a[ I ]<= a[ j ] ) do j := j-1 ；

temp := a[ I ] ； a[ I ] := a[ j ] ； a[ j ] :=temp；

while ( a[ j ]>=a[ I ] ) do I :=I+1；

temp := a[ I ] ； a[ I ] := a[ j ] ； a[ j ] :=temp；

end；

template := j ；

end；

例4_4：归并排序

[问题描述] 对一组无序的整数用归并法进行排序。

第一行为数列的总个数，第二行为待排序的数列。

输出：

排序后的数列。

[样例输入]

8

10 4 6 3 8 2 5 7

[样例输出]

2 3 4 5 6 7 8 10

[问题分析] 归并排序实际上就是二分法在排序中的应用。它的基本思想是：将待排序的数列分成两个小的数集，先对两个子数集进行排序，然后进行两个有序子集的合并，形成排序后的数列（称为序列）。而对子集的处理方法与刚才的处理方法是一致的，直到子集集中只存在一个整数为止结束分解。（详见下图）

图4_6

算法中子集合的数目为2，其中子集A中含有n / 2个元素。

[程序分析]

Procedure sort ( e：arr； n：integer ) ；

{ 对数组E中的n 个元素进行排序 }

if (n >=2) then

begin

i = n / 2； j = n - i；

令A 包含E中的前i 个元素；

令B 包含E中余下的j 个元素；

s o r t ( A , i ) ；

s o r t ( B , j ) ；

m e rge ( A , B , E , I , j )； { 把A和B合并到E }

else 终止；

procedure merge （ a，b：arr； var e：arr；I，j：integer）；

var k，m，mb，p：integer；

begin

k：= 1；m：=1；p：=0；

if (a [k ]< b [m ]) then

begin p：=p+1；e [p] ：=a [ k ]；k：=k+1 end

else begin p：=p+1；e [p]：= b [ m ]；m：=m+1 end ；

if k >m then

for mb：= m to j do

begin p：=p+1；e [ p ]：= b [ mb ] end

else

for mb：=k to I do

begin p：=p+1；e [ p ]：= a [ mb ] end；

end；

算法思考与改进：

改进一：

为此按照下述过程来对的伪代码进行细化：当集合E被化分成两个子集合时，可以不必把两个子集合的元素分别复制到A和B中，只需简单地在集合E中保持两个子集合的左右边界即可。接下来对A 中的初始序列进行排序，并将所得到的排序序列归并到一个新数组B中，最后将它们复制到A 中。

M e rgeSort( a: arr；left, right：integr) ；

{ 对a 数组中从 l e f t到 r i g h t元素进行排序 }

Begin

if left < right then

begin { 至少两个元素 }

I: = (left + right) div 2；

M e rgeSort (a, left, i)；

M e rgeSort (a, i+1, right)；

M e rge (a, b, left, i, right)； { 从a 合并到b }

Copy (b, a, left, right)； { 结果放回a }

End；

End；

改进二：仔细查看原有的序列，我们可以发现，其实也可以不需人为地分成两个部分，只要将序列从左往右扫描一下，就可以分成若干有序序列。

例如，元素序列[ 4，8，3，7，1，5，6，2 ]中就可以分成子序列[ 4，8 ]，[ 3，7 ]，

[ 1，5，6 ]和[ 2 ]，每个子序列都是有序的。分割子序列的标准是：若位置i 的元素比位置i+ 1的元素大，则从位置i 进行分割。然后再根据归并的算法进行归并运算。这种排序法被称为自然归并排序，它是基本归并排序的一种变化。

对于上面这个元素序列，可找到四个子序列，子序列1和子序列2归并可得[ 3 , 4 , 7 , 8 ]，子序列3和子序列4归并可得[ 1 , 2 , 5 , 6 ]，最后，归并这两个子序列得到[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。因此，对于上述元素序列，仅仅使用了两趟归并就可以了。而以前的几个算法来处理这个数列则用了三趟归并作为一个极端的例子。假设输入的元素序列已经排好序并有n 个元素，自然归并排序法将准确地识别该序列不必进行归并排序。可见利用自然归并法来解决归并排序问题无疑是最佳的。

例4_5：最近点对距离问题

[问题描述] 在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。

最接近点对问题的提法是:给定平面上n 个点，找其中的一对点，使得在n 个点的所有点对中，该点对的距离最小。严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。

（预备知识：在平面几何中每一个点都用（X ，Y ）来表示它在平面中的位置，点1（11,y x ）

与点2（22,y x ）之间的距离可用公式：2

21221)()(y y x x -+- 表示）

输入：

平面中各点的坐标，以（0，0）表示输入结束。 输出：

距离最近的两点坐标。

[样例输入]

7 2 2 7 3 4 9 7 0 0

[样例输出]

the nearest lenght is: 3.16

the first point is:2 2.00 7.00 the second point is:3 3.00 4.00

[问题分析] 常规分析中，我们通常是套用公式，求出所有点对之间的距离，然后用找最小值的方法进行比较分析，从而找出距离最小的点对。这种方法称为直接分析法。

使用这种方法优点在于能找出所有的点对，比较稳定；缺点在于耗时太多，用数学方法分析一下，我们就会发现对于平面上的n个点，会产生n*(n-1)个点对，即需要求n*(n-1)次距离，就时间复杂性而言应为O(n2)。对于N的值很小的时候可以这样做，但随着N值增大，计算机所花的计算时间将成倍地增加，很显然这种算法是不可取的。

不妨试着将大问题规模缩小，将一个大问题缩小为两个小问题，其中一个问题（称为问题A）大小为n/2 ，另一个问题（称为问题B）大小也为n/2。这样出现最近点对的情况有可能是以下三种：

情况1：两个点都出现在A中；

情况2：两个点都出现在B中；

情况3：一个点在A中，一个点在B中。

分别找出这三种情况下的距离最近的点对，而最近的点对必定是这三种情况下距离值最小的。

对于情况1和情况2都可以递归地实现找距离最近的点对，对于情况3则需用另外的方法进行判断。这种方法取决于如何对A和B进行划分，一种合理的方法是在根据X坐标的中间值处做一条垂线，垂线的左边归点集A，垂线的右边归点集B，在垂线线上点可以A、B之间分配以便满足A，B的大小。

因为对于A中的任意一个点P，B中仍需要n/2个点与之构成候选点，这样的思路势必会导致耗时仍为O（n2），因此我们应该把注意力转移到情况3上去。

为了使问题易于理解和分析，我们先来考虑一维的情形。如下图4_7所示，x轴上的n 个实数x1,x2,..,xn。那么找最接近点对就是为这n个实数中相差最小的2个实数。

我们显然可以先将x1,x2,..,xn排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，虽然这种方法无法适应二维的情形，但是如果我们对这种一维的简单情形试用分治法来求解，那么就有可能推广到二维的情形。

图4_7

根据某一种方法，我们找出了划分两个子集的分割点m，假设已经找到A集中的最小点对距离为S1，B集中的最小点对距离为S2，又设在两种情况下的最小点对距离为g，显然，g = ＭＩＮ（Ｓ１，Ｓ２）。而第三种情况（即跨越两个子集）只需找出S1中坐标的最大值点p3和S2中坐标的最小值点q3，然后求出p3和q3之间的距离，可以得出g最终应是S1，S2，q3-p3的最小值。通过分治算法，我们可以把时间复杂度降低到O（n）。

问题的关键转化为如何确定分割点m及A和B两个数集的划分。明显地，如果通过m点，将两个数集的规模划分相等无疑是最佳的。

涉及的数据为 x : array [1.. 50 ] of real；{ 存放点的坐标 }

[程序分析]

function CPAIRI(S) : real；

begin

if S中有2个点 then g:=abs(x[2]-x[1])

else if (S中有1个点)

then g:=maxint

else begin

m:=S中各点的坐标值的中位数；

构造A和B,使A中的坐标值都小于m,B中的坐标值都大

于m；

g1:=CPAIRI(A)；

g2:=CPAIRI(B)；

p:=max(A)；

q:=min(B)；

g:=min(g1,g2,q-p)；

end；

CPAIRI : =g；

end；

虽然这个算法看上去比用排序加扫描的算法复杂，但足可以向二维推广。

下面我们来考虑二维的情形。此时S中的点为平面上的点，它们都有2个坐标值x和y。为了将平面上点集S线性分割为大小大致相等的2个子集A和B，我们选取一垂直线x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为A 和B，其中A中所有点的X坐标都小于Xm，B中所有点的X坐标都大于Xm。从而使S1和S2分别位于直线l的左侧和右侧。由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等。分别在A集中最近的两点，B集中最近的两点和A集与B集中各取一点构成最近的一对点对进行比较，取最小值。当某集合中点的个数小于4时就可以不再分解，用直接分析法进行处理。

对于有些与垂线重合的点，我们可以先将它们归入B集，然后将这些点按纵坐标按照由高到低的顺序重新安排，按同样的拆分法进行拆分即可以找出最小值。

数据说明如下：

point = array [1..200] of record

ban:byte {0表示按原始状态存放，

1表示X与Y坐标进行了对调}

num:integer； {点的编号}

xpos:real； {点的X坐标}

ypos:real； {点的Y坐标}

end；

pointarr=array [1..10] of point；存放点的数组类型名

twopoint=array [1..2] of point；存放结果的类型名

[程序分析]

procedure close(n:integer；a:pointarr；var answer : twopoint)；

{n表示数组A的元素总个数，answer表示最后结果的两个点}

{该过程用于找出数组A中最近的两个点的有关信息}

var ap,bp:pointarr；

i,j,acount,bcount,enda:integer；

xm,mina,minb,minc,min,longab,temppos:real；

temp:point；

tempabc,tempc:twopoint；

begin

if n=0 then exit；

if n<=4 then 用直接分析法

else

begin

xm:=(a[1].xpos+a[n].xpos)/2； {求X轴的中间值}

{将数组分成两部分ap和bp}

i:=1；acount:=1；

while a[i].xpos

begin

temp:=a[i]；ap[acount]:=temp；inc(acount)；inc(i)

end；

dec(acount)；bcount:=1；

while (a[i].xpos>=xm)and(i<=n) do

begin

temp:=a[i]；bp[bcount]:=temp；inc(bcount)；inc(i)

end；

dec(bcount)；

mina:=100；

if acount>0 then

begin close(acount,ap,tempa)；mina:=long(tempa[1],tempa[2])； close(bcount,bp,tempb)；minb:=long(tempb[1],tempb[2]) end else

{数组AP中无数，表示以下点均具有同一个横坐标的值，

此时应根据这些点的纵坐标的值进行排序，再找最近的两个点}

begin

minb:=100；

for i:=1 to bcount do bp[i].ban:=1；

{用1作标志表示将这些点的纵横坐标值对调}

change(bp,bcount)；

sort(bp,bcount)；

close(bcount,bp,tempb)；minb:=long(tempb[1],tempb[2])

end；

找一点在AP，另一点在BP的最小值，并将结果存于tempc中；

找出最小值并将最小值存入answer中

end；

end；

其它过程说明：

function long(x1,x2:point):real；计算两点之间的距离；

procedure input(var a:pointarr；var count:byte)；输入原始的点坐标；

procedure change(var a:pointarr；count:byte)；将数组A中每个点的横坐标与纵坐标对调；

procedure sort(var a:pointarr；count:byte)；将数组A按XPOS的值进行排序；

例4_6：剔除多余括号

[问题描述] 输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价。

注意：输入a+b时不能输出b+a。

表达式以字符串输入，长度不超过２５５。输入不要判错。

所有变量为单个小写字母。只是要求去掉所有多余括号，不要求对表达式化简。

输入：

原表达式

输出：

经过处理的表达式

[样例输入]

(a*b)+c/d a*b+c/d

[样例输出]

a*b+c/d a*b +c/d

[算法分析] 四则运算表达式含运算符 +, - ,* , / , ( , ) ，其优先顺序由低至高为：+ , - ─→ * , / ─→ ( , )

一个括号是否作为多余的括号剔除，关键是分析该括号内优先级最低的运算符与左邻括号或右邻括号的运算符之间的运算优先关系：

设待整理的表达式为(s1 op s2)

其中op表示括号内优先级最低的运算符( + , - 或 * , / )；

１、若左邻括号的运算符为 / ，则无论op为何运算符，括号必须保留，即…… /( s1 op s2)……。因为原式(s1 op s2)作为除数，一旦去除括号后，仅s1作为除数，不可能与原式等价；

２、若左邻括号的运算符为 * 或 - ，而op为 +或 -，则保留括号，即……*-(s1+-s2)。不能去除括号的原因是：

若左邻标符为*，优先级大于括号内运算符，因此必须用括号保证括号内的+或-优先进行；

若左邻算符为-，去除括号后，由于括号内的+、-要变号，结果不与原式等价；

３、若右邻括号的运算符为*或/ ，而op为+或-，原式中的op运算必须优先进行，因此括号不能去除，即(s1+-s2)*/……；

４、除上述情况外，括号去除，结果与原式等价，即…s1 op s2…。

在设计算法时，可以在优先级最低的运算符处将原表达式拆分为两个子表达式，然后对每个子表达式的分析方法我们采用相似的方法对表达式进行拆分，同时对相应层进行括号整理，直至最外层的括号保留或去除为止。

例如，剔除表达式‘（（a+b）*f）-（i/j）’中多余的括号。依据上述算法进行整理的过程如下：

图4_8

最后，自底向上得整理结果：(a+b)*f-i/j。这个整理过程可以用函数reduce来描述。

数据描述如下：

s:string； {表达式字符串}

a,b:string；{拆分后形成的两个子串}

[程序分析]

function reduce （s:string）:string；{ 整理表达式s,并返回整理结果 }

begin

if s中只有一个元素 then reduce :=s；

else { s是's1 op s2' 形式 }

begin

找优先级最小的运算符op所在的位置c1；{用函数find实现}

s1为OP的左半部分表达式；

S2为OP的右半部分表达式；

If （s1是用’(’和’)’包围的）and（该括号是一对） then

{用函数pairyes实现}

Begin

Temp=去掉外围括号后的表达式；

找temp中优先级最小的运算符OP1；

IF OP1>OP then S1:=reduce(temp)

Else s1:=’(‘+reduce (temp)+’)’

End

Else s1:=reduce(s1)；

同理对S2字符串进行处理；

reduce:=s1+op+s2；

end；

end；

函数pairyes主要用来判断两点：

1、字符串s的第一个字符‘（‘与最后一个字符‘）’是否是一对；

2、表达式是否合理；

procedure pairyes(s:string；var firsttoend,duoyu:boolean)；

var i,code:integer；

yes:boolean；

begin

i:=1；code:=0；

if (s[i]='(')and(s[length(s)]=')') then

begin

code:=0；

repeat

if s[i]='(' then inc(code)；

if s[i]=')' then dec(code)；

inc(i)

until (code=0)or(i>length(s))；

if (i>length(s))and(code=0) then firsttoend:=true else firsttoend:=false；

if code<>0 then duoyu:=true else duoyu:=false

end

else

begin

firsttoend:=false；

code:=0；

repeat

if s[i]='(' then inc(code)；

if s[i]=')' then dec(code)；

inc(i)

until (code=0)or(i>length(s))；

if code<>0 then duoyu:=true else duoyu:=false

end

end；

函数find用来找出表达式字符串中具有最小优先级的运算符：

function find(s:string):byte；

程序略；

函数list用以判断A和B两个运算符的优先级：

function list(a,b:char):char；

程序略；

分治法是程序设计中常见的解决方法，其特点主要有以下两个：

（1）对大问题的解决可以分解成对若干小问题的解决；

（2）每个小问题出现的情况又与大问题出现的情况是一致的。

在算法实现中，我们通常采用递归来实现。当然有的问题在分析时用的是递归的思路，在具体实现时只用递推的方法，这样做的目的是简化运行步骤，提高运行效率。

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

（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；

（3）合并：将各个子问题的解合并为原问题的解。