第4章1 迭代蛮力分治

第四章基本的算法策略4.1迭代算法4.2蛮力算法4.3分而治之算法4.4贪婪算法4.5动态规划4.6算法策略间的比较14.1迭代算法4.1.1递推法4.1.2倒推法4.1.3迭代法解方程24.1.1递推法

【例1】兔子繁殖问题问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。3问题分析：因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对数由前两个月的小兔子的对数决定。则繁殖过程如下：一月二月三月四月五月六月……111+1=22+1=33+2=55+3=8……数学建模：y1=y2=1yn=yn-1+yn-2n=3，4，5，…4算法1：main(){inti,a=1,b=1;print(a,b);for(i=1;i＜=10;i++){c=a+b;print(c);a=b;b=c；}}5算法2：递推迭代表达式123456789abc=a+ba=b+cb=a+cc=a+ba=b+cb=a+c……由此归纳出可以用c=a+b;a=b+c;b=c+a;做循环不变式。算法2如下：main(){inti,a=1,b=1;print(a,b);for(i=1;i＜=4;i++){c=a+b;a=b+c;b=c+a;print(a,b,c);}}算法2，最后输出的并不是12项，而是2+3*4共14项。

6递推迭代表达式12

3456789aba=a+bb=a+ba=a+bb=a+b……

由此归纳出可以用a=a+b;b=a+b;做循环不变式，从而得到以下算法3:main(){inti,a=1,b=1;print(a,b);for(i=1;i＜=5;i++){a=a+b;b=a+b;print(a,b);}}算法3：7【例2】求两个整数的最大公约数。数学建模：辗转相除法是根据递推策略设计的。不妨设两个整数a>b且a除以b商x余c；则a-bx=c，不难看出a、b的最大公约数也是c的约数(一个数能整除等式左边就一定能整除等式的右边)，则a、b的最大公约数与b、c的最大公约数相同。

同样方法推出b、c的最大公约数与…,直到余数为0时，除数即为所求的最大公约数。8算法如下：main(){inta,b;input(a,b);c=amodb;while(c<>0){a=b;b=c;c=amodb;}print(b);}94.1.2倒推法

所谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从后向前推解问题的方法。10【例1】猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第10天时就只有一个桃子了，求原有多少个桃？11数学模型：每天的桃子数为：a10=1,a9=(1+a10)*2,a8=(1+a9)*2,……a10=1

递推公式为：ai=(1+ai+1)*2i=9,8,7,6……1算法如下：main(){inti,a;a=1;for(i=9;i>=1;i=i-1)a=(a+1)*2print(a)；}12【例2】输出如图所示的杨辉三角形，限定用一个一维数组完成。111121133114641

……………

13数学模型：上下层规律较明显，中间的数等于上行左上、右上两数之和。111121133114641

……………

14算法如下：main(){intn,i,j,a[100];input(n);print("1");print("换行符");a[1]=a[2]=1;print(a[1],a[2]);print("换行符");for(i=3;i<=n;i=i+1){a[1]=a[i]=1;for(j=i-1，j>1，j=j-1)a[j]=a[j]+a[j-1];for(j=1;j<=i;j=j+1)print(a[j]);print("换行符");}}为了算法简便输出如下：11112113311

4641……………因为是一维数组，只能倒推计算15【例3】穿越沙漠问题用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑，耗油率为1加仑/公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。

