第四章算法策略

第四章算法策略第1页，共82页，2023年，2月20日，星期三4.1迭代算法4.1.1递推法4.1.2倒推法4.1.3迭代法解方程第2页，共82页，2023年，2月20日，星期三4．1．1递推法

【例1】兔子繁殖问题问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。问题分析：因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数(用斜体数字表示)显然由前两个月的小兔子的对儿数决定。则繁殖过程如下：一月二月三月四月五月六月……111+1=22+1=33+2=55+3=8……第3页，共82页，2023年，2月20日，星期三算法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；

}}数学建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，……。第4页，共82页，2023年，2月20日，星期三算法2：

表4-1递推迭代表达式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项。

第5页，共82页，2023年，2月20日，星期三

表4-2递推迭代表达式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：第6页，共82页，2023年，2月20日，星期三【例2】求两个整数的最大公约数。数学建模：辗转相除法是根据递推策略设计的。不妨设两个整数a>b且a除以b商x余c；则a-bx=c，不难看出a、b的最大公约数也是c的约数（一个数能整除等式左边就一定能整除等式的右边），则a、b的最大公约数与b、c的最大公约数相同。同样方法推出b、c的最大公约数与……，直到余数为0时，除数即为所求的最大公约数。算法设计：循环“不变式”第一次是求a、b相除的余数c，第二次还是求“a”“b”

相除的余数，经a=b,b=c操作，就实现了第二次还是求“a”“b”

相除的余数，这就找到了循环不变式。循环在余数c为0时结束。

第7页，共82页，2023年，2月20日，星期三算法如下：main（）{inta,b;input(a,b);if(b=0)

{print(“dataerror”);return;}else{c=amodb;whilec<>0{a=b;b=c;c=amodb;}}print(b);}第8页，共82页，2023年，2月20日，星期三4.1.2倒推法

所谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从后向前推解问题的方法。如下面的例题，因不同方面的需求而采用了倒推策略。例1在不知前提条件的情况下，经过从后向前递推，从而求解问题。即由结果倒过来推解它的前提条件。又如例2由于存储的要求，而必须从后向前进行推算。另外，在对一些问题进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法（如例3），则问题容易理解和解决。下面分别看这几个例子：第9页，共82页，2023年，2月20日，星期三【例1】猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第10天时就只有一个桃子了，求原有多少个桃？数学模型：每天的桃子数为：a10=1,a9=(1+a10)*2,a8=(1+a9)*2,……a10=1，递推公式为：ai=(1+ai+1)*2I=9,8,7,6……1算法如下：

main(){inti,s;s=1;for(i=9;i>=1;i=i-1)s=(s+1)*2print(s)；

}第10页，共82页，2023年，2月20日，星期三【例2】输出如图4-1的杨辉三角形（限定用一个一维数组完成）。数学模型：上下层规律较明显，中间的数等于上行左上、右上两数之和。问题分析：题目中要求用一个一维数组即完成。数组空间一定是由下标从小到大利用的，这样其实杨辉三角形是按下图4-2形式存储的。若求n层，则数组最多存储n个数据。

111121133114641

……………

图4-1杨辉三角形11112113311

4641……………图4-2杨辉三角形存储格式

算法设计：

A[1]=A[i]=1A[j]=A[j]+A[j-1]j=i-1，i-2，……，2i行i-1行i-1行第11页，共82页，2023年，2月20日，星期三算法如下：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(“换行符”);}}第12页，共82页，2023年，2月20日，星期三【例3】穿越沙漠问题用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑，耗油率为1加仑/公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。

问题分析：

1）先看一简单问题：有一位探险家用5天的时间徒步横穿A、B两村，两村间是荒无人烟的沙漠，如果一个人只能担负3天的食物和水，那么这个探险家至少雇几个人才能顺利通过沙漠。

第13页，共82页，2023年，2月20日，星期三

A城雇用一人与探险家同带3天食物同行一天，然后被雇人带一天食物返回，并留一天食物给探险家，这样探险家正好有3天的食物继续前行，并于第三天打电话雇B城人带3天食物出发，第四天会面他们会面，探险家得到一天的食物赴B城。如图4-3主要表示了被雇用二人的行程。

AB

