《第四章算法策略》由会员分享，可在线阅读，更多相关《第四章算法策略（82页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章基本的算法策略基本的算法策略4.1 4.1 迭代算法迭代算法4.2 4.2 蛮力算法蛮力算法4.3 4.3 分而治之算法分而治之算法4.4 4.4 贪婪算法贪婪算法4.5 4.5 动态规划动态规划 4.6 4.6 算法策略间的比较算法策略间的比较4.1迭代算法迭代算法4.1.1 4.1.1 递推法递推法4.1.2 4.1.2 倒推法倒推法4.1.3 4.1.3 迭代法解方程迭代法解方程411 递推递推法 【例【例1】兔子繁殖问题】兔子繁殖问题问问题题描描述述：一一对对兔兔子子从从出出生生后后第第三三个个月月开开始始，每每月月生生一一对对小小兔兔子子。小小兔兔子子到到第第三三个个月月
2、又又开开始始生生下下一一代代小小兔兔子子。假假若若兔兔子子只只生生不不死死，一一月月份份抱抱来来一一对对刚刚出出生生的的小小兔兔子子，问问一一年年中中每每个个月月各有多少只兔子。各有多少只兔子。问问题题分分析析：因因一一对对兔兔子子从从出出生生后后第第三三个个月月开开始始每每月月生生一一对对小小兔兔子子，则则每每月月新新下下小小兔兔子子的的对对儿儿数数(用用斜斜体体数数字字表表示示)显显然然由由前前两个月的小兔子的对儿数决定。则繁殖过程如下：两个月的小兔子的对儿数决定。则繁殖过程如下：一月一月二月二月三月三月四月四月五月五月六月六月111+1=22+1=33+2=55+3=8算法算法1 1：
3、main( )main( ) int int i,a=1,b=1; i,a=1,b=1; print(a,b); print(a,b); for(i=1;i for(i=1;i=10;i+)=10;i+) c=a+b; c=a+b; print (c); print (c); a=b; a=b; b=c b=c； 数学建模：数学建模：y y1 1=y=y2 2=1=1，y yn n= =y yn n-1-1+ +y yn n-2-2，n=3n=3，4 4，5 5，。算法算法2 2： 表表4-1 4-1 递推迭代表达式递推迭代表达式1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8
4、 9a b c=a+b a=b+c b=a+c c=a+b a=b+c b=a+c a b c=a+b a=b+c b=a+c c=a+b a=b+c b=a+c 由此归纳出可以用由此归纳出可以用“c=a+b; a=b+c; b=c+a;”c=a+b; a=b+c; b=c+a;”做循环做循环“不变不变式式”。算法算法2 2如下：如下： main( ) main( ) int int i,a=1,b=1; i,a=1,b=1; print(a,b); print(a,b); for(i=1; i for(i=1; i=4;i+)=4;i+) c=a+b; a=b+c; c=a+b; a=b+c
5、; b=c+a; print(a,b,c); b=c+a; print(a,b,c); 算法算法2 2，最后输出的，最后输出的并不是并不是1212项，而是项，而是2+3*42+3*4共共1414项。项。 表表4-2 4-2 递推迭代表达式递推迭代表达式1 21 2 3 4 5 6 7 8 93 4 5 6 7 8 9a a b a=a+b b=a+b a=a+b b=a+b b a=a+b b=a+b a=a+b b=a+b 由此归纳出可以用由此归纳出可以用“a=a+b; b=a+b;”a=a+b; b=a+b;”做循环做循环“不变式不变式”，从而得到以下算法，从而得到以下算法3:3:main
6、( )main( ) int int i,a=1,b=1; i,a=1,b=1; print(a,b); print(a,b); for(i=1; i for(i=1; i=5;i+)=5;i+) a=a+b; a=a+b; b=a+b; print(a,b); b=a+b; print(a,b); 算法算法算法算法3 3 3 3：【例【例2 2】求两个整数的最大公约数。求两个整数的最大公约数。数学建模：数学建模：辗转相除法是根据递推策略设计的。辗转相除法是根据递推策略设计的。不不妨妨设设两两个个整整数数abab且且a a除除以以b b商商x x余余c c；则则a-a-bxbx=c=c，不不难
7、难看看出出a a、b b的的最最大大公公约约数数也也是是c c的的约约数数（一一个个数数能能整整除除等等式式左左边边就就一一定定能能整整除除等等式式的的右右边边），则则a a、b b的的最最大大公公约约数数与与b b、c c的的最最大大公公约约数数相相同同。同同样样方方法法推推出出b b、c c的的最最大大公公约约数数与与，直直到到余余数数为为0 0时时，除除数数即即为为所求的最大公约数。所求的最大公约数。算算法法设设计计：循循环环“不不变变式式”第第一一次次是是求求a a、b b相相除除的的余余数数c c，第第二二次次还还是是求求“a”“b” a”“b” 相相除除的的余余数数，经经a=b,b
8、=ca=b,b=c操操作作，就就实实现现了了第第二二次次还还是是求求“a”“b” a”“b” 相相除除的的余余数数，这这就就找找到到了了循循环环不不变变式式。循循环环在余数在余数c c为为0 0时结束。时结束。算法如下：算法如下：mainmain（）（） int int a, b; a, b; input(a,b); input(a,b); if(b=0) if(b=0) print(“dataerror”);return; else else c = a mod b; c = a mod b; while c0 while c0 a=b; a=b; b=c; b=c; c=a mod b;
9、c=a mod b; print(b); print(b); 4.1.2 4.1.2 倒推法倒推法 所所谓谓倒倒推推法法：是是对对某某些些特特殊殊问问题题所所采采用用的的违违反反通通常常习习惯惯的的，从从 后后向向前前推推解解问问题题的的方方法法。如如下下面面的的例例题题，因因不不同同方方面面的的需需求求而而采采用了倒推策略。用了倒推策略。例例1在在不不知知前前提提条条件件的的情情况况下下，经经过过从从后后向向前前递递推推，从从而而求求解解问问题题。即即由由结结果果倒倒过过来来推推解解它它的的前前提提条条件件。又又如如例例2由由于于存存储储的的要要求求，而而必必须须从从后后向向前前进进行行推推
10、算算。另另外外，在在对对一一些些问问题题进进行行分分析析或或建建立立数数学学模模型型时时，从从前前向向后后分分析析问问题题感感到到比比较较棘棘手手，而而采采用用倒倒推推法（如例法（如例3），则问题容易理解和解决。下面分别看这几个例子：），则问题容易理解和解决。下面分别看这几个例子：【例【例1 1】猴子吃桃问题猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第到第1010天时就只有一个桃子了，求原有多少个桃？天时就只有一个桃子了，求原有多少个桃？数数 学学 模模 型型 ： 每每 天天 的的 桃桃 子子 数数 为为 ： a10=1,
11、 a10=1, a9=(1+a10)*2, a9=(1+a10)*2, a8=(1+a9)*2,a10=1a8=(1+a9)*2,a10=1， 递推公式为：递推公式为：aiai=(1+=(1+aiai+1)*2 I = 9,8,7,61+1)*2 I = 9,8,7,61算法如下算法如下 ： main( )main( ) int int i,s; i,s; s=1; s=1; for (i=9 ;i=1;i=i-1) for (i=9 ;i=1;i=i-1) s=(s+1)*2 s=(s+1)*2 print (s) print (s)； 【例【例2 2】 输出如图输出如图4-14-1的杨辉三
12、角形（限的杨辉三角形（限定用一个一维数组完成）。定用一个一维数组完成）。数学模型：数学模型：上下层规律较明显，中间的数上下层规律较明显，中间的数等于上行左上、右上两数之和。等于上行左上、右上两数之和。问题分析：问题分析：题目中要求用一个一维数组即题目中要求用一个一维数组即完成。数组空间一定是由下标从小到大完成。数组空间一定是由下标从小到大利用的，这样其实杨辉三角形是按下图利用的，这样其实杨辉三角形是按下图4-24-2形式存储的。若求形式存储的。若求n n层，则数组最多层，则数组最多存储存储n n个数据。个数据。 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1
13、 1 2 1 1 3 3 1 1 3 3 1 1 3 3 1 1 3 3 11 4 6 4 11 4 6 4 11 4 6 4 11 4 6 4 1 图图图图4-1 4-1 4-1 4-1 杨辉三角形杨辉三角形杨辉三角形杨辉三角形1 11 11 11 2 11 2 11 3 3 11 3 3 11 14 4 6 6 4 4 1 1图图4-2杨辉三角形存储格式杨辉三角形存储格式算法设计：算法设计：A1 = Ai=1A1 = Ai=1Aj = Aj + Aj-1 j=i-1Aj = Aj + Aj-1 j=i-1，i-2i-2，2 2i i行行 i-1i-1行行 i-1i-1行行算法如下：算法如下
14、：main()intn,i,j,a100;input(n);print(“1”);print(“换行符换行符”);a1=a2=1;print(a1,a2);print(“换行符换行符”);for(i=3;i1，j=j-1)aj=aj+aj-1;for(j=1;j=i;j=j+1)print(aj);print(“换行符换行符”);【例【例3 3】穿越沙漠问题穿越沙漠问题 用一辆吉普车穿越用一辆吉普车穿越10001000公里的沙漠。吉普车的总装油量为公里的沙漠。吉普车的总装油量为500500加仑，耗油率为加仑，耗油率为1 1加仑加仑/ /公里。由于沙漠中没有油库，公里。由于沙漠中没有油库，必须先
15、用这辆车在沙漠中建立临时油库。该吉普车以最少必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。油量。问题分析：问题分析： 1 1）先看一简单问题：有一位探险家用先看一简单问题：有一位探险家用5 5天的时间徒步天的时间徒步 横穿横穿A A、B B两村，两村间是荒无人烟的沙漠，如果一两村，两村间是荒无人烟的沙漠，如果一 个人只能担负个人只能担负3 3天的食物和水，那么这个探险家至天的食物和水，那么这个探险家至 少雇几个人才能顺利通过沙漠。少雇几个人才能顺利通过沙漠。 A A城雇用一人与探险家同
16、带城雇用一人与探险家同带3 3天食物同行一天，然后被雇天食物同行一天，然后被雇 人带一天食物返回，并留一天食物给探险家，这样探险人带一天食物返回，并留一天食物给探险家，这样探险 家正好有家正好有3 3天的食物继续前行，并于第三天打电话雇天的食物继续前行，并于第三天打电话雇B B城城 人带人带3 3天食物出发，第四天会面他们会面，探险家得到一天食物出发，第四天会面他们会面，探险家得到一 天的食物赴天的食物赴B B城。如图城。如图4-34-3主要表示了被雇用二人的行程。主要表示了被雇用二人的行程。 A A B B 图图4-3 4-3 被雇用二人的行程被雇用二人的行程 2 2）贮油点问题要求要以最少
17、的耗油量穿越沙漠，即到达终贮油点问题要求要以最少的耗油量穿越沙漠，即到达终 点时，沙漠中的各临时油库和车的装油量均为点时，沙漠中的各临时油库和车的装油量均为0 0。这样只。这样只 能从终点开始向前倒着推解贮油点和贮油量。能从终点开始向前倒着推解贮油点和贮油量。数数学学模模型型：根根据据耗耗油油量量最最少少目目标标的的分分析析，下下面面从从后后向向前前分分段段讨论。讨论。第一段长度为第一段长度为500500公里且第一个加油点贮油为公里且第一个加油点贮油为500500加仑。加仑。第第二二段段中中为为了了贮贮备备油油，吉吉普普车车在在这这段段的的行行程程必必须须有有往往返返。下下面讨论怎样走效率高：
18、面讨论怎样走效率高：1 1）首先不计方向这段应走奇数次（保证最后向前走）。首先不计方向这段应走奇数次（保证最后向前走）。2 2）每次向前行进时吉普车是满载。每次向前行进时吉普车是满载。3 3）要能贮存够下一加油点的贮油量，路上耗油又最少。要能贮存够下一加油点的贮油量，路上耗油又最少。下下图图是是满满足足以以上上条条件件的的最最佳佳方方案案，此此段段共共走走3 3次次：第第一一、二二次次来来回回耗耗油油2/32/3贮贮油油1/31/3，第第三三次次耗耗油油1/31/3贮贮油油2/32/3，所所以以第第二二个个加加油油点点贮贮油油为为10001000加加仑仑。由由于于每每公公里里耗耗油油率率为为1
19、 1加加仑仑，则此段长度为则此段长度为500/3500/3公里。公里。第第三三段段与与第第二二段段思思路路相相同同。下下图图是是一一最最佳佳方方案案此此段段共共走走5 5次次：第第一一、二二次次来来回回耗耗油油2/52/5贮贮油油3/53/5，第第三三、四四次次来来回回耗耗油油2/52/5贮贮油油3/53/5，第第五五次次耗耗油油1/51/5贮贮油油4/54/5，第第三三个个加加油油点点贮贮油油为为15001500加仑。此段长度为加仑。此段长度为500/5500/5。 500/5500/5公里公里 第二第二 第三第三 终点终点贮油点（贮油点（500500）贮油点（贮油点（10001000）贮油
20、点（贮油点（15001500）图图4-4 4-4 贮油点及贮油量示意贮油点及贮油量示意综上分析综上分析，从终点开始分别间隔，从终点开始分别间隔 500 500，500/3500/3，500/5500/5，500/7500/7，（公里）设立贮油点，直到总距离超过（公里）设立贮油点，直到总距离超过10001000公里。每个贮油点的油量为公里。每个贮油点的油量为500500，10001000，15001500，。 算法设计：算法设计：由模型知道此问题并不必用倒推算法解决（只由模型知道此问题并不必用倒推算法解决（只是分析过程用的是倒推法），只需通过累加算法就能解决。是分析过程用的是倒推法），只需通过累
21、加算法就能解决。变量说明：变量说明：disdis表示距终点的距离，表示距终点的距离，1000- 1000- disdis则表示距起则表示距起点的距离，点的距离，k k表示贮油点从后到前的序号。表示贮油点从后到前的序号。desertdesert（ ） int dis int dis，k k，oil,k;oil,k; dis dis=500;k=1;oil=500;=500;k=1;oil=500; do do print(“print(“storepointstorepoint”,k,”distance”,1000-”,k,”distance”,1000-disdis,”,”oilquantit
22、yoilquantity”,oil)”,oil)； k=k+1; k=k+1; dis dis= =disdis+500/(2*k-1);+500/(2*k-1); oil= 500*k; oil= 500*k; while ( while ( dis dis1000)1000) oil=500*(k-1)+(1000-dis)*(2*k-1); print(“print(“storepointstorepoint”,k,”distance”,0,”,k,”distance”,0,”oilquantityoilquantity”,oil)”,oil)； 4.1.3 4.1.3 迭代法解方程迭代
23、法解方程迭迭代代法法解解 方方 程程的的 实实 质质是是 按按照照下下 列列步步 骤骤构构造造一一个个 序序列列x x0 0,x,x1 1, , ,x xn n, ,来逐步逼近方程来逐步逼近方程f(x)=0f(x)=0的解：的解： 1 1）选选取适当的初取适当的初值值x x0 0； 2 2）确确定定迭迭代代格格式式，即即建建立立迭迭代代关关系系，需需要要将将方方程程f(x)=0f(x)=0改改 写写为为x=(x)x=(x)的等价形式；的等价形式； 构造序列构造序列x0，x1，xn，即先求得即先求得x1=(x0)，再求再求 x2=(x1)，如此反复迭代，就得到一个数列如此反复迭代，就得到一个数列
24、x0， x1，xn，若这个数列收敛，即存在极值，且函数若这个数列收敛，即存在极值，且函数 (x)连续，则很容易得到这个极限值连续，则很容易得到这个极限值x*就是方程就是方程f(x)=0的根。的根。【例【例1 1】迭代法迭代法求方程求方程组组根根算法算法说说明：明：方程方程组组解的初解的初值值X=X=（x0x0，x1x1，xnxn-1-1）, ,迭代关迭代关系系方程方程组为组为：xixi= =gigi(X)(i=0,1,(X)(i=0,1,n-1),w,n-1),w为为解的精度解的精度, ,则则算算法如下：法如下：for(i=0;in;i+)for(i=0;in;i+)xi=xi=初始近似根初始
25、近似根; ;do k=k+1;do k=k+1; for(i=0;in;i yi=xi; for(i=0;in;i yi=xi; for(i=0;in;i+) for(i=0;in;i+) xi=xi=gigi(X);(X); for(i=0;in;i+) c=c+for(i=0;iw and kw and kmaxnmaxn ) )；for(i=0;in;i+)for(i=0;i=1e-4);(x1-x0)=1e-4); return(x1);return(x1); 令令 a0,b0=a,ba0,b0=a,b，c0=(a0+b0)/2c0=(a0+b0)/2，若若f(c0)=0f(c0)=0
26、，则则c0c0为为方方程程 f(x)=0f(x)=0的的 根根 ； 否否 则则 ， 若若 f(a0)f(a0)与与 f(c0)f(c0)异异 号号 ， 即即 f(a0)*f(c0)0f(a0)*f(c0)0，则则令令 a1,b1=a0,c0a1,b1=a0,c0；若若f(b0)f(b0)与与f(c0)f(c0)异异号号，即即 f(b0)*f(c0)0f(b0)*f(c0)0，则则令令 a1,b1=c0,b0a1,b1=c0,b0。依此做下去，依此做下去，当发现当发现f(cn)=0时，或时，或区间区间an,bn足够小，足够小，比如比如|an-bn|0.0001时，就认为找到了方程的根。时，就认为
27、找到了方程的根。用二分法求一元非线性方程用二分法求一元非线性方程f(x)=x3/2+2x2-8=0（其中其中表示幂运算）在区间表示幂运算）在区间0，2上的近似实根上的近似实根r，精确到精确到0.0001.算算法如下：法如下：图图4-6 4-6 二分法二分法求求解解方程方程示意示意【例【例【例【例3 3 3 3】二分法二分法二分法二分法求求求求解方程解方程解方程解方程f(x)=0f(x)=0f(x)=0f(x)=0根根根根 用二用二用二用二分法分法分法分法求求求求解方程解方程解方程解方程f(x)=0f(x)=0f(x)=0f(x)=0根根根根的前提条件是：的前提条件是：的前提条件是：的前提条件是
28、：f(x)f(x)f(x)f(x)在在在在求解的求解的求解的求解的区区区区间间间间 a,ba,ba,ba,b上上上上是是是是连续连续连续连续的，的，的，的，且且且且已知已知已知已知f(a)f(a)f(a)f(a)与与与与f(b)f(b)f(b)f(b)异号，即异号，即异号，即异号，即 f(a)*f(b)0f(a)*f(b)0f(a)*f(b)0f(a)*f(b)0。main( )main( ) float x,x1=0,x2=2,f1,f2,f; float x,x1=0,x2=2,f1,f2,f; print(“input a,b (f(a)*f(b)0)”); input(a,b); pr
29、int(“input a,b (f(a)*f(b)0) if(f1*f20) printf printf(No root); return;(No root); return; do do x=(x1+x2)/2; x=(x1+x2)/2; f=x*x*x/2+2*x*x-8; f=x*x*x/2+2*x*x-8; if(f=0) break; if(f=0) break; if(f1*f0.0) x1=x; f1=x1*x1*x1/2+2*x1*x1-8; if(f1*f0.0) x1=x; f1=x1*x1*x1/2+2*x1*x1-8; else x2=x; else x2=x;whil
30、e(while(fabsfabs(f)=1e-4);(f)=1e-4);print(root=,x); print(root=,x); 4.2蛮力法蛮力法4.2.1 4.2.1 枚举法枚举法4.2.2 4.2.2 其它范例其它范例 蛮力法蛮力法是基于计算机运算速度快这一特性，在解决问题时采取是基于计算机运算速度快这一特性，在解决问题时采取的一种的一种“ “懒惰懒惰” ”的策略。这种策略不经过（或者说是经过很少的）的策略。这种策略不经过（或者说是经过很少的）思考，把问题的所有情况或所有过程交给计算机去一一尝试，从思考，把问题的所有情况或所有过程交给计算机去一一尝试，从中找出问题的解。蛮力策略的应
31、用很广，具体表现形式各异，数中找出问题的解。蛮力策略的应用很广，具体表现形式各异，数据结构课程中学习的：选择排序、冒泡排序、插入排序、顺序查据结构课程中学习的：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等，都是蛮力策略具体应用。比较常用还找、朴素的字符串匹配等，都是蛮力策略具体应用。比较常用还有有枚枚举举法法、盲目搜索算法等，本节介绍、盲目搜索算法等，本节介绍枚枚举举法法和其它一些小的范和其它一些小的范例，第五章介绍盲目搜索算法。例，第五章介绍盲目搜索算法。4 42 21 1 枚举法枚举法枚枚举举（enumerate）法法（穷穷举举法法）是是蛮蛮力力策策略略的的一一种种表表现现形
32、形式式，也也是是一一种种使使用用非非常常普普遍遍的的思思维维方方法法。它它是是根根据据问问题题中中的的条条件件将将可可能能的的情情况况一一一一列列举举出出来来，逐逐一一尝尝试试从从中中找找出出满满足足问问题题条条件件的的解解。但但有有时时一一一一列列举举出出的的情情况况数数目目很很大大，如如果果超超过过了了我我们们所所能能忍忍受受的的范范围围，则则需需要要进进一一步步考考虑虑，排排除除一一些些明明显显不不合合理理的的情情况况，尽尽可可能能减减少少问问题题可能解的列举数目。可能解的列举数目。用枚举法解决问题，通常可以从两个方面进行算法设计：用枚举法解决问题，通常可以从两个方面进行算法设计：1）找
33、出枚举范围：分析问题所涉及的各种情况。找出枚举范围：分析问题所涉及的各种情况。 2 2）找找出出约约束束条条件件：分分析析问问题题的的解解需需要要满满足足的的条条件件，并并用用逻逻辑辑表达式表示。表达式表示。【例【例1 1】百百钱钱百百鸡问题鸡问题。中国古代数学家。中国古代数学家张张丘建在他的算丘建在他的算经经中提出了著名的中提出了著名的“百百钱钱百百鸡问题鸡问题”：鸡鸡翁一，翁一，值钱值钱五；五；鸡鸡母一，母一，值钱值钱三；三；鸡雏鸡雏三，三，值钱值钱一；百一；百钱买钱买百百鸡鸡，翁、母、，翁、母、雏雏各几何各几何? ?算法设计算法设计1：通过对问题的理解，读者可能会想到列出两个三元一次方程
34、，通过对问题的理解，读者可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用但这里我们要用“懒惰懒惰”的枚举策略进行算法设计：的枚举策略进行算法设计：设设x，y，z分别为公鸡、母鸡、小鸡的数量。分别为公鸡、母鸡、小鸡的数量。 尝尝试试范范围围：由由题题意意给给定定共共100钱钱要要买买百百鸡鸡，若若全全买买公公鸡鸡最最多多买买100/5=100/5=20只只，显显然然x的的取取值值范范围围120之之间间；同同理理，y的的取取值值范范围在围在133之间，之间，z z的取值范围的取值范围在在1
35、1001100之间之间。 约束条件：约束条件： x+y+z=100 x+y+z=100 且且 5* 5*x+3*y+z/3=100x+3*y+z/3=100 算法算法1如下：如下： main( )main( ) int int x,y,z; x,y,z;for(x=1;x=20;x=x+1)for(x=1;x=20;x=x+1) for(y=1;y=34;y=y+1) for(y=1;y=34;y=y+1) for(z=1;z=100;z=z+1) for(z=1;z=100;z=z+1) if(100=x+y+z and 100=5*x+3*y+z/3) if(100=x+y+z and 1
36、00=5*x+3*y+z/3) print(the cock number is,x) print(the cock number is,x)； print(the hen number is, y) print(the hen number is, y)；print(the chick number is z);print(the chick number is z); 算算法法分分析析：以以上上算算法法需需要要枚枚举举尝尝试试20*34*100=68000次次。算法的效率显然太低算法的效率显然太低算法设计算法设计2：在在公公鸡鸡（x x）、母母鸡鸡（y y）的的数数量量确确定定后后，小小鸡
37、鸡的的数数量量z就就固固定为定为100-x-y，无需再进行枚举了无需再进行枚举了此时此时约约束条件只有一个：束条件只有一个： 5*x+3*y+z/3=100算法算法2如下：如下： main( )main( ) int int x,y,z; x,y,z;for(x=1;x=20;x=x+1) for(x=1;x=20;x=x+1) for(y=1;y=33;y=y+1) for(y=1;y=33;y=y+1) z=100-x-y; z=100-x-y; if(z mod 3=0 and if(z mod 3=0 and 5*x+3*y+z/3=100)5*x+3*y+z/3=100)print(
38、the cock number is,x)print(the cock number is,x)； print(the hen number is, y) print(the hen number is, y)；print(the chick number is z);print(the chick number is z); 算法分析：算法分析：以上算法只需要枚举尝试以上算法只需要枚举尝试20*33=660次。实现时约次。实现时约束条件又限定束条件又限定Z能被能被3整除时，才会判断整除时，才会判断“5*5*x+3*y+z/3=100”x+3*y+z/3=100”。这样这样省去了省去了z z不
39、整除不整除3 3时时的算的算术计术计算和条件算和条件判断，判断，进进一步提高了算一步提高了算法的效率。法的效率。 【例【例2 2】解数字迷：】解数字迷： A B C A BA B C A B A A D D D D D D D D D D D D算法设计算法设计1 1：按乘法枚举按乘法枚举1)1)枚举范围为：枚举范围为： A A：3939（A=1A=1，2 2时积不会得到六位数）时积不会得到六位数）, ,B B：09,09, C C：09 09 六位数表示为六位数表示为A*10000+B*1000+C*100+A*10+BA*10000+B*1000+C*100+A*10+B， 共尝试共尝试8
40、00800次。次。2)2)约束条件为：约束条件为： 每次尝试，先求六位数与每次尝试，先求六位数与A A的积，再测试积的各位是否相的积，再测试积的各位是否相 同，若相同则找到了问题的解。同，若相同则找到了问题的解。 测试积的各位是否相同比较简单的方法是，从低位开始，测试积的各位是否相同比较简单的方法是，从低位开始， 每次都取数据的个位，然后整除每次都取数据的个位，然后整除1010，使高位的数字不断变，使高位的数字不断变 成个位，并逐一比较。成个位，并逐一比较。算法算法1 1如下：如下：main（）intA,B,C,D,E,E1,F,G1,G2,i;for(A=3;A=9;A+)for(B=0;B
41、=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(G1G2)break;if(i=6)print(F，”*”，A，”=”，E);算法说明算法说明算法说明算法说明1 1 1 1：算法中对枚举出的每一个五位数与算法中对枚举出的每一个五位数与A A相乘，结果相乘，结果存储在变量存储在变量E E中。然后，测试得到的六位数中。然后，测试得到的六位数E E是否各个位的数是否各个位的数字都相同。鉴于要输出结果，所以不要改变计算
42、结果，而另字都相同。鉴于要输出结果，所以不要改变计算结果，而另设变量设变量E1E1，用于测试运算。用于测试运算。算法分析算法分析算法分析算法分析1 1 1 1：以上算法的尝试范围是以上算法的尝试范围是以上算法的尝试范围是以上算法的尝试范围是A A A A：3 3 3 39 9 9 9，B B B B：0 0 0 09 9 9 9， C C C C：0 0 0 09 9 9 9 。共尝试共尝试共尝试共尝试800800800800次，每次，不是一个好的算法。次，每次，不是一个好的算法。次，每次，不是一个好的算法。次，每次，不是一个好的算法。算法设计算法设计2 2：将算式变形为除法：将算式变形为除法
43、：DDDDDD/A=ABCABDDDDDD/A=ABCAB。此时此时只需枚举只需枚举A A：39 D39 D：1919，共尝试共尝试7*9=637*9=63次。每次次。每次尝试，测试商的万位、十位与除数是否相同，千位与个位尝试，测试商的万位、十位与除数是否相同，千位与个位是否相同，都相同时为解。是否相同，都相同时为解。算法算法2 2如下如下: :mainmain（）（） intint A,B,C,D,E,F; A,B,C,D,E,F; for(A=3;A=9;A+) for(A=3;A=9;A+) for(D=1;D=9;D+) for(D=1;D=9;D+) E = E = D*100000
44、+D*10000+D*1000+D*100+D*10+D;D*100000+D*10000+D*1000+D*100+D*10+D; if(E mod A=0) F=EA; if(E mod A=0) F=EA; if(F10000=A and (F mod 100)10=A) if(F10000=A and (F mod 100)10=A) if(F1000=F mod 10) if(F1000=F mod 10) print( F print( F，”* *”，A A，”= =”，E);E); 蛮力法的表现形式非常多，如第三章蛮力法的表现形式非常多，如第三章3.2.4例题、例题、3.2.5
45、例例1及本章下一节及本章下一节4.3.3例例4的算法的算法1等。本节将通过蛮力策略，用等。本节将通过蛮力策略，用算法模拟问题中所描述的全部过程和全部状态，来找出问题的解，算法模拟问题中所描述的全部过程和全部状态，来找出问题的解，并与经过数学建模后的算法进行效率上的比较。并与经过数学建模后的算法进行效率上的比较。4 42 22 2 其它范例其它范例【例【例3 3】狱吏问题狱吏问题 某国王对囚犯进行大赦，让一狱吏某国王对囚犯进行大赦，让一狱吏n n次通过一排锁着的次通过一排锁着的n n间牢房，每通过一次，按所定规则转动间牢房，每通过一次，按所定规则转动n n间牢房中的某些门间牢房中的某些门锁锁,
46、, 每转动一次每转动一次, , 原来锁着的被打开原来锁着的被打开, , 原来打开的被锁上；原来打开的被锁上；通过通过n n次后，门锁开着的，牢房中的犯人放出，否则犯人不次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。得获释。 转动门锁的规则是这样的，第一次通过牢房，要转动每转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第开始转动，每隔一间转动一次；第k k次通过牢房，从第次通过牢房，从第k k间开间开始转动，每隔始转动，每隔k-1 k-1 间转动一次；问通
47、过间转动一次；问通过n n次后，那些牢房的次后，那些牢房的锁仍然是打开的？锁仍然是打开的？算法设计算法设计1 1：1 1）用用n n个空间的一维数组个空间的一维数组an,an,每个元素每个元素记录一个锁的状记录一个锁的状态，态，1 1为为被锁上，被锁上，0 0为被打开。为被打开。2 2）用数学运算方便模拟开关锁的技巧，对）用数学运算方便模拟开关锁的技巧，对i i号锁的一次开号锁的一次开 关锁可以转化为算术运算：关锁可以转化为算术运算：ai=1-aiai=1-ai。3 3）第一次转动的是第一次转动的是1 1，2 2，3 3，n n号牢房；号牢房； 第二次转动的是第二次转动的是2 2，4 4，6
48、6，号牢房；号牢房； 第三次转动的是第三次转动的是3 3，6 6，9 9，号牢房；号牢房； 第第i i次次转转动动的的是是i i，2i2i，3i3i，4i4i，号号牢牢房房，是是起起点为点为i i，公差为公差为i i的等差数列。的等差数列。 4 4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关）不做其它的优化，用蛮力法通过循环模拟狱吏的开关 锁过程，最后当第锁过程，最后当第i号牢房对应的数组元素号牢房对应的数组元素aiai为为0 0时，时， 该牢房的囚犯得到大赦。算法该牢房的囚犯得到大赦。算法1如下：如下：main1( )main1( ) intint *a,i,j,n; *a,i,j,n;
49、 input(n); input(n); a= a=calloccalloc(n+1,(n+1,sizeofsizeof( (intint);); for (i=1; i=n;i+) for (i=1; i=n;i+) ai=1; ai=1; for (i=1; i=n;i+) for (i=1; i=n;i+) for (j=i; j=n;j=j+i) for (j=i; j=n;j=j+i) ai=1-ai;ai=1-ai; for (i=1; i=n;i+) for (i=1; i=n;i+) if (ai=0) print(i,”is free.”); if (ai=0) print(
50、i,”is free.”); 算算法法分分析析：以以一一次次开开关关锁锁计计算算，算算法法的的时时间间复复杂杂度度为为n(1+1/2+1/3+1/n)=O(n(1+1/2+1/3+1/n)=O(nlognnlogn) )。问题分析：问题分析：转动门锁的规则可以有另一种理解，第一次转动转动门锁的规则可以有另一种理解，第一次转动的是编号为的是编号为1 1的倍数的牢房；第二次转动的是编号为的倍数的牢房；第二次转动的是编号为2 2的倍的倍数的牢房；第三次转动的是编号为数的牢房；第三次转动的是编号为3 3的倍数的牢房；的倍数的牢房；则则狱吏问题是一个关于因子个数的狱吏问题是一个关于因子个数的问题。令问题
51、。令d(n)d(n)为自然数为自然数n n的因子个数，这里不计重复的因子，如的因子个数，这里不计重复的因子，如4 4的因子为的因子为1 1，2 2，4 4共三个因子，而非共三个因子，而非1 1，2 2，2 2，4 4。则。则d(n)d(n)有的为奇数，有有的为奇数，有的为偶数，见下表的为偶数，见下表: : 表表4-3 4-3 编号与因数个数的关系编号与因数个数的关系 n 1 2 3 4 5 6 7 8 9 10 n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 11 12 13 14 15 16 d(n) 1 2 2 3 2 4 2 4 3 4 2 6 2 4
52、4 d(n) 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 5 数学模型数学模型1 1：上表中的上表中的d(n)d(n)有的为奇数，有的为偶数，有的为奇数，有的为偶数，由于由于牢房的门开始是关着的，这样编号为牢房的门开始是关着的，这样编号为i i的牢房，所含的牢房，所含11i i之间的不重复因子个数为奇数时，牢房最后是打开的，之间的不重复因子个数为奇数时，牢房最后是打开的，反之，牢房最后是关闭的。反之，牢房最后是关闭的。算法设计算法设计2:2:1 1）算算法法应应该该是是求求出出每每个个牢牢房房编编号号的的不不重重复复的的因因子子个个数数，当当它它为奇数时，这里边的囚犯得到大
53、赦。为奇数时，这里边的囚犯得到大赦。2 2）一一个个数数的的因因子子是是没没有有规规律律的的，只只能能从从11n n枚枚举举尝尝试试。算算法法2 2如下：如下：main2( )main2( ) intint s,i,j,n; s,i,j,n; input(n); input(n); for (i=1; i=n;i+) for (i=1; i=n;i+) s=1; s=1; for (j=2; j=i;j=j+) for (j=2; j=i;j=j+) if if （i mod j=0i mod j=0） s=s+1; s=s+1; if if （s mod 2 =1s mod 2 =1） pr
54、int(i,”is free.”); print(i,”is free.”); 算法分析：算法分析： 狱吏开关锁的主要操作是狱吏开关锁的主要操作是ai=1- ai;ai=1- ai;共执行了共执行了n*(1+1/2+1/3+1/n)n*(1+1/2+1/3+1/n)次，时间近似为复杂度为次，时间近似为复杂度为O（nlogn）。）。使用了使用了n n个空间的一维数组。算法个空间的一维数组。算法2 2没有使用辅助没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其空间，但由于求一个编号的因子个数也很复杂，其主要操主要操作是判断作是判断i mod ji mod j是否为是否为0 0，共执行了，共
55、执行了n*(1+2+3+n)n*(1+2+3+n)次，时间复杂度为次，时间复杂度为O O（n n2 2）。）。数数学学模模型型2 2：仔仔细细观观察察表表4-34-3，发发现现当当且且仅仅当当n n为为完完全全平平方方数数时时, ,d(n)d(n)为为奇奇数数；这这是是因因为为n n的的因因子子是是成成对对出出现现的的, ,也也即即当当n=a*bn=a*b且且abab时时，必必有有两两个个因因子子a a，b; b; 只只有有n n为为完完全全平平方方数数，也也即即当当n=an=a2 2时时, , 才才会会出出现现d(n)d(n)为奇数的情形。为奇数的情形。算算法法设设计计3 3：这这时时只只需
56、需要要找找出出小小于于n n的的平平方方数数即即可可。算法算法3 3如下：如下：main3( )main3( ) intint s,i,j,n; s,i,j,n; input(n); input(n);for (i=1;i=n;i+)for (i=1;i=n;i+)ifif（i*i=ni*i=n） print(i,”is free. print(i,”is free.”);); else else break; break; 由由此此算算法法我我们们应应当当注注意意：在在对对运运行行效效率率要要求求较较高高的的大大规规模模的的数数据据处处理理问问题题时时，必必须须多多动动脑脑筋筋找找出出效效率
57、率较较高高的的数数学学模模型型及及其其对应的算法。对应的算法。4.3分而治之算法分而治之算法4.3.1 4.3.1 分治算法框架分治算法框架4.3.2 4.3.2 二分法二分法4.3.3 4.3.3 二分法变异二分法变异4.3.4 4.3.4 其它分治方法其它分治方法431分治算法框架分治算法框架1算法算法设计设计思想思想分分治治法法求求解解问问题题的的过过程程是是，将将整整个个问问题题分分解解成成若若干干个个小小问问题题后后分分而而治治之之。如如果果分分解解得得到到的的子子问问题题相相对对来来说说还还太太大大，则则可可反反复复使使用用分分治治策策略略将将这这些些子子问问题题分分成成更更小小的
58、的同同类类型型子子问问题题，直直至至产产生生出出方方便便求求解解的的子子问问题题，必必要要时时逐逐步步合合并并这这些些子子问问题题的的解解，从从而而得得到到问问题题的解。的解。分治法的基本步分治法的基本步骤骤在每一在每一层递归层递归上都有三个步上都有三个步骤骤：1）分解：将原问题分解为若干个规模较小，相互独立，与原问）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；题形式相同的子问题；2）解决：若子问题规模较小而容易被解决则直接解，否则再）解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；继续分解为更小的子问题，直到容易解决；3）合
59、并：将已求解的各个子问题的解，逐步合并为原问题的）合并：将已求解的各个子问题的解，逐步合并为原问题的解。解。有有时问题时问题分解后，不必求解所有的子分解后，不必求解所有的子问题问题，也就不必作第三步，也就不必作第三步的操作。比如折半的操作。比如折半查查找，在判找，在判别别出出问题问题的解在某一个子的解在某一个子问题问题中中后，其它的子后，其它的子问题问题就不必求解了，就不必求解了，问题问题的解就是最后（最小）的解就是最后（最小）的子的子问题问题的解。分治法的的解。分治法的这类应这类应用，又称用，又称为为“减治法减治法”。 多数问题需要所有子问题的解，并由子问题的解，使用恰多数问题需要所有子问题
60、的解，并由子问题的解，使用恰当的方法合并成为整个问题的解，比如合并排序，就是不断将当的方法合并成为整个问题的解，比如合并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。子问题中已排好序的解合并成较大规模的有序子集。2适合用分治法策略的问题适合用分治法策略的问题当求解一个输入规模为当求解一个输入规模为n且取值又相当大的问题时，用蛮力策且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。治法来提高解决问题的效率。1）能将这能将这n个数据分解成个数据分解成k个不同子集合
61、，且得到个不同子集合，且得到k个子集合个子集合是可以独立求解的子问题，其中是可以独立求解的子问题，其中1kn；2）分解所得到的子问题与原问题具有相似的结构，便于利分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；用递归或循环机制；在求出这些子问题的解之后，就可以推解出原问题的解；在求出这些子问题的解之后，就可以推解出原问题的解；分治法的一般的算法分治法的一般的算法设计设计模式如下：模式如下：Divide-and-Conquer(Divide-and-Conquer(int int n) /n n) /n为问题规为问题规模模/ / if if （nn0nn0） /n0 /n0 为
62、为可解子可解子问题问题的的规规模模/ / 解子解子问题问题； return(return(子子问题问题的解的解) )； for for （i=1 ;i=k;i+i=1 ;i=k;i+） / /分解分解为较为较小子小子问题问题p1,p2,p1,p2,pkpk/ / yi yi=Divide-and-Conquer(|Pi|); /=Divide-and-Conquer(|Pi|); /递归递归解决解决PiPi/ / T =MERGE(y1,y2,.,T =MERGE(y1,y2,.,ykyk); /); /合并子合并子问题问题/ / return(T); return(T); 其中其中| |P|
63、P|表示表示问题问题P P的的规规模；模；n0n0为为一一阈值阈值，表示当，表示当问题问题P P的的规规模不超模不超过过n0n0时时，问题问题已容易直接解出，不必再已容易直接解出，不必再继续继续分解。算法分解。算法MERGE(y1,y2,.,MERGE(y1,y2,.,ykyk) )是是该该分治法中的合并子算法，用于将分治法中的合并子算法，用于将P P的子的子问题问题P1 ,P2 ,.,P1 ,P2 ,.,PkPk的相的相应应的解的解y1,y2,.,y1,y2,.,ykyk合并合并为为P P的解。在的解。在一些一些问题问题中不需要中不需要这这一步。如析半一步。如析半查查找、找、4 43 32
64、2中的例中的例1 1、例、例2 2等。等。432二分二分法法 不不同同于于现现实实中中对对问问题题（或或工工作作）的的分分解解，可可能能会会考考虑虑问问题题（或或工工作作）的的重重点点、难难点点、承承担担人人员员的的能能力力等等来来进进行行问问题题的的分分解解和和分分配配。在在算算法法设设计计中中每每次次一一个个问问题题分分解解成成的的子子问问题题个个数数一一般般是是固固定定的的，每每个个子子问问题题的的规规模模也也是是平平均均分分配配的的。当当每每次次都都将将问问题题分分解解为为原原问问题题规规模模的的一一半半时时，称称为为二二分分法法。二二分分法法是是分分治治法法较较常常用用的的分分解解策
65、策略略，数数据据结结构构课课程程中中的的折折半半查查找找、归归并并排排序序等算法都是采用此策略实现的。等算法都是采用此策略实现的。【例【例1 1】金块问题：】金块问题： 老板有一袋金块老板有一袋金块( (共共n n块块) )，最优秀的雇员得最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。金块。算法设计算法设计1 1：比较简单的方法是逐个的进行比较查找。先拿两块比较简单的方法是逐个的进行比较查找。先拿两块比较重
66、量，留下重的一个与下一块比较，直到全部比较完毕，比较重量，留下重的一个与下一块比较，直到全部比较完毕，就找到了最重的金子。算法类似于一趟选择排序，算法如下：就找到了最重的金子。算法类似于一趟选择排序，算法如下： maxminmaxmin( float a,( float a,intint n) n) max=min=a1; max=min=a1; for(i=2 i=n i+ ) for(i=2 i=n i+ ) if(max ai) max=ai; if(max ai) else if(min ai) min=ai; min=ai; 算法分析算法分析算法分析算法分析1 1：算法中需要算法中需
67、要算法中需要算法中需要n-1n-1次比较得到次比较得到次比较得到次比较得到maxmax。最好的情况是金块是最好的情况是金块是最好的情况是金块是最好的情况是金块是由小到大取出的，不需要进行与由小到大取出的，不需要进行与由小到大取出的，不需要进行与由小到大取出的，不需要进行与minmin的比较，共进行的比较，共进行的比较，共进行的比较，共进行n-1n-1次比较。次比较。次比较。次比较。最坏的情况是金块是由大到小取出的，需要再经过最坏的情况是金块是由大到小取出的，需要再经过最坏的情况是金块是由大到小取出的，需要再经过最坏的情况是金块是由大到小取出的，需要再经过n-1n-1次比较得到次比较得到次比较得
68、到次比较得到min,min,共进行共进行共进行共进行2*2*n-2n-2次比较。至于在平均情况下，次比较。至于在平均情况下，次比较。至于在平均情况下，次比较。至于在平均情况下，A(i)A(i)将有一半的时将有一半的时将有一半的时将有一半的时间比间比间比间比maxmax大，因此平均比较数是大，因此平均比较数是大，因此平均比较数是大，因此平均比较数是3(3(n1)/2n1)/2。 算法设计算法设计算法设计算法设计2:2:2:2:问题可以简化为：在含问题可以简化为：在含问题可以简化为：在含问题可以简化为：在含n n n n（n n n n是是是是2 2 2 2的幂（的幂（的幂（的幂（n=2n=2n=
69、2n=2）个元个元个元个元素的集合中寻找极大元和极小元。用分治法（二分法）可以用较素的集合中寻找极大元和极小元。用分治法（二分法）可以用较素的集合中寻找极大元和极小元。用分治法（二分法）可以用较素的集合中寻找极大元和极小元。用分治法（二分法）可以用较少比较次数地解决上述问题：少比较次数地解决上述问题：少比较次数地解决上述问题：少比较次数地解决上述问题：1 1 1 1） 将数据等分为两组（两组数据可能差将数据等分为两组（两组数据可能差将数据等分为两组（两组数据可能差将数据等分为两组（两组数据可能差1 1 1 1），目的是分别选取），目的是分别选取），目的是分别选取），目的是分别选取 其中的最大（
70、小）值。其中的最大（小）值。其中的最大（小）值。其中的最大（小）值。2 2 2 2） 递归分解直到每组元素的个数递归分解直到每组元素的个数递归分解直到每组元素的个数递归分解直到每组元素的个数2222，可简单地找到最大（小），可简单地找到最大（小），可简单地找到最大（小），可简单地找到最大（小） 值。值。值。值。3 3 3 3） 回溯时将分解的两组解大者取大，小者取小，合并为当前问回溯时将分解的两组解大者取大，小者取小，合并为当前问回溯时将分解的两组解大者取大，小者取小，合并为当前问回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。题的解。题的解。题的解。算法算法算法算法2 2 2 2
71、 递归求取最大和最小元素递归求取最大和最小元素递归求取最大和最小元素递归求取最大和最小元素 float an;float an;maxmin （intint i, i, int int j ,float & j ,float &fmaxfmax, float , float & &fminfmin） intint mid; float mid; float lmaxlmax, , lmin lmin, , rmax rmax, , rmin rmin; ;if (i=j) if (i=j) fmaxfmax= ai; = ai; fminfmin=ai;=ai;else if (i=j-1)e
72、lse if (i=j-1) if(aiaj) if(ai rmaxrmax) ) fmaxfmax= =lmaxlmax; ; else else fmaxfmax= =rmaxrmax; ; if( if(lminlmin rminrmin) ) fmin fmin= =rminrmin; ; else else fmin fmin= =lminlmin; ; 算法分析：算法分析：MAXMINMAXMIN需要的元素比较数是多少呢？如果用需要的元素比较数是多少呢？如果用T(n)T(n)表示这个数，则所导出的递归关系式是表示这个数，则所导出的递归关系式是: :当当n n是是2 2的幂时，即对于
73、这个某个正整数的幂时，即对于这个某个正整数k，n=2k，有有可以证明，任何以元素可以证明，任何以元素可以证明，任何以元素可以证明，任何以元素比较为基础的找最大和比较为基础的找最大和比较为基础的找最大和比较为基础的找最大和最小元素的算法，其元最小元素的算法，其元最小元素的算法，其元最小元素的算法，其元素比较下界均为素比较下界均为素比较下界均为素比较下界均为 次。次。次。次。因此，过程因此，过程因此，过程因此，过程MAXMINMAXMINMAXMINMAXMIN在这在这在这在这种意义上是最优的。种意义上是最优的。种意义上是最优的。种意义上是最优的。【例【例2 2】残缺棋盘残缺棋盘残缺棋盘是一个有残
74、缺棋盘是一个有2 2k k22k k （k1k1）个个方格的棋盘，其中恰有方格的棋盘，其中恰有一个方格残缺。图一个方格残缺。图4-7给出给出k=1时各种可能的残缺棋盘，其时各种可能的残缺棋盘，其中残缺的方格用阴影表示。中残缺的方格用阴影表示。 号 号 号 号图4-7 四种三格板这这样样的的棋棋盘盘我我们们称称作作“三三格格板板”，残残缺缺棋棋盘盘问问题题就就是是要要用用这这四四种三格板覆盖更大的残缺棋种三格板覆盖更大的残缺棋盘盘。在此覆盖中要求：。在此覆盖中要求：1 1）两个三格板不能重叠）两个三格板不能重叠2 2）三格板不能覆盖残缺方格，但必）三格板不能覆盖残缺方格，但必须须覆盖其他所有的方
75、格覆盖其他所有的方格在这种限制条件下，所需要的三格板总数为在这种限制条件下，所需要的三格板总数为(2k2k-1)/3。算法算法设计设计1 1：下面用分而治之方法解决残缺棋下面用分而治之方法解决残缺棋盘问题盘问题。1 1）问题问题分解分解过过程如下：程如下：以以k=2时时的的问问题题为为例例，用用二二分分法法进进行行分分解解，得得到到的的是是如如下下图图4-8，用用双双线线划划分分的的四四个个k=1的的棋棋盘盘。但但要要注注意意这这四四个个棋棋盘盘，并并不不都都是是与与原原问问题题相相似似且且独独立立的的子子问问题题。因因为为当当如如图图4-8中中的的残残缺缺方方格格在在左左上上部部时时，第第1
76、个个子子问问题题与与原原问问题题相相似似，而而右右上上角角、左左下下角角和和右右下下角角三三个个子子棋棋盘盘（也也就就是是图图中中标标识识为为2、3、4号号子子棋棋盘盘），并并不不是是原原问问题题的的相相似似子子问问题题，自自然然也也就就不不能能独独立立求求解解了了。当当使使用用一一个个号号三三格格板板（图图中中阴阴影影）覆覆盖盖2、3、4号号三三个个子子棋棋盘盘的的各各一一个个方方格格后后，如如4-8右右图图所所示示，我我们们把把覆覆盖盖后后的的方方格格，也也看看作作是是残残缺缺方方格格（称称为为“伪伪”残残缺缺方方格格），这这时时的的2、3、4号号子子问问题题就就是是独独立立且且与与原原问
77、问题题相相似似的的子子问问题题了。了。 图图图图4-8 4-8 4-8 4-8 一个一个一个一个4*44*44*44*4的残缺棋的残缺棋的残缺棋的残缺棋盘盘盘盘从从以以上上例例子子还还可可以以发发现现，当当残残缺缺方方格格在在第第1个个子子棋棋盘盘，用用号号三三格格板板覆覆盖盖其其余余三三个个子子棋棋盘盘的的交交界界方方格格，可可以以使使另另外外三三个个子子棋棋盘盘转转化化为为独独立立子子问问题题；同同样样地地（如如下下图图4-9所所示示），当当残残缺缺方方格格在在第第2个个子子棋棋盘盘时时，则则首首先先用用号号三三格格板板进进行行棋棋盘盘覆覆盖盖，当当残残缺缺方方格格在在第第3个个子子棋棋盘
78、盘时时，则则首首先先用用号号三三格格板板进进行行棋棋盘盘覆覆盖盖，当当残残缺缺方方格格在在第第4个个子子棋棋盘盘时时，则则首首先先用用号号三三格格板板进进行行棋棋盘盘覆盖，覆盖，这样这样就使另外三个子棋就使另外三个子棋盘转盘转化化为为独立子独立子问题问题。如下图如下图4-94-9：同样地同样地k=1，2，3，4都是如此，都是如此，k=1为停止条件。为停止条件。 图图4-9 4-9 其它其它4*44*4的残缺棋的残缺棋盘盘2 2）棋）棋盘盘的的识别识别 棋棋盘盘的的规规模是一个必要的信息，有了模是一个必要的信息，有了这这个信息，只要知道其左上个信息，只要知道其左上角的左上角方格所在行、列就可以唯
79、一确定一个棋角的左上角方格所在行、列就可以唯一确定一个棋盘盘了，残缺了，残缺方格或方格或“伪伪”残缺方格直接用行、列号残缺方格直接用行、列号记录记录。 tr tr 棋棋盘盘中左上角方格所在行。中左上角方格所在行。 tc tc 棋棋盘盘中左上角方格所在列。中左上角方格所在列。 dr dr 残缺方残缺方块块所在行。所在行。 dl dl 残缺方残缺方块块所在列。所在列。 size size 棋棋盘盘的行数或列数。的行数或列数。数据数据结结构构设计设计：用二用二维维数数组组board board ，模模拟拟棋棋盘盘。覆盖。覆盖残缺棋残缺棋盘盘所需要的三格板数目所需要的三格板数目为为：( ( sizes
80、ize2 2 -1 ) / 3 -1 ) / 3将将这这些三格板些三格板编编号号为为1 1到到( ( s i z es i z e2 2-1 ) / 3-1 ) / 3。则则将残缺棋将残缺棋盘盘三格板三格板编编号的存号的存储储在数在数组组board board 的的对应对应位置中，位置中，这这样输样输出数出数组组内容就是内容就是问题问题的解。的解。结结合合图图4-94-9，理解算法。，理解算法。算法如下：算法如下： intamount=0;main（）（）intsize=1,x,y;input(k);for(i=1;i=k;i+)size=size*2;print(“inputincomple
81、tepane”);input(x,y);Cover(0,0,x,y,size);图图4-9一个一个4*4的残缺棋盘及其解的残缺棋盘及其解Cover(inttr,inttc,intdr,intdc,intsize)if(size2)return;intt=amount+,/所使用的三格板的数目所使用的三格板的数目s=size/2;/子子问题问题棋棋盘盘大小大小if(drtr+s&dctc+s)/残缺方格位于左上棋残缺方格位于左上棋盘盘Cover(tr,tc,dr,dc,s);Boardtr+s-1tc+s=t;/覆盖号三格板覆盖号三格板Boardtr+stc+s-1=t;Boardtr+stc+
82、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);elseif(dr=tc+s)/残缺方格位于右上象限残缺方格位于右上象限Cover(tr,tc+s,dr,dc,s);Boardtr+s-1tc+s-1=t;/覆盖号三格板覆盖号三格板Boardtr+stc+s-1=t;Boardtr+stc+s=t;Cover(tr,tc,tr+s-1,tc+s-1,s);/覆盖其余部分覆盖其余部分Cover(tr+s,tc,tr+s,tc+s-1,s)
83、;Cover(tr+s,tc+s,tr+s,tc+s,s);elseif(dr=tr+s&dc=tr+s&dc=tc+s)/残缺方格位于右下象限残缺方格位于右下象限Cover(tr+s,tc+s,dr,dc,s);Boardtr+s-1tc+s-1=t;/覆盖号三格板覆盖号三格板Boardtr+s-1tc+s=t;Boardtr+stc+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)
84、for(inti=0;isize;i+)for(intj=0;j0)return(aleft);elsereturn(0);elsecenter=(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;for(i=center;i=left;i-)lefts=lefts+ai;if(leftss1)s1=lefts;s2=0;rights=0;for(i=center+1;is2)s2=rights;if(s1+s2lef
85、t_sumandright_sumleft_sum)rturn(left_sum);if(s1+s2right_sum)return(right_sum);return(s1+s2);【例【例4 4】大整数乘法大整数乘法在某些情况下，我们需要处理很大的整数，它无法在计算机在某些情况下，我们需要处理很大的整数，它无法在计算机硬件能直接允许的范围内进行表示和处理。若用浮点数来存硬件能直接允许的范围内进行表示和处理。若用浮点数来存储它，只能近似地参与计算，计算结果的有效数字会受到限储它，只能近似地参与计算，计算结果的有效数字会受到限制。若要精确地表示大整数，并在计算结果中要求精确地得制。若要精确地表
86、示大整数，并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。请设计一个有效的算法，可以进行两个算术运算。请设计一个有效的算法，可以进行两个n位大整数位大整数的乘法运算。的乘法运算。数据结构设计数据结构设计：首先用数组存储大整数数据，再将两个乘数：首先用数组存储大整数数据，再将两个乘数和积都按由低位到高位逐位存储到数组元素中。和积都按由低位到高位逐位存储到数组元素中。算法设计算法设计1 1：存储好两个高精度数据后，模拟竖式乘法，让两：存储好两个高精度数据后，模拟竖式乘法，让两个高精度数据的按位交叉相乘，并逐
87、步累加即可得到精确的个高精度数据的按位交叉相乘，并逐步累加即可得到精确的结果，用二重循环就可实现。结果，用二重循环就可实现。算算法法设设计计1：存存储储好好两两个个高高精精度度数数据据后后，我我们们模模拟拟竖竖式式乘乘法法，让让两两个个高高精精度度数数据据的的按按位位交交叉叉相相乘乘，并并逐逐步步累累加加，即即可可得得到到精精确确的计算结果。用二重循环就可控制两个数不同位相乘的过程。的计算结果。用二重循环就可控制两个数不同位相乘的过程。只考虑正整数的乘法，算法细节设计如下：只考虑正整数的乘法，算法细节设计如下：1)对对于于大大整整数数比比较较方方便便的的输输入入方方法法是是，按按字字符符型型处
88、处理理，存存储储在在字符串数组字符串数组s1、s2中，计算结果存储在整型数组中，计算结果存储在整型数组a中。中。2)2)通通过过字字符符的的ASCII码码，数数字字字字符符可可以以直直接接参参与与运运算算，k位位数数字字与与j位位数数字字相相乘乘的的表表达达式式为为：s1k-48)*(s2j-48)。这这是是C语语言言的的处处理理方方法法，其其它它程程序序设设计计语语言言有有对对应应的的函函可可以以实实现现数数字字字符与数字的转换，这里不详细介绍了。字符与数字的转换，这里不详细介绍了。3)3)每每一一次次数数字字相相乘乘的的结结果果位位数数是是不不固固定定的的，而而结结果果数数组组中中每每个个
89、元元素素只只存存储储一一位位数数字字，所所以以用用变变量量b暂暂存存结结果果，若若超超过过1位位数数则则进位，用变量进位，用变量d存储。这样每次计算的表达式为：存储。这样每次计算的表达式为：b=ai+(s1k-48)*(s2j-48)+d;。main( )main( ) long b,c,d; long b,c,d; intint i,i1,i2,j,k,n,n1,n2,a256; i,i1,i2,j,k,n,n1,n2,a256; char s1256,s2256; char s1256,s2256; input(s1); input(s2); input(s1); input(s2); f
90、or (i=0;i255;i+) for (i=0;i255;i+) ai=0; ai=0; n1= n1=strlenstrlen(s1); n2=(s1); n2=strlenstrlen(s2); (s2); d=0; d=0; for (i1=0,k=n1-1;i1n1;i1+,k-) for (i1=0,k=n1-1;i1n1;i1+,k-) for (i2=0,j=n2-1;i2n2;i2+,j-) for (i2=0,j=n2-1;i20) while (d0) i=i+1; ai= ai+d mod 10; d=d/10; i=i+1; ai= ai+d mod 10; d=d
91、/10; n=i; n=i; for (i=n;i=0;i-) print(ai); for (i=n;i=0;i-) print(ai); 算算法法说说明明：循循环环变变量量j j、k k分分别别是是两两个个乘乘数数字字符符串串的的下下标标。i1i1表表示示字字符符串串str1str1由由低低位位到到高高位位的的位位数数，范范围围00n1-1n1-1（与与k k相相同同）。i2i2表表示示字字符符串串str2str2由由低低位位到到高高位位的的位位数数，范范围围00n2-n2-1 1（与与j j相相同同）。i i表表示示乘乘法法正正在在运运算算的的位位，也也是是计计算算结结果果存存储储的位置
92、。的位置。算法分析算法分析1 1：算法是以算法是以n1,n2n1,n2代表两个乘数的位数，由算法中的循代表两个乘数的位数，由算法中的循环嵌套知，算法的主要操作是乘法，算法的时间复杂度是环嵌套知，算法的主要操作是乘法，算法的时间复杂度是O O（n1*n2n1*n2）。）。算法设计算法设计2 2：下面们用分治法来设计一个更有效的大整数乘积算下面们用分治法来设计一个更有效的大整数乘积算法。设计的重点是要提高乘法算法的效率，设计如下：法。设计的重点是要提高乘法算法的效率，设计如下：设设X和和Y都是都是n位的二进制整数，现在要计算它们的乘积位的二进制整数，现在要计算它们的乘积X*Y。图图4-10 4-1
93、0 大整数大整数X X和和Y Y的分段的分段 将将n n位的二进制整数位的二进制整数X X和和Y Y各分为各分为2 2段，每段的长为段，每段的长为n/2n/2位位( (为简为简单起见，假设单起见，假设n n是是2 2的幂的幂) )，如图，如图4-104-10所示。显然问题的答案并不所示。显然问题的答案并不是是A*C*K1+C*D*K2A*C*K1+C*D*K2（K1K1、K2K2与与A A、B B、C C、D D无关），也就是说，这无关），也就是说，这样做并没有将问题分解成两个独立的子问题。按照乘法分配律，样做并没有将问题分解成两个独立的子问题。按照乘法分配律，分解后的计算过程如下：分解后的计
94、算过程如下：记：记：X=A*2X=A*2n/2n/2+B +B ，Y=C*2Y=C*2n/2n/2+D+D。这样，这样，X X和和Y Y的乘积为：的乘积为：X*Y=(A*2n/2+B)(C*2n/2+D)=A*C*2n+(AD+CB)*2n/2+B*D(1)(1)模型分析模型分析：如如果果按按式式(1)(1)计计算算X*YX*Y，则则我我们们必必须须进进行行4 4次次n/2n/2位位整整数数的的乘乘法法( (ACAC，ADAD，BCBC和和BD)BD)，以以及及3 3次次不不超超过过n n位位的的整整数数加加法法，此此外外还还要要做做2 2次次移移位位 ( (分分别别对对应应于于式式(1)(1
95、)中中乘乘2 2n n和和乘乘2 2n/2n/2) )。所所有有这这些些加加法法和和移移位位共共用用O(n)O(n)步步运运算算。设设T(n)T(n)是是2 2个个n n位位整整数数相相乘乘所所需需的的运运算算总总数数，则由式则由式(1)(1)，我们有以下，我们有以下(2)(2)式：式： T T（1 1）=1=1 T T（n n）=4T(n/2)+O(n) =4T(n/2)+O(n) （2 2） 由此由此递归递归式迭代式迭代过过程如下：程如下：T(n)=4T(n/2)+T(n)=4T(n/2)+cncn =4(4T(n/4)+ =4(4T(n/4)+cncn/2)+/2)+cncn =16(T
96、(n/8)+=16(T(n/8)+ cn cn/4)+3cn/2+/4)+3cn/2+cncn = = = = +4+4k-1 k-1 *2c+4*2c+4k-2 k-2 *4c+4c2*4c+4c2k-1k-1+c2+c2k k =O =O（4 4k k）= O= O(nlog4) =O =O（n n2 2）所以可得算法的时间复杂度为所以可得算法的时间复杂度为T(n)=O(nT(n)=O(n2 2) )。模型改进：模型改进：可以把可以把X*YX*Y写成另一种形式：写成另一种形式：X*Y=A*C*2X*Y=A*C*2n n+(A-B)(D-C)+AC+BD*2+(A-B)(D-C)+AC+BD
97、*2n/2n/2+B*D+B*D (3) (3)式式(3)(3)看看起起来来比比式式(1)(1)复复杂杂，但但它它仅仅需需做做3 3次次n/2n/2位位整整数数的的乘乘法法：ACAC，BDBD和和( (A-B)(D-C)A-B)(D-C)，6 6次次加加、减减法法和和2 2次次移移位位。由由此此可可得得: : (4) (4)用解递归方程的迭代公式法，不妨设用解递归方程的迭代公式法，不妨设n=2n=2k k： T(n)=3T(n/2)+ T(n)=3T(n/2)+cncn =3(3T(n/4)+=3(3T(n/4)+cncn/2)+/2)+cncn =9(T(n/8)+=9(T(n/8)+ cn
98、 cn/4)+3cn/2+/4)+3cn/2+cncn = = =3 3k k +3+3k-1 k-1 *2c+3*2c+3k-2 k-2 *4c+3c2*4c+3c2k-1k-1+c2+c2k k = O = O(nlog3)则得到则得到T(n)=OT(n)=O(nlog3)=O(nO(n1.59) )。MULT(X,Y,n)X和和Y为为2个小于个小于2n的整数，返回结果为的整数，返回结果为X和和Y的乘积的乘积XYS=SIGN(X)*SIGN(Y);/S为为X和和Y的符号乘积的符号乘积X=ABS(X);Y=ABS(Y);/X和和Y分别取绝对值分别取绝对值if（n=1）if(X=1andY=1
99、)return(S)；elsereturn(0)；elseA=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);434其它分治方法其它分治方法以上的例子都是用二分策略把以上的例子都是用二分策略把问题问题分解分解为为与原与原问题问题相似相似“相等相等”的子的子问题问题。下面看几个用。下面看几个用“非等分二分法非等分二分法”解决解决问题问题的例
100、子。的例子。选择问题选择问题就是就是“从一从一组组数中数中选择选择的第的第k小的数据小的数据”，这这个个问题问题的一的一个个应应用就是用就是寻寻找中找中值值元素，此元素，此时时k=n/2。中中值值是一个很有是一个很有用的用的统计统计量，例如中量，例如中间间工工资资，中，中间间年年龄龄，中，中间间重量等。重量等。k取其他取其他值值也是有意也是有意义义的，例如，通的，例如，通过寻过寻找第找第k=n/2、k=n/3和和k=n/4的年的年龄龄,可将人口可将人口进进行划分，了解人口的分布情况。行划分，了解人口的分布情况。 这个问题可以通过排序来解决，但根据数据结构课程的经这个问题可以通过排序来解决，但根
101、据数据结构课程的经验，最好的排序算法的复杂性也是验，最好的排序算法的复杂性也是O O（n*log(n)n*log(n)），），下面我们要利下面我们要利用分治法，找到复杂性为用分治法，找到复杂性为O O（n n）的算法。但这个问题不能用简单的的算法。但这个问题不能用简单的二分法分解成完全独立、相似的两个子问题。因为在选出分解后第二分法分解成完全独立、相似的两个子问题。因为在选出分解后第一组的第一组的第k k小的数据和第二组的第小的数据和第二组的第k k小的数据，不能保证在这两个数小的数据，不能保证在这两个数据之一是原问题的解。据之一是原问题的解。以求一组数的第二小的数据为例，我们讨论解决问题的办
102、法。以求一组数的第二小的数据为例，我们讨论解决问题的办法。【例【例5】选择问题】选择问题0求一组数的第二小的数。求一组数的第二小的数。 floatan;second（inti,intj，float&fmin2,&fmin1）floatlmin2,lmin1,rmin2,rmin;intmid;if（i=j）fmin2=fmin1=aielseif(i=j-1)if(aiaj)fmin2=aj；fmin1=ai;elsefmin2=ai;fmin1=aj; elsemid=(i+j)/2;second（i，mid，lmin2，lmin1）;second（mid+1，j，rmin2，rmin1）;
103、算法分析：此算法的时间复杂度与【例算法分析：此算法的时间复杂度与【例1】相同，为】相同，为O（n）。if(lmin1rmin1)if（lmin2rmin1）fmin1=lmin1;fmin2=lmin2;elsefmin1=lmin1;fmin2=rmin1;elseif(rmin2k-1k-1，则选择问题的答案继续在左子集中找，问则选择问题的答案继续在左子集中找，问 题规模变小了。题规模变小了。 3 3）nleftnleftk-1k-1，则选择问题的答案继续在右子集中找，问则选择问题的答案继续在右子集中找，问 题变为选择第题变为选择第k-k-nleftnleft-1-1小的数，问题的规模也变
104、小了。小的数，问题的规模也变小了。xzwt(inta,intn,intk)/返回返回a0:n-1中第中第k小的元素小的元素if(kn)error();returnselect(a,0,n-1,k);select(inta,intleft,intright,intk)/在在aleft:right中选择第中选择第k小的元素小的元素/if(left=right)returnaleft;inti=left;/从左至右的指针从左至右的指针j=right+1;/从右到左的指针从右到左的指针intpivot=aleft;/把最左面的元素作为分界数据把最左面的元素作为分界数据while(1)do/在左侧寻找在
105、左侧寻找=pivot的元素的元素i=i+1;while(aipivot);/在右侧寻找在右侧寻找=j)break;/未发现交换对象未发现交换对象Swap(ai,aj);if(j-left+1=k)returnpivot;aleft=aj;/设置设置pivotaj=pivot;if(j-left+1k)/对一个段进行递归调用对一个段进行递归调用returnselect(a,j+1,right,k-j-1+left);elsereturnselect(a,left,j-1,k);算法分析：算法分析：1 1）以上算法在最坏情况下的复杂性是）以上算法在最坏情况下的复杂性是O( nO( n2 2 ) )
106、，此时此时left left 总是为空，总是为空，而且第而且第k k个元素总是位于个元素总是位于rightright子集中。子集中。2 2）如果假定）如果假定n n是是2 2的幂，通过迭代方法，可以得到算法的平均复杂的幂，通过迭代方法，可以得到算法的平均复杂性是性是O(n)。若仔细地选择分界元素，则最坏情况下的时间开销也若仔细地选择分界元素，则最坏情况下的时间开销也可以变成可以变成( (n)n)。一种选择分界元素的方法是使用一种选择分界元素的方法是使用“中间的中间中间的中间（median-of-median）”规则，该规则首先将数组规则，该规则首先将数组a a中的中的n n 个元素分成个元素分
107、成n/r n/r 组，组，r r 为某一整常数，除了最后一组外，每组为某一整常数，除了最后一组外，每组都有都有r r 个元素。然后通过在每组中对个元素。然后通过在每组中对r r 个元素进行排序来寻找每个元素进行排序来寻找每组中位于中间位置的元素。最后根据所得到的组中位于中间位置的元素。最后根据所得到的n/r n/r 个中间元素，个中间元素，递归使用选择算法，求得所需要的分界元素。这里不深入讨论。递归使用选择算法，求得所需要的分界元素。这里不深入讨论。3 3）注意到这个算法实质上只是利用了分治法的分解策略，分解后）注意到这个算法实质上只是利用了分治法的分解策略，分解后根据不同情况，只处理其中的一个子问题，并没有象根据不同情况，只处理其中的一个子问题，并没有象【例【例1 1】一】一样有回溯合并的过程。样有回溯合并的过程。