16贮油点问题要求要以最少的耗油量穿越沙漠，即到达终点时，沙漠中的各临时油库和车的装油量均为0。这样只能从终点开始向前倒着推解贮油点和贮油量。17数学模型：根据耗油量最少目标的分析，下面从后向前分段讨论。第一段长度为500公里且第一个加油点贮油为500加仑。第二段中为了贮备油，吉普车在这段的行程必须有往返。下面讨论怎样走效率高：1)首先这段路应走奇数次，保证最后向前走。2)每次向前行进时吉普车是满载。3)要能贮存够下一加油点的贮油量，路上耗油又最少。……18下图是满足以上条件的最佳方案，此段共走3次：第一、二次来回耗油2/3贮油1/3，第三次耗油1/3贮油2/3，所以第二个加油点贮油为1000加仑。由于每公里耗油率为1加仑，则此段长度为500/3公里。第三段与第二段思路相同。此段共走5次：第一、二次来回耗油2/5贮油3/5，第三、四次来回耗油2/5贮油3/5，第五次耗油1/5贮油4/5，第三个加油点贮油为1500加仑。此段长度为500/5。……

500/5公里<——500/3公里——><——<——500公里——>——>终点<——贮油点(500)<——贮油点(1000)<——贮油点(1500)……12319综上分析从终点开始分别间隔500，500/3，500/5，500/7，…设立贮油点，直到总距离超过1000公里。每个贮油点的油量为500，1000，1500，2000…。算法设计：

由模型知道此问题并不必用倒推算法解决(只是分析过程用的是倒推法)，只需通过累加算法就能解决。

20变量说明：dis表示距终点的距离，1000-dis则表示距起点的距离，k表示贮油点从后到前的序号。main(){intdis，k，oil,k;dis=500;k=1;oil=500;do{print(“贮油点”,k,“距离”,1000-dis,“贮油量",oil)；k=k+1;dis=dis+500/(2*k-1);oil=500*k;}while(dis<1000)

oil=500*(k-1)+(1000-dis)*(2*k-1);

print("贮油点",k,"距离",0,"贮油量",oil)；}214.1.3迭代法解方程22【例1】牛顿迭代法牛顿迭代法又称为切线法，它比一般的迭代法有更高的收敛速度。首先,选择一个接近函数f(x)零点的x0,计算相应的f(x0)和切线斜率f'(x0)(这里f'表示函数f的导数)。然后计算穿过点(x0,f(x0))且斜率为f'(x0)的直线方程为：直线和x轴的交点,也就是求如下方程的解：

将新求得交点的x坐标命名为x1。通常x1会比x0更接近方程的解。接下来用x1开始下一轮迭代.

牛顿迭代法示意图23迭代公式可化简为：此公式就是有名的牛顿迭代公式。已经证明,如果f'是连续的,并且待求的零点x是孤立的,那么在零点x周围存在一个区域,只要初始值x0位于这个邻近区域内,那么牛顿法必定收敛。

下面给出用牛顿迭代法，求形如ax^3+bx^2+cx+d=0方程根的算法，系数a、b、c、d的值依次为1、2、3、4，由主函数输入。求x在1附近的一个实根。求出根后由主函数输出。24main(){floata,b,c,d,fx;print("输入系数a,b,c,d:");input(a,b,c,d);fx=f(a,b,c,d);printf("方程的根为：",fx);}

floatf(a,b,c,d)floata,b,c,d;{floatx1=1,x0,f0,f1;do{x0=x1;f0=((a*x0+b)*x0+c)*x0+d;f1=(3*a*x0+2*b)*x0+c;x1=x0-f0/f1;}while(fabs(x1-x0)>=1e-4);return(x1);}25二分法求解方程示意【例3】二分法求解方程f(x)=0根

用二分法求解方程f(x)=0根的前提条件是：f(x)在求解的区间[a,b]上是连续的，且已知f(a)与f(b)异号，即f(a)*f(b)<026令[a0,b0]=[a,b]，c0=(a0+b0)/2，若f(c0)=0，则c0为方程f(x)=0的根；否则，若f(a0)与f(c0)异号，即f(a0)*f(c0)<0，则令[a1,b1]=[a0,c0]；若f(b0)与f(c0)异号，即f(b0)*f(c0)<0，则令[a1,b1]=[c0,b0]。依此做下去，当发现f(cn)=0时，或区间[an,bn]足够小，比如|an-bn|<0.0001时，就认为找到了方程的根。

用二分法求一元非线性方程f(x)=x^3/2+2x^2-8=0(其中^表示幂运算)在区间[0，2]上的近似实根r，精确到0.0001.算法如下：

二分法求解方程示意27main(){floatx,x1=0,x2=2,f1,f2,f;f1=x1*x1*x1/2+2*x1*x1-8;f2=x2*x2*x2/2+2*x2*x2-8;if(f1*f2>0){printf("Noroot");return;}do{x=(x1+x2)/2;f=x*x*x/2+2*x*x-8;if(f=0)break;if(f1*f>0.0){x1=x;f1=f;}elsex2=x;}while(fabs(f)>=1e-4);print("root=",x);}二分法求解方程示意284.2蛮力法

蛮力法是基于计算机运算速度快这一特性，在解决问题时采取的一种“懒惰”的策略。这种策略不经过(或者说是经过很少的)思考，把问题的所有情况或所有过程交给计算机去一一尝试，从中找出问题的解。蛮力策略的应用很广，具体表现形式各异，数据结构课程中学习的：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等，都是蛮力策略具体应用。比较常用还有枚举法、盲目搜索算法等，本节介绍枚举法和其它一些小的范例，第五章介绍盲目搜索算法。

294.2.1枚举法

枚举(enumerate)法(穷举法)是蛮力策略的一种表现形式，也是一种使用非常普遍的思维方法。它是根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。用枚举法解决问题，通常可以从两个方面进行算法设计：1)找出枚举范围：分析问题所涉及的各种情况。2)找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。30【例1】百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了著名的"百钱百鸡问题"：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?