图4-3被雇用二人的行程

2）贮油点问题要求要以最少的耗油量穿越沙漠，即到达终点时，沙漠中的各临时油库和车的装油量均为0。这样只能从终点开始向前倒着推解贮油点和贮油量。第14页，共82页，2023年，2月20日，星期三数学模型：根据耗油量最少目标的分析，下面从后向前分段讨论。第一段长度为500公里且第一个加油点贮油为500加仑。第二段中为了贮备油，吉普车在这段的行程必须有往返。下面讨论怎样走效率高：1）首先不计方向这段应走奇数次（保证最后向前走）。2）每次向前行进时吉普车是满载。3）要能贮存够下一加油点的贮油量，路上耗油又最少。……第15页，共82页，2023年，2月20日，星期三下图是满足以上条件的最佳方案，此段共走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）……图4-4贮油点及贮油量示意第16页，共82页，2023年，2月20日，星期三综上分析，从终点开始分别间隔500，500/3，500/5，500/7，……（公里）设立贮油点，直到总距离超过1000公里。每个贮油点的油量为500，1000，1500，……。算法设计：由模型知道此问题并不必用倒推算法解决（只是分析过程用的是倒推法），只需通过累加算法就能解决。变量说明：dis表示距终点的距离，1000-dis则表示距起点的距离，k表示贮油点从后到前的序号。第17页，共82页，2023年，2月20日，星期三desert（）{intdis，k，oil,k;dis=500;k=1;oil=500;do{

print(“storepoint”,k,”distance”,1000-dis,”oilquantity”,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(“storepoint”,k,”distance”,0,”oilquantity”,oil)；

}第18页，共82页，2023年，2月20日，星期三4.1.3迭代法解方程迭代法解方程的实质是按照下列步骤构造一个序列x0,x1,…,xn,来逐步逼近方程f(x)=0的解：

1）选取适当的初值x0；

2）确定迭代格式，即建立迭代关系，需要将方程f(x)=0改写为x=φ(x)的等价形式；构造序列x0，x1，……，xn，即先求得x1=φ(x0)，再求

x2=φ(x1)，……如此反复迭代，就得到一个数列x0，

x1，……，xn，若这个数列收敛，即存在极值，且函数

φ(x)连续，则很容易得到这个极限值

x*就是方程f(x)=0的根。

第19页，共82页，2023年，2月20日，星期三【例1】迭代法求方程组根

算法说明：方程组解的初值X=（x0，x1，…，xn-1）,迭代关系方程组为：xi=gi(X)(i=0,1,…,n-1),w为解的精度,则算法如下：

for

(i=0;i<n;i++)

x[i]=初始近似根;

do{k=k+1;for

(i=0;i<n;i

y[i]=x[i];

for

(i=0;i<n;i++)

x[i]=gi(X);

for

(i=0;i<n;i++)c=c+fabs(y[i]-x[i])；

}

while

(c>wandk<maxn)；

for

(i=0;i<n;i++)

print(i，“变量的近似根是”，x[i])；

}第20页，共82页，2023年，2月20日，星期三【例2】牛顿迭代法牛顿迭代法又称为切线法，它比一般的迭代法有更高的收敛速度，如图4-5所示。首先,选择一个接近函数f(x)零点的x0,计算相应的f(x0)和切线斜率f‘(x0)（这里f’表示函数f的导数）。然后我们计算穿过点(x0,f(x0))且斜率为f‘(x0)的直线方程为：和x轴的交点的x坐标,也就是求如下方程的解：

将新求得交点的x坐标命名为x1。如图4-5所示，通常x1会比x0更接近方程f(x)=0的解。接下来用x1开始下一轮迭代

.图4-5牛顿迭代法

示意图第21页，共82页，2023年，2月20日，星期三迭代公式可化简为：此公式就是有名的牛顿迭代公式。已经证明,如果f‘是连续的,并且待求的零点x是孤立的,那么在零点x周围存在一个区域,只要初始值x0位于这个邻近区域内,那么牛顿法必定收敛。

下面给出用牛顿迭代法，求形如ax3+bx2+cx+d=0方程根的算法，系数a、b、c、d的值依次为1、2、3、4，由主函数输入。求x在1附近的一个实根。求出根后由主函数输出。

第22页，共82页，2023年，2月20日，星期三main(){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);}第23页，共82页，2023年，2月20日，星期三令[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.算法如下：

图4-6二分法求解方程示意【例3】二分法求解方程f(x)=0根用二分法求解方程f(x)=0根的前提条件是：f(x)在求解的区间[a,b]上是连续的，且已知f(a)与f(b)异号，即f(a)*f(b)<0。第24页，共82页，2023年，2月20日，星期三main(){floatx,x1=0,x2=2,f1,f2,f;print(“inputa,b(f(a)*f(b)<0)”);input(a,b);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=x1*x1*x1/2+2*x1*x1-8;}elsex2=x;}while(fabs(f)>=1e-4);print("root=",x);}第25页，共82页，2023年，2月20日，星期三4.2蛮力法4.2.1枚举法4.2.2其它范例

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

第26页，共82页，2023年，2月20日，星期三4．2．1枚举法

枚举（

enumerate）法（穷举法）是蛮力策略的一种表现形式，也是一种使用非常普遍的思维方法。它是根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。用枚举法解决问题，通常可以从两个方面进行算法设计：

1）找出枚举范围：分析问题所涉及的各种情况。

2）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。第27页，共82页，2023年，2月20日，星期三【例1】百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?算法设计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

第28页，共82页，2023年，2月20日，星期三算法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);}

}第29页，共82页，2023年，2月20日，星期三算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低算法设计2：在公鸡（x）、母鸡（y）的数量确定后，小鸡

的数量

z就固定为100-x-y，无需再进行枚举了

此时约束条件只有一个：

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

算法2如下：

第30页，共82页，2023年，2月20日，星期三main()

{

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时的算术计算和条件判断，进一步提高了算法的效率。

第31页，共82页，2023年，2月20日，星期三【例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，共尝试800次。2)约束条件为：每次尝试，先求六位数与A的积，再测试积的各位是否相同，若相同则找到了问题的解。测试积的各位是否相同比较简单的方法是，从低位开始，每次都取数据的个位，然后整除10，使高位的数字不断变成个位，并逐一比较。

第32页，共82页，2023年，2月20日，星期三算法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);}}第33页，共82页，2023年，2月20日，星期三算法说明1：算法中对枚举出的每一个五位数与A相乘，结果存储在变量E中。然后，测试得到的六位数E是否各个位的数字都相同。鉴于要输出结果，所以不要改变计算结果，而另设变量E1，用于测试运算。算法分析1：以上算法的尝试范围是A：3——9，B：0——9，C：0——9。共尝试800次，每次，不是一个好的算法。算法设计2：将算式变形为除法：DDDDDD/A=ABCAB。此时只需枚举A：3——9D：1——9，共尝试7*9=63次。每次尝试，测试商的万位、十位与除数是否相同，千位与个位是否相同，都相同时为解。算法2如下:第34页，共82页，2023年，2月20日，星期三main（）{intA,B,C,D,E,F;for(A=3;A<=9;A++)for(D=1;D<=9;D++){E=D*100000+D*10000+D*1000+D*100+D*10+D;if(EmodA=0)F=E\A;if(F\10000=Aand(Fmod100)\10=A)if(F\1000==Fmod10)print(F，”*”，A，”=”，E);}}第35页，共82页，2023年，2月20日，星期三蛮力法的表现形式非常多，如第三章3.2.4例题、3.2.5例1及本章下一节4.3.3例4的算法1等。本节将通过蛮力策略，用算法模拟问题中所描述的全部过程和全部状态，来找出问题的解，并与经过数学建模后的算法进行效率上的比较。

4．2．2其它范例第36页，共82页，2023年，2月20日，星期三【例3】狱吏问题某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁,每转动一次,原来锁着的被打开,原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1间转动一次；问通过n次后，那些牢房的锁仍然是打开的？第37页，共82页，2023年，2月20日，星期三算法设计1：1）用n个空间的一维数组a[n],每个元素记录一个锁的状态，1为被锁上，0为被打开。2）用数学运算方便模拟开关锁的技巧，对i号锁的一次开关锁可以转化为算术运算：a[i]=1-a[i]。3）第一次转动的是1，2，3，……，n号牢房；第二次转动的是2，4，6，……号牢房；第三次转动的是3，6，9，……号牢房；