31算法设计1：通过对问题的理解，读者可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用"懒惰"的枚举策略进行算法设计：

设x，y，z分别为公鸡、母鸡、小鸡的数量。尝试范围：由题意给定共100钱要买百鸡，若全买公鸡最多买100/5=20只，显然x的取值范围1~20之间；同理，y的取值范围在1~33之间，z的取值范围在1~100之间。约束条件：x+y+z=100且5*x+3*y+z/3=100

32算法1如下：

main()

{intx,y,z;

for(x=1;x<=20;x=x+1)

for(y=1;y<=34;y=y+1)

for(z=1;z<=100;z=z+1)

if(100=x+y+zand100=5*x+3*y+z/3)

{print(thecocknumberis",x)；print(thehennumberis",y)；print(thechicknumberis"z);}

}33算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低算法设计2：在公鸡(x)、母鸡(y)的数量确定后，小鸡

的数量

z就固定为100-x-y，无需再进行枚举了此时约束条件只有一个：

5*x+3*y+z/3=100

34main()

{

intx,y,z;

for(x=1;x<=20;x=x+1)

for(y=1;y<=33;y=y+1)

{

z=100-x-y;

if(zmod3=0and5*x+3*y+z/3=100)

{print(thecocknumberis",x)；print(thehennumberis",y)；print(thechicknumberis"z);}

}

}算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断"5*x+3*y+z/3=100"。这样省去了z不整除3时的算术计算和条件判断，进一步提高了算法的效率。35【例2】解数字迷：ABCAB

×ADDDDDD算法设计1：按乘法枚举1)枚举范围为：A：3——9(A=1，2时积不会得到六位数),B：0——9,C：0——9五位数表示为A*10000+B*1000+C*100+A*10+B共尝试700次。362)约束条件为：每次尝试，先求五位数与A的积，再测试积的各位是否相同，若相同则找到了问题的解。测试积的各位是否相同比较简单的方法是，从低位开始，每次都取数据的个位，然后整除10，使高位的数字不断变成个位，并逐一比较。

37算法1如下：main(){intA,B,C,D,E,E1,F,G1,G2,i;for(A=3;A<=9;A++)for(B=0;B<=9;B++)for(C=0;C<=9;C++){F=A*10000+B*1000+C*100+A*10+B;E=F*A；E1=E;G1=E1mod10;for(i=1;i<=5;i++){G2=G1;E1=E1\10;G1=E1mod10;if(G1<>G2)break;}if(i=6)print(F，"*"，A，"="，E);}}38算法分析1：以上算法的尝试范围是A：3-9，B：0-9，C：0-9。共尝试700次，每次，不是一个好的算法。算法设计2：将算式变形为除法：DDDDDD/A=ABCAB。此时只需枚举A：3-9D：1-9，共尝试7*9=63次。每次尝试测试商的万位、十位与除数是否相同，千位与个位是否相同，都相同时为解。39main(){intA,B,C,D,E,F;for(D=1;D<=9;D++){E=D*100000+D*10000+D*1000+D*100+D*10+D;for(A=3;A<=9;A++){if(EmodA=0){F=E\A;if(F\10000=Aand(Fmod100)\10=A)

if(F\1000mod10=Fmod10)print(F，"*"，A，"="，E);}}}}40【例3】狱吏问题某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁,每转动一次,原来锁着的被打开,原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1间转动一次；问通过n次后，那些牢房的锁仍然是打开的？41算法设计1：1)用一维数组a[n],每个元素记录一个锁的状态，1为被锁上，0为被打开。2)对i号锁的一次开关锁可转化为运算：a[i]=1-a[i]。3)第一次转动的是1，2，3，……，n号牢房；第二次转动的是2，4，6，……号牢房；第三次转动的是3，6，9，……号牢房；……4)用蛮力法通过循环模拟狱吏的开关锁过程，最后当第i号牢房对应的数组元素a[i]为0时，该牢房的囚犯得到大赦。42main(){inta[100],i,j,n;input(n);for(i=1;i<=n;i++)a[i]=1;for(i=1;i<=n;i++)for(j=i;j<=n;j=j+i)a[i]=1-a[i];for(i=1;i<=n;i++)if(a[i]=0)print(i,"isfree.");}算法分析：算法的时间复杂度为n*(1+1/2+1/3+……+1/n)=O(nlogn)。43问题分析：转动门锁的规则可以有另一种理解，第一次转动的是编号为1的倍数的牢房；第二次转动的是编号为2的倍数的牢房；第三次转动的是编号为3的倍数的牢房；……则狱吏问题是一个关于因子个数的问题。令d(n)为自然数n的因子个数，这里不计重复的因子，如4的因子为1，2，4共三个因子，而非1，2，2，4。则d(n)有的为奇数，有的为偶数，见下表:编号与因数个数的关系n12345678910111213141516……d(n)1223242434262445……