……第i次转动的是i，2i，3i，4i，……号牢房，是起点为i，公差为i的等差数列。

4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关锁过程，最后当第i号牢房对应的数组元素a[i]为0时，该牢房的囚犯得到大赦。算法1如下：

第38页，共82页，2023年，2月20日，星期三main1(){int*a,i,j,n;input(n);a=calloc(n+1,sizeof(int));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)。第39页，共82页，2023年，2月20日，星期三问题分析：转动门锁的规则可以有另一种理解，第一次转动的是编号为1的倍数的牢房；第二次转动的是编号为2的倍数的牢房；第三次转动的是编号为3的倍数的牢房；……则狱吏问题是一个关于因子个数的问题。令d(n)为自然数n的因子个数，这里不计重复的因子，如4的因子为1，2，4共三个因子，而非1，2，2，4。则d(n)有的为奇数，有的为偶数，见下表:

表4-3编号与因数个数的关系

n12345678910111213141516……d(n)1223242434262445……

数学模型1：上表中的d(n)有的为奇数，有的为偶数，由于牢房的门开始是关着的，这样编号为i的牢房，所含1——i之间的不重复因子个数为奇数时，牢房最后是打开的，反之，牢房最后是关闭的。第40页，共82页，2023年，2月20日，星期三算法设计2:

1）算法应该是求出每个牢房编号的不重复的因子个数，当它为奇数时，这里边的囚犯得到大赦。2）一个数的因子是没有规律的，只能从1——n枚举尝试。算法2如下：main2(){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.”);}}第41页，共82页，2023年，2月20日，星期三算法分析：狱吏开关锁的主要操作是a[i]=1-a[i];共执行了n*(1+1/2+1/3+……+1/n)次，时间近似为复杂度为O（nlogn）。使用了n个空间的一维数组。算法2没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其主要操作是判断imodj是否为0，共执行了n*(1+2+3+……+n)次，时间复杂度为O（n2）。

数学模型2：仔细观察表4-3，发现当且仅当n为完全平方数时,d(n)为奇数；这是因为n的因子是成对出现的,也即当n=a*b且a≠b时，必有两个因子a，b;只有n为完全平方数，也即当n=a2时,才会出现d(n)为奇数的情形。算法设计3：这时只需要找出小于n的平方数即可。算法3如下：第42页，共82页，2023年，2月20日，星期三main3(){ints,i,j,n;input(n);for(i=1;i<=n;i++)if（i*i<=n）print(i,”isfree.”);elsebreak;}

由此算法我们应当注意：在对运行效率要求较高的大规模的数据处理问题时，必须多动脑筋找出效率较高的数学模型及其对应的算法。第43页，共82页，2023年，2月20日，星期三4.3分而治之算法4.3.1分治算法框架4.3.2二分法4.3.3二分法变异4.3.4其它分治方法第44页，共82页，2023年，2月20日，星期三4．3．1分治算法框架

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

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

3）合并：将已求解的各个子问题的解，逐步合并为原问题的解。第45页，共82页，2023年，2月20日，星期三有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中后，其它的子问题就不必求解了，问题的解就是最后（最小）的子问题的解。分治法的这类应用，又称为“减治法”。多数问题需要所有子问题的解，并由子问题的解，使用恰当的方法合并成为整个问题的解，比如合并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。

第46页，共82页，2023年，2月20日，星期三2．适合用分治法策略的问题当求解一个输入规模为n且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。1）

能将这n个数据分解成k个不同子集合，且得到k个子集合是可以独立求解的子问题，其中1＜k≤n；2）

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

第47页，共82页，2023年，2月20日，星期三分治法的一般的算法设计模式如下：Divide-and-Conquer(intn)/n为问题规模/{if（n≤n0）/n0为可解子问题的规模/

{解子问题；

return(子问题的解)；}for（i=1;i<=k;i++）/分解为较小子问题p1,p2,……pk/

yi=Divide-and-Conquer(|Pi|);/递归解决Pi/

T=MERGE(y1,y2,...,yk);/合并子问题/return(T);}

其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1,P2,...,Pk的相应的解y1,y2,...,yk合并为P的解。在一些问题中不需要这一步。如析半查找、4．3．2中的例1、例2等。第48页，共82页，2023年，2月20日，星期三4．3．2二分法不同于现实中对问题（或工作）的分解，可能会考虑问题（或工作）的重点、难点、承担人员的能力等来进行问题的分解和分配。在算法设计中每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。第49页，共82页，2023年，2月20日，星期三【例1】金块问题：老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。算法设计1：比较简单的方法是逐个的进行比较查找。先拿两块比较重量，留下重的一个与下一块比较，直到全部比较完毕，就找到了最重的金子。算法类似于一趟选择排序，算法如下：

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

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

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

}第50页，共82页，2023年，2月20日，星期三算法分析1：算法中需要n-1次比较得到max。最好的情况是金块是由小到大取出的，不需要进行与min的比较，共进行n-1次比较。最坏的情况是金块是由大到小取出的，需要再经过n-1次比较得到min,共进行2*n-2次比较。至于在平均情况下，A(i)将有一半的时间比max大，因此平均比较数是3(n—1)/2。

算法设计2:问题可以简化为：在含n（n是2的幂（n>=2））个元素的集合中寻找极大元和极小元。用分治法（二分法）可以用较少比较次数地解决上述问题：1）

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

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

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

第51页，共82页，2023年，2月20日，星期三算法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;

}第52页，共82页，2023年，2月20日，星期三

算法分析：MAXMIN需要的元素比较数是多少呢？如果用T(n)表示这个数，则所导出的递归关系式是:

当n是2的幂时，即对于这个某个正整数k，n=2k，有

可以证明，任何以元素比较为基础的找最大和最小元素的算法，其元素比较下界均为次。因此，过程MAXMIN在这种意义上是最优的。第53页，共82页，2023年，2月20日，星期三【例2】残缺棋盘残缺棋盘是一个有2k×2k

（k≥1）个方格的棋盘，其中恰有一个方格残缺。图4-7给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。

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

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

图4-8一个4*4的残缺棋盘第55页，共82页，2023年，2月20日，星期三从以上例子还可以发现，当残缺方格在第1个子棋盘，用①号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；同样地（如下图4-9所示），当残缺方格在第2个子棋盘时，则首先用②号三格板进行棋盘覆盖，当残缺方格在第3个子棋盘时，则首先用③号三格板进行棋盘覆盖，当残缺方格在第4个子棋盘时，则首先用④号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。如下图4-9：同样地k=1，2，3，4……都是如此，k=1为停止条件。

图4-9其它4*4的残缺棋盘第56页，共82页，2023年，2月20日，星期三2）棋盘的识别棋盘的规模是一个必要的信息，有了这个信息，只要知道其左上角的左上角方格所在行、列就可以唯一确定一个棋盘了，残缺方格或“伪”残缺方格直接用行、列号记录。•tr棋盘中左上角方格所在行。•tc棋盘中左上角方格所在列。•dr残缺方块所在行。•dl残缺方块所在列。•size棋盘的行数或列数。数据结构设计：用二维数组board[][]，模拟棋盘。覆盖残缺棋盘所需要的三格板数目为：(size2-1)/3将这些三格板编号为1到(size2-1)/3。则将残缺棋盘三格板编号的存储在数组board[][]的对应位置中，这样输出数组内容就是问题的解。结合图4-9，理解算法。第57页，共82页，2023年，2月20日，星期三算法如下：

intamount=0;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);}图4-9一个4*4的残缺棋盘及其解

第58页，共82页，2023年，2月20日，星期三

Cover(inttr,inttc,intdr,intdc,intsize){if(size<2)return;intt=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);｝第59页，共82页，2023年，2月20日，星期三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);｝第60页，共82页，2023年，2月20日，星期三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）。

第61页，共82页，2023年，2月20日，星期三4．3．3二分法变异

【例３】求最长连续不升数列有一组数据找出其中最长的连续不升数列算法设计：此问题用二分法分解后的两个子序列（子问题）并不独立，因为有可能最长的连续不升数列正好存在于两个子序列的连接位置。如果将所给的序列a[1..n]分为长度相等的2段