数学模型2：上表中的d(n)有的为奇数，有的为偶数，由于牢房的门开始是关着的，这样编号为i的牢房，所含因子个数为奇数时，牢房最后是打开的，反之，牢房最后是关闭的。44算法设计2:main(){ints,i,j,n;input(n);for(i=1;i<=n;i++){s=1;for(j=2;j<=i;j=j++)if(imodj=0)s=s+1;if(smod2=1)print(i,"isfree.");}}45算法分析：算法1的时间近似为复杂度为O(nlogn)。使用了n个空间的一维数组。算法2没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其主要操作是判断imodj是否为0，共执行了n*(1+2+3+……+n)次，时间复杂度为O(n2)。

46数学模型3：仔细观察下表，发现当且仅当n为完全平方数时,d(n)为奇数；这是因为n的因子是成对出现的,也即当n=a*b且a≠b时，必有两个因子a，b;只有n为完全平方数，也即当n=a2时,才会出现d(n)为奇数的情形。算法设计3：这时只需要找出小于n的平方数即可。47main(){ints,i,j,n;input(n);for(i=1;i<=n;i++)if(i*i<=n)print(i*i,"isfree.");elsebreak;}

在对运行效率要求较高的大规模的数据处理问题时，必须多动脑筋找出效率较高的数学模型及其对应的算法。484.3分而治之算法4.3.1分治算法概述4.3.2二分法4.3.3二分法变异4.3.4其它分治方法494.3.1分治算法概述

1.算法设计思想分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。50分治法的基本步骤在每一层递归上都有三个步骤：1)分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

2)解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；

3)合并：将已求解的各个子问题的解，逐步合并为原问题的解。51有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中后，其它的子问题就不必求解了。分治法的这类应用，又称为"减治法"。多数问题需要所有子问题的解，并由子问题的解，使用恰当的方法合并成为整个问题的解，比如合并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。

522.适合用分治法策略的问题当求解一个规模相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。1)

能将n个数据分解成k个不同子集合，且得到的k个子集合是可以独立求解的子问题；2)

分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；在求出这些子问题的解之后，就可以推解出原问题的解；

534.3.2典型二分法当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。54【例1】金块问题：

老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较贵重的仪器，我们希望用最少的比较次数找出最重和最轻的金块。55算法设计1：比较简单的方法是逐个的进行比较查找。先拿两块比较重量，留下重的一个与下一块比较，直到全部比较完毕，就找到了最重的金子。算法类似于一趟选择排序，算法如下：

maxmin(floata[],intn,float&max,float&min){max=min=a[1];

for(i=2i<=ni++)

if(max<a[i])max=a[i];elseif(min>a[i])min=a[i];

}56算法分析1：

算法中需要n-1次比较得到max。最好的情况是金块是由小到大取出的，不需要进行与min的比较，共进行n-1次比较。最坏的情况是金块是由大到小取出的，需要再经过n-1次比较得到min,共进行2*(n-1)次比较。至于在平均情况下，A(i)将有一半的时间比max大，因此平均比较数是3*(n-1)/2。

57算法设计2:用二分法可以用较少比较次数地解决上述问题：1)

将数据等分为两组(两组数据可能差1)，目的是分别选取其中的最大(小)值。2)

递归分解直到每组元素的个数≤2，可简单地找到最大(小)。3)

回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。

58算法2递归求取最大和最小元素floata[n];maxmin(inti,intj,float&fmax,float&fmin){intmid;floatlmax,lmin,rmax,rmin;

if(i=j){fmax=a[i];fmin=a[i];}

elseif(i=j-1)if(a[i]<a[j]){fmax=a[j]；fmin=a[i];}

else{fmax=a[i];fmin=a[j];}

else{mid=(i+j)/2;

maxmin(i，mid，lmax，lmin);

maxmin(mid+1，j，rmax，rmin);

if(lmax>rmax)fmax=lmax;elsefmax=rmax;

if(lmin>rmin)fmin=rmin;elsefmin=lmin;

}594.3.3二分法不相似情况对一维数据进行二分法分解，得到两个独立子问题。对二维问题的二分法分解，会得到几个独立的子问题呢？60【例1】残缺棋盘残缺棋盘是一个有2k×2k(k≥1)个方格的棋盘，其中恰有一个方格残缺。下图给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。

①号②号③号④号四种三格板这样的棋盘我们称作"三格板"，残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：1)两个三格板不能重叠2)三格板不能覆盖残缺方格，但必须覆盖其他所有的方格在这种限制条件下，所需要的三格板总数为(2k×2k-1)/3。

61算法设计：下面用分而治之方法解决残缺棋盘问题。1)以k=2时的问题为例，用二分法进行分解，得到的是如下图，用双线划分的四个k=1的棋盘。但要注意这四个棋盘，并不都是与原问题相似且独立的子问题。因为当如图中的残缺方格在左上部时，第1个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘(也就是图中标识为2、3、4号子棋盘)，并不是原问题的相似子问题，自然也就不能独立求解了。当使用一个①号三格板(图中阴影)覆盖2、3、4号三个子棋盘的各一个方格后，我们把覆盖后的方格，也看作是残缺方格(称为"伪"残缺方格)，这时的2、3、4号子问题就是独立且与原问题相似的子问题了。