a[1——(n/2)]和a[(n/2)+1——n],则a[1.n]的最长连续不升数列有3种情况：

第62页，共82页，2023年，2月20日，星期三问题分析：若用二分法将实例中的数据分解为两组(-2,11,-4),（13,-5,-2），第一个子问题的解是11，第二个子问题的解是13，两个子问题的解不能简单地得到原问题的解。由此看出这个问题不能分解用二分法成解为独立的两个子问题，子问题中间还有公共的子问题，这类问题称为子问题重叠类的问题。那么，怎样解决这类问题呢？虽没有通用的方法，但本章4.5节的介绍的动态规划算法是一种较好的解决方法。下面我们仍用二分法解决这类问题中的一些简单问题，学习一下如何处理不独立的子问题。算法设计：分解方法和上面的例题一样采用二分法，虽然分解后的子问题并不独立，但通过对重叠的子问题进行专门处理，并对所有子问题合并进行设计，就可以用二分策略解决此题。第63页，共82页，2023年，2月20日，星期三如果将所给的序列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[k],且

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)时的最优值。第64页，共82页，2023年，2月20日，星期三算法如下：intmax_sum3(inta[],intn){return(max_sub_sum(a,1,n));}max_sub_sum(inta[],intleft,intright){intcenter,i,j,sum,left_sum,right_sum,s1,s2,lefts,rights;if(left=right)if(a[left]>0)return(a[left]);elsereturn(0);else{center=(left+right)/2;left_sum=max_sub_sum(a,left,center);right_sum=max_sub_sum(a,center+1,right);s1=0;/处理情形3/lefts=0;第65页，共82页，2023年，2月20日，星期三for(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<left_sumandright_sum<left_sum)rturn(left_sum);if(s1+s2<right_sum)return(right_sum);return(s1+s2);}}第66页，共82页，2023年，2月20日，星期三【例4】大整数乘法在某些情况下，我们需要处理很大的整数，它无法在计算机硬件能直接允许的范围内进行表示和处理。若用浮点数来存储它，只能近似地参与计算，计算结果的有效数字会受到限制。若要精确地表示大整数，并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。请设计一个有效的算法，可以进行两个n位大整数的乘法运算。数据结构设计：首先用数组存储大整数数据，再将两个乘数和积都按由低位到高位逐位存储到数组元素中。算法设计1：存储好两个高精度数据后，模拟竖式乘法，让两个高精度数据的按位交叉相乘，并逐步累加即可得到精确的结果，用二重循环就可实现。

第67页，共82页，2023年，2月20日，星期三算法设计1：存储好两个高精度数据后，我们模拟竖式乘法，让两个高精度数据的按位交叉相乘，并逐步累加，即可得到精确的计算结果。用二重循环就可控制两个数不同位相乘的过程。只考虑正整数的乘法，算法细节设计如下：1)对于大整数比较方便的输入方法是，按字符型处理，存储在字符串数组s1、s2中，计算结果存储在整型数组a中。2)通过字符的ASCII码，数字字符可以直接参与运算，k位数字与j位数字相乘的表达式为：s1[k]-48)*(s2[j]-48)。这是C语言的处理方法，其它程序设计语言有对应的函可以实现数字字符与数字的转换，这里不详细介绍了。3)每一次数字相乘的结果位数是不固定的，而结果数组中每个元素只存储一位数字，所以用变量b暂存结果，若超过1位数则进位，用变量d存储。这样每次计算的表达式为：

b=a[i]+(s1[k]-48)*(s2[j]-48)+d;。第68页，共82页，2023年，2月20日，星期三main(){longb,c,d;inti,i1,i2,j,k,n,n1,n2,a[256];chars1[256],s2[256];input(s1);input(s2);for(i=0;i<255;i++)a[i]=0;n1=strlen(s1);n2=strlen(s2);d=0;for(i1=0,k=n1-1;i1<n1;i1++,k--){for(i2=0,j=n2-1;i2<n2;i2++,j--){i=i1+i2;b=a[i]+(s1[k]-48)*(s2[j]-48)+d;a[i]=bmod10;d=b/10;}while(d>0){i=i+1;a[i]=a[i]+dmod10;d=d/10;}n=i;}for(i=n;i>=0;i--)print(a[i]);}第69页，共82页，2023年，2月20日，星期三算法说明：循环变量j、k分别是两个乘数字符串的下标。i1表示字符串str1由低位到高位的位数，范围0——n1-1（与k相同）。i2表示字符串str2由低位到高位的位数，范围0——n2-1（与j相同）。i表示乘法正在运算的位，也是计算结果存储的位置。算法分析1：算法是以n1,n2代表两个乘数的位数，由算法中的循环嵌套知，算法的主要操作是乘法，算法的时间复杂度是O（n1*n2）。