62从以上例子还可以发现，当残缺方格在第1个子棋盘，用①号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；同样地当残缺方格在第2个子棋盘时，则首先用②号三格板进行棋盘覆盖，当残缺方格在第3个子棋盘时，则首先用③号三格板进行棋盘覆盖，当残缺方格在第4个子棋盘时，则首先用④号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。同样地k=1，2，3，4……都是如此，k=1为停止条件。

632)棋盘的识别子棋盘的左上角的方格所在行、列,加上子棋盘的大小，就可以唯一确定一个子棋盘。残缺方格或“伪”残缺方格直接用行、列号记录。•tr棋盘中左上角方格所在行。•tc棋盘中左上角方格所在列。•dr残缺方块所在行。•dl残缺方块所在列。•size棋盘的大小（即行数或列数）。64数据结构设计：

用二维数组board[][]模拟棋盘。覆盖残缺棋盘所需要的三格板数目为：(size2-1)/3。将这些三格板编号为1到(size2-1)/3。将三格板编号存储在数组board[][]的对应位置，这样输出数组内容就是问题的解。65算法如下：intamount=0,Board[100][100];main(){intsize=1,x,y;input(k);for(i=1;i<=k;i++)size=size*2;print("inputincompletepane");input(x,y);Cover(0,0,x,y,size);OutputBoard(size);}66Cover(inttr,inttc,intdr,intdc,intsize){ints,t;if(size<2)return;amount=amount+1t=amount;//所使用的三格板的数目s=size/2;//子问题棋盘大小

if(dr<tr+s&&dc<tc+s)//残缺方格位于左上棋盘｛Cover(tr,tc,dr,dc,s);Board[tr+s-1][tc+s]=t;//覆盖１号三格板Board[tr+s][tc+s-1]=t;Board[tr+s][tc+s]=t;Cover(tr,tc+s,tr+s-1,tc+s,s);//覆盖其余部分Cover(tr+s,tc,tr+s,tc+s-1,s);Cover(tr+s,tc+s,tr+s,tc+s,s);｝67

elseif(dr<tr+s&&dc>=tc+s)//残缺方格位于右上象限｛Cover(tr,tc+s,dr,dc,s);Board[tr+s-1][tc+s-1]=t;//覆盖２号三格板Board[tr+s][tc+s-1]=t;Board[tr+s][tc+s]=t;Cover(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余部分Cover(tr+s,tc,tr+s,tc+s-1,s);Cover(tr+s,tc+s,tr+s,tc+s,s);}

elseif(dr>=tr+s&&dc<tc+s)//残缺方格位于覆盖左下｛Cover(tr+s,tc,dr,dc,s);Board[tr+s-1][tc+s-1]=t;//覆盖３号三格板Board[tr+s-1][tc+s]=t;Board[tr+s][tc+s]=t;Cover(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余部分Cover(tr,tc+s,tr+s-1,tc+s,s);Cover(tr+s,tc+s,tr+s,tc+s,s);｝68

elseif(dr>=tr+s&&dc>=tc+s)//残缺方格位于右下象限｛Cover(tr+s,tc+s,dr,dc,s);Board[tr+s-1][tc+s-1]=t;//覆盖４号三格板Board[tr+s-1][tc+s]=t;Board[tr+s][tc+s-1]=t;Cover(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余部分Cover(tr,tc+s,tr+s-1,tc+s,s);Cover(tr+s,tc,tr+s,tc+s-1,s);｝}voidOutputBoard(intsize){for(inti=0;i<size;i++){for(intj=0;j<size;j++)print(Board[i][j]);print("换行符");}}算法分析：因为要覆盖(size2-1)/3个三格板，所以算法的时间复杂性为Ｏ(size2)。

694.3.4二分法不独立情况

【例1】求数列的最大子段和给定n个整数a1,a2,…an。求ai…aj的子段，使其和最大。当所有整数为负数时定义其最大子段和为0。如-2，11，-4，13，-5，-2，最大子段和为2070问题分析：若用二分法将实例中的数据分解为两组(-2,11,-4),(13,-5,-2)，第一个子问题的解是11，第二个子问题的解是13，两个子问题的解不能简单地得到原问题的解。由此看出这个问题不能分解用二分法成解为独立的两个子问题，子问题中间还有公共的子问题，这类问题称为子问题重叠类的问题。

那么，怎样解决这类问题呢？下面我们用二分法解决这类问题中的一些简单问题，学习一下如何处理不独立的子问题。71算法设计：

分解方法采用二分法，虽然分解后的子问题并不独立，但通过对重叠的子问题进行专门处理，并对所有子问题合并进行设计，就可以用二分策略解决此题。72如果将所给的序列a[1..n]分为长度相等的2段a[1-(n/2)]和a[(n/2)+1-n],分别求出这2段的最大子段和,则a[1..n]的最大子段和有3种情形。1)a[1..n]的最大子段和与a[1..(n/2)]的最大子段和相同;2)a[1..n]的最大子段和与a[(n/2)+1..n]的最大子段和相同;3)a[1..n]的最大子段和为a[i..j],且1≤i≤(n/2),(n/2),(n/2)+1≤j≤n。情况1)和情况2)可分别递归求得。对于情况3),a[(n/2)]与a[(n/2)+1]一定在最优子序列中。因此,我们可以计算出a[i..(n/2)]的最大值s1;并计算出a[(n/2)+1..j]中的最大值s2。则s1+s2即为出现情况3)时的最优值。73算法如下：MaxSubSum(inta[],intleft,intright){intcenter,i,j,sum,leftsum,rightsum,s1,s2,lefts,rights;if(left=right){if(a[left]>0)return(a[left]);elsereturn(0);}else{center=(left+right)\2;

leftsum=MaxSubSum(a,left,center);rightsum=MaxSubSum(a,center+1,right);s1=0;/处理情形3/lefts=0;74for(i=center;i>=left;i--){lefts=lefts+a[i];if(lefts>s1)s1=lefts;}s2=0;rights=0;for(i=center+1;i<=right;i++){rights=rights+a[i];if(rights>s2)s2=rights;}

if(s1+s2<leftsumandrightsum<left_sum)rturn(leftsum);if(s1+s2<rightsum)return(rightsum);return(s1+s2);}}754.3.5

非等分分治

以上的例子都是用二分策略把问题分解为与原问题相似的子问题。下面看几个用非等分二分法解决问题的例子。选择问题就是从一组数中选择的第k小的数据，这个问题的一个应用就是寻找中值元素，此时k=[n/2]。中值是一个很有用的统计量，例如中间工资，中间年龄，中间重量等。k取其他值也是有意义的，例如，通过寻找第k=n/2、k=n/3和k=n/4的年龄,可将人口进行划分，了解人口的分布情况。

76这个问题可以通过排序来解决，但根据《数据结构》课程的经验，最好的排序算法的复杂性也是O(n*log(n))，下面我们要利用分治法，找到复杂性为O(n)的算法。但这个问题不能用简单的二分法分解成完全独立、相似的两个子问题。因为在选出分解后第一组的第k小的数据和第二组的第k小的数据，不能保证在这两个数据之一是原问题的解。77【例1】选择问题1：求一组数的第二小的数。

算法设计：这个问题不能用简单的二分法分解成相似的两个子问题。因为在选出分解后第一组的第二小的数据和第二组的第二小的数据，不能保证在这两个数据之一是原问题的解。但是，可以在两个子集中分别选出最小的两个数，共得到4个数，则第二小的数在这4个数中。78floata[n];second(inti,intj，float&fmin2,&fmin1)

{floatlmin2,lmin1,rmin2,rmin;intmid;