算法设计2：下面们用分治法来设计一个更有效的大整数乘积算法。设计的重点是要提高乘法算法的效率，设计如下：

设X和Y都是n位的二进制整数，现在要计算它们的乘积X*Y。图4-10大整数X和Y的分段第70页，共82页，2023年，2月20日，星期三将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，如图4-10所示。显然问题的答案并不是A*C*K1+C*D*K2（K1、K2与A、B、C、D无关），也就是说，这样做并没有将问题分解成两个独立的子问题。按照乘法分配律，分解后的计算过程如下：记：X=A*2n/2+B，Y=C*2n/2+D。这样，X和Y的乘积为：X*Y=(A*2n/2+B)(C*2n/2+D)=A*C*2n+(AD+CB)*2n/2+B*D

(1)模型分析：如果按式(1)计算X*Y，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法，此外还要做2次移位(分别对应于式(1)中乘2n和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2个n位整数相乘所需的运算总数，则由式(1)，我们有以下(2)式：

第71页，共82页，2023年，2月20日，星期三

T（1）=1T（n）=4T(n/2)+O(n)（2）

由此递归式迭代过程如下：T(n)=4T(n/2)+cn=4(4T(n/4)+cn/2)+cn=16(T(n/8)+cn/4)+3cn/2+cn=……=

+4k-1*2c+4k-2*4c+……+4c2k-1+c2k

=O（4k）=O(nlog4)=O（n2）所以可得算法的时间复杂度为T(n)=O(n2)。第72页，共82页，2023年，2月20日，星期三模型改进：可以把X*Y写成另一种形式：X*Y=A*C*2n+[(A-B)(D-C)+AC+BD]*2n/2+B*D

(3)式(3)看起来比式(1)复杂，但它仅需做3次n/2位整数的乘法：AC，BD和(A-B)(D-C)，6次加、减法和2次移位。由此可得:

(4)

用解递归方程的迭代公式法，不妨设n=2k：

T(n)=3T(n/2)+cn=3(3T(n/4)+cn/2)+cn=9(T(n/8)+cn/4)+3cn/2+cn=……=3k+3k-1*2c+3k-2*4c+……+3c2k-1+c2k=O(nlog3)则得到T(n)=O(nlog3)=O(n1.59)。第73页，共82页，2023年，2月20日，星期三MULT(X,Y,n){X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY}

{S=SIGN(X)*SIGN(Y);//S为X和Y的符号乘积

X=ABS(X);

Y=ABS(Y);//X和Y分别取绝对值

if（n=1）

if(X=1andY=1)return(S)；

elsereturn(0)；

else{

A=X的左边n/2位;B=X的右边n/2位;

C=Y的左边n/2位;D=Y的右边n/2位;

ml=MULT(A,C,n/2);m2=MULT(A-B,D-C,n/2);

m3=MULT(B,D,n/2);

S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);

return(S);}

}第74页，共82页，2023年，2月20日，星期三4．3．4其它分治方法

以上的例子都是用二分策略把问题分解为与原问题相似“相等”的子问题。下面看几个用“非等分二分法”解决问题的例子。选择问题就是“从一组数中选择的第k小的数据”，这个问题的一个应用就是寻找中值元素，此时k=[n/2]。中值是一个很有用的统计量，例如中间工资，中间年龄，中间重量等。k取其他值也是有意义的，例如，通过寻找第k=n/2、k=n/3和k=n/4的年龄,可将人口进行划分，了解人口的分布情况。这个问题可以通过排序来解决，但根据《数据结构》课程的经验，最好的排序算法的复杂性也是O（n*log(n)），下面我们要利用分治法，找