第四章 算法策略

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、一代小兔子。假若兔子子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。个月各有多少只兔子。问题分析：问题分析：因一对兔子从出生后第三个月开始每月生一对小兔因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数子，则每月新下小兔子的对儿数(用斜体数字表示用斜体数字表示)显然由前显然由前两个月的小兔子的对儿数决定。则繁殖过程如下：两个月的小兔子的对儿数决定。则繁殖过程如下： 一月一月 二月二月 三月三月 四月四月 五月五月 六月六月 1 1 1+1=2 2+1=

3、3 3+2=5 5+3=8 算法算法1 1： 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

4、 8 91 2 3 4 5 6 7 8 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

5、=b+c; c=a+b; a=b+c; b=c+a; print(a,b,c); b=c+a; print(a,b,c); 算法算法2 2，最后输出的，最后输出的并不是并不是1212项，而是项，而是2+32+3* *4 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;”做循环做循环“不变式不变式”，从而得到以

6、下算法从而得到以下算法3: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=5;i+)=5;i+) a=a+b; a=a+b; b=a+b; print(a,b); b=a+b; print(a,b); 【例【例2 2】求两个整数的最大公约数。求两个整数的最大公约数。数学建模：数学建模：辗转相除法是根据递推策略设计的。辗转相除法是根据递推策略设计的。不妨设两个整数不妨设两个整数abab且且a a除以除以b b商商x x余余c c；则；则a-bxa-bx=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” 相除的余数，

8、经相除的余数，经a=b,b=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(“data error”); return; else else c = a mod b; c = a mod b; while c0 while c0 a=b; a=b; b=

9、c; b=c; c=a mod b; c=a mod b; print(b); print(b); 4.1.2 4.1.2 倒推法倒推法 所谓所谓倒推法倒推法：是对某些特殊问题所采用的违反通常习惯的，从：是对某些特殊问题所采用的违反通常习惯的，从 后向前推解问题的方法。如下面的例题，因不同方面的需求而采后向前推解问题的方法。如下面的例题，因不同方面的需求而采用了倒推策略。用了倒推策略。例例1在不知前提条件的情况下，经过从后向前递推，从而求解问在不知前提条件的情况下，经过从后向前递推，从而求解问题。即由结果倒过来推解它的前提条件。又如例题。即由结果倒过来推解它的前提条件。又如例2由于存储的要由于

10、存储的要求，而必须从后向前进行推算。另外，在对一些问题进行分析或求，而必须从后向前进行推算。另外，在对一些问题进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法（如例法（如例3），则问题容易理解和解决。下面分别看这几个例子：），则问题容易理解和解决。下面分别看这几个例子：【例【例1 1】猴子吃桃问题猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第到第1010天时就只有一个桃子了，求原有多少个桃？天时就只有一个桃子了，求原有多少个桃？数学模型：数学模型：每

11、天的桃子数为：每天的桃子数为：a10=1, a9=(1+a10)a10=1, a9=(1+a10)* *2, 2, a8=(1+a9)a8=(1+a9)* *2,2,a10=1a10=1， 递推公式为：递推公式为：ai=(1+aiai=(1+ai+1)+1)* *2 i = 9,8,7,62 i = 9,8,7,61 1算法如下算法如下 ： 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) s=(s+1)* *2 2 print (s) print (s)；

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

13、 2 11 3 3 11 3 3 11 1 4 6 4 14 6 4 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行行算法如下：算法如下：main( ) int n,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

14、-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城雇用一人与探险家同带城雇用一人与探险家同带3 3天食物同行一天，然后被雇天食物同行一天，然后被雇 人带一天食物返回，并留一天食物给探险家，这样探险人带一天食物返回，并留一天食物给探险家，这样探险 家正好有家正好有3 3天的食物继续前行，并于第三

16、天打电话雇天的食物继续前行，并于第三天打电话雇b b城城 人带人带3 3天食物出发，第四天会面他们会面，探险家得到一天食物出发，第四天会面他们会面，探险家得到一 天的食物赴天的食物赴b b城。如图城。如图4-34-3主要表示了被雇用二人的行程。主要表示了被雇用二人的行程。 a a b b 图图4-3 4-3 被雇用二人的行程被雇用二人的行程 2 2）贮油点问题要求要以最少的耗油量穿越沙漠，即到达终贮油点问题要求要以最少的耗油量穿越沙漠，即到达终 点时，沙漠中的各临时油库和车的装油量均为点时，沙漠中的各临时油库和车的装油量均为0 0。这样只。这样只 能从终点开始向前倒着推解贮油点和贮油量。能从终

17、点开始向前倒着推解贮油点和贮油量。数学模型：数学模型：根据耗油量最少目标的分析，下面从后向前分段根据耗油量最少目标的分析，下面从后向前分段讨论。讨论。第一段长度为第一段长度为500500公里且第一个加油点贮油为公里且第一个加油点贮油为500500加仑。加仑。第二段中为了贮备油，吉普车在这段的行程必须有往返。第二段中为了贮备油，吉普车在这段的行程必须有往返。下下面讨论怎样走效率高：面讨论怎样走效率高：1 1）首先不计方向这段应走奇数次（保证最后向前走）。首先不计方向这段应走奇数次（保证最后向前走）。2 2）每次向前行进时吉普车是满载。每次向前行进时吉普车是满载。3 3）要能贮存够下一加油点的贮油

18、量，路上耗油又最少。要能贮存够下一加油点的贮油量，路上耗油又最少。下图是满足以上条件的最佳方案，此段共走下图是满足以上条件的最佳方案，此段共走3 3次：第一、二次：第一、二次来回耗油次来回耗油2/32/3贮油贮油1/31/3，第三次耗油，第三次耗油1/31/3贮油贮油2/32/3，所以第，所以第二个加油点贮油为二个加油点贮油为10001000加仑。由于每公里耗油率为加仑。由于每公里耗油率为1 1加仑，加仑，则此段长度为则此段长度为500/3500/3公里。公里。第三段与第二段思路相同。下图是一最佳方案此段共走第三段与第二段思路相同。下图是一最佳方案此段共走5 5次：次：第一、二次来回耗油第一、

19、二次来回耗油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） 贮油点（贮油点（15001500）图图4-4 4-4 贮油点及贮油量示意贮油点及贮油量示意综上分析综上分析，从终点开始分别间隔，从终点开始分别间隔 500500，500/3500/3，50

20、0/5500/5，500/7500/7，（公里）设立贮油点，直到总距离超过（公里）设立贮油点，直到总距离超过10001000公里。每个贮油点的油量为公里。每个贮油点的油量为500500，10001000，15001500，。 算法设计：算法设计：由模型知道此问题并不必用倒推算法解决（只由模型知道此问题并不必用倒推算法解决（只是分析过程用的是倒推法），只需通过累加算法就能解决。是分析过程用的是倒推法），只需通过累加算法就能解决。变量说明：变量说明：disdis表示距终点的距离，表示距终点的距离，1000- 1000- disdis则表示距起则表示距起点的距离，点的距离，k k表示贮油点从后到前的

21、序号。表示贮油点从后到前的序号。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 p r i n t ( “ s t o r e p o i n t ” , k , ” d i s t a n c e ” , 1 0 0 0 -p r i n t ( “ s t o r e p o i n t ” , k , ” d i s t a n c e ” , 1 0 0 0 -dis,”oilquantitydis,”oilquantity”,oil)”,o

22、il)； k=k+1;k=k+1; dis=dis dis=dis+500/(2+500/(2* *k-1);k-1); oil= 500 oil= 500* *k;k; while ( dis while ( dis1000)1000) oil=500*(k-1)+(1000-dis)*( 2*k-1); print(“storepoint”,k,”distance”,0,”oilquantityprint(“storepoint”,k,”distance”,0,”oilquantity”,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=（x0 x0，x1x1，xnxn-1-1）, ,迭代迭代关系关系方程组为：方程组为：xi=gixi=gi(x)(i=0,1,(x)(i=0,1,n-1),w,n-1),w为解的精度为解的精度, ,则则算法如下：算法如下： for (i=0;in;i+)for (

25、i=0;in;i+) xi= xi=初始近似根初始近似根; ; 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+) xi=gi for (i=0;in;i+) xi=gi(x);(x); for (i=0;in;i+) c=c+fabs for (i=0;iw and kw and kmaxn ) )； for (i=0;in;i+) for (i=0;in;i+) print(i print(i，“变量的近似根是变量的近似根是”，xi)xi)； 【例【例2 2】牛顿迭代法牛顿迭代法 牛顿迭代

26、法又称为切线法，它比一般的迭代法有更高的收敛速度，牛顿迭代法又称为切线法，它比一般的迭代法有更高的收敛速度，如图如图4-54-5所示。首先所示。首先, , 选择一个接近函数选择一个接近函数f(x)f(x)零点的零点的x0, x0, 计算相应计算相应的的f(x0)f(x0)和切线斜率和切线斜率f(x0)f(x0)（这里（这里f f 表示函数表示函数f f的导数）。然后的导数）。然后我们计算穿过点我们计算穿过点( (x0,f (x0)x0,f (x0)且斜率为且斜率为f (x0)f (x0)的直线方程为：的直线方程为：和和x x轴的交点的轴的交点的x x坐标坐标, , 也就是求如下方程的解：也就是

27、求如下方程的解：)()(000 xxxfxfy0000)()(xxxfxf图图4-5 4-5 牛顿迭代法牛顿迭代法 示意图示意图迭代公式可化简为：迭代公式可化简为：此公式就是有名的牛顿迭代公式此公式就是有名的牛顿迭代公式。已经证明。已经证明, , 如果如果ff是连是连续的续的, , 并且待求的零点并且待求的零点x x是孤立的是孤立的, , 那么在零点那么在零点x x周围存在周围存在一个区域一个区域, , 只要初始值只要初始值x0 x0位于这个邻近区域内位于这个邻近区域内, , 那么牛顿那么牛顿法必定收敛。法必定收敛。 下面给出用牛顿迭代法，求形如下面给出用牛顿迭代法，求形如ax3+bx2+cx

28、+d=0方程根的方程根的算法，系数算法，系数a、b、c、d的值依次为的值依次为1、2、3、4，由主函数，由主函数输入。求输入。求x在在1附近的一个实根。求出根后由主函数输出。附近的一个实根。求出根后由主函数输出。 main( ) float a , b, c, d, fx; print(输入系数输入系数 a,b,c,d:); input(a,b,c,d); fx=f(a,b,c,d); printf(方程的根为：方程的根为：,fx); 令令 a0,b0=a,ba0,b0=a,b，c0=(a0+b0)/2c0=(a0+b0)/2，若若f(c0)=0f(c0)=0，则，则c0c0为为方程方程f(x

29、)=0f(x)=0的根；否则，若的根；否则，若f(a0)f(a0)与与f(c0)f(c0)异号，即异号，即 f(a0)f(a0)* *f(c0)0f(c0)0，则令，则令 a1,b1=a0,c0a1,b1=a0,c0；若；若f(b0)f(b0)与与f(c0)f(c0)异异号，即号，即 f(b0)f(b0)* *f(c0)0f(c0)0，则令，则令 a1,b1=c0,b0a1,b1=c0,b0。 依此做下去，依此做下去，当发现当发现f(cn)=0时，或时，或区间区间an,bn足够小，足够小，比如比如| an-bn |0.0001时，就认为找到了方程的根。时，就认为找到了方程的根。 用二分法求一元

30、非线性方程用二分法求一元非线性方程f(x)= x3/2+2x2-8=0（其中（其中表示幂运算）在区间表示幂运算）在区间0，2上的近似实根上的近似实根r，精确到，精确到0.0001.算法如下：算法如下： 图图4-6 4-6 二分法二分法求求解解 方程方程示意示意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) print(“input a,b (f(a)* *f(b)0)”); input(a,b);f(b)0) printff20) printf(no root

31、); return;(no root); return; do do x=(x1+x2)/2; x=(x1+x2)/2; f=x f=x* *x x* *x/2+2x/2+2* *x x* *x-8;x-8; if(f=0) break; if(f=0) break; if(f1 if(f1* *f0.0) x1=x; f1=x1f0.0) x1=x; f1=x1* *x1x1* *x1/2+2x1/2+2* *x1x1* *x1-8;x1-8; else x2=x; else x2=x;while(fabswhile(fabs(f)=1e-4);(f)=1e-4);print(root=,x

32、); print(root=,x); 4.2 蛮力法蛮力法4.2.1 4.2.1 枚举法枚举法4.2.2 4.2.2 其它范例其它范例 蛮力法蛮力法是基于计算机运算速度快这一特性，在解决问题时采是基于计算机运算速度快这一特性，在解决问题时采取的一种取的一种“ “懒惰懒惰” ”的策略。这种策略不经过（或者说是经过很少的）的策略。这种策略不经过（或者说是经过很少的）思考，把问题的所有情况或所有过程交给计算机去一一尝试，从思考，把问题的所有情况或所有过程交给计算机去一一尝试，从中找出问题的解。蛮力策略的应用很广，具体表现形式各异，数中找出问题的解。蛮力策略的应用很广，具体表现形式各异，数据结构课程中

33、学习的：选择排序、冒泡排序、插入排序、顺序查据结构课程中学习的：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等，都是蛮力策略具体应用。比较常用还找、朴素的字符串匹配等，都是蛮力策略具体应用。比较常用还有有枚举法枚举法、盲目搜索算法等，本节介绍、盲目搜索算法等，本节介绍枚举法枚举法和其它一些小的范和其它一些小的范例，第五章介绍盲目搜索算法。例，第五章介绍盲目搜索算法。 4 42 21 1 枚举法枚举法 枚举枚举（ enumerate）法（穷举法）是）法（穷举法）是蛮力策略的一种表现形式蛮力策略的一种表现形式，也是一种使用非常普遍的思维方法。它是根据问题中的条件将可能也是一种使用非常普

34、遍的思维方法。它是根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。可能解的列举数目。用枚举法解决问题，通常可以从两个方面进行算法设计：用枚举法解决问题，通常可以从两个方面进行算法设计： 1）找出枚举范围：分析问题所涉及的各种情况。找出枚举范围：分析问题所涉及的

35、各种情况。 2 2）找出约束条件：分析问题的解需要满足的条件，并用逻辑）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。表达式表示。【例【例1 1】百钱百鸡问题。中国古代数学家张丘建在他的百钱百鸡问题。中国古代数学家张丘建在他的算经算经中提出了著名的中提出了著名的“百钱百鸡问题百钱百鸡问题”：鸡翁一，值钱五；鸡母一，：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何? ?算法设计算法设计1：通过对问题的理解，读者可能会想到列出两个三元一次方程，通过对问题的理解，读者可能会想到列出两个三元一次方程，去解

36、这个不定解方程，就能找出问题的解。这确实是一种办法，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用但这里我们要用“懒惰懒惰”的枚举策略进行算法设计：的枚举策略进行算法设计： 设设x，y，z分别为公鸡、母鸡、小鸡的数量。分别为公鸡、母鸡、小鸡的数量。 尝试范围：由尝试范围：由题意给定共题意给定共100钱要买百鸡，若全买公鸡最钱要买百鸡，若全买公鸡最多买多买100/5=100/5=20只，显然只，显然x的取值范围的取值范围120之间；同理，之间；同理，y的的取值范围在取值范围在133之间，之间，z z的取值范围的取值范围在在11001100之间之间。 约束条件：约束条件：

37、x+y+z=100 x+y+z=100 且且 5 5* *x+3x+3* *y+z/3=100y+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 if(100=x+y+z and 100=5* *x+3x+3* *y+z/3)y+z/3) pr

38、int(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）的数量的数量确定后，小鸡确定后，小鸡的数量的数量z就固就固

39、定为定为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 5* *x+3x+3* *y+z/3=100) y+z/3=100) print(the c

40、ock 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+3x+3* *y+z/3=100”y+z/3=100”。这样省去了这样省去了z z不整除

41、不整除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：3 39 9（a=1a=1，2 2时积不会得到六位数）时积不会得到六位数）, ,b b：0 09,9, c c：0 09 9 六位数表示为六位数表示为a a* *10000+b10000+b* *1000+c1000+c* *100+a100+a* *10+b10+b，

42、共尝试共尝试800800次。次。2)2)约束条件为：约束条件为： 每次尝试，先求六位数与每次尝试，先求六位数与a a的积，再测试积的各位是否相的积，再测试积的各位是否相 同，若相同则找到了问题的解。同，若相同则找到了问题的解。 测试积的各位是否相同比较简单的方法是，从低位开始，测试积的各位是否相同比较简单的方法是，从低位开始， 每次都取数据的个位，然后整除每次都取数据的个位，然后整除1010，使高位的数字不断变，使高位的数字不断变 成个位，并逐一比较。成个位，并逐一比较。 算法算法1 1如下：如下：main（ ） int a,b,c,d,e,e1,f,g1,g2,i; for(a=3; a=9

43、; 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=e1 mod 10; for(i=1; i=5; i+) g2=g1; e1=e1/10; g1= e1 mod 10; if(g1g2 ) break; if(i=6) print( f，”*”，a，”=”，e); 算法中对枚举出的每一个五位数与算法中对枚举出的每一个五位数与a a相乘，结果相乘，结果存储在变量存储在变量e e中。然后，测试得到的六位数中。然后，测试得到的六位数e e是否各个位的数是否各个位的数字都相

44、同。鉴于要输出结果，所以不要改变计算结果，而另字都相同。鉴于要输出结果，所以不要改变计算结果，而另设变量设变量e1e1，用于测试运算。，用于测试运算。算法设计算法设计2 2：将算式变形为除法：将算式变形为除法：dddddd/a=abcabdddddd/a=abcab。此时。此时只需枚举只需枚举a a：3 39 d9 d：1 19 9，共尝试，共尝试7 7* *9=639=63次。每次次。每次尝试，测试商的万位、十位与除数是否相同，千位与个位尝试，测试商的万位、十位与除数是否相同，千位与个位是否相同，都相同时为解。是否相同，都相同时为解。算法算法2 2如下如下: :mainmain（）（）int

45、int 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 = d e = d* *100000+d100000+d* *10000+d10000+d* *1000+d1000+d* *100+d100+d* *10+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

46、mod 10) if(f1000=f mod 10) print( f print( f，”* *”，a a，”=”=”，e);e); 蛮力法的表现形式非常多，如第三章蛮力法的表现形式非常多，如第三章3.2.4例题、例题、3.2.5例例1及本章下一节及本章下一节4.3.3例例4的算法的算法1等。本节将通过蛮力策略，用等。本节将通过蛮力策略，用算法模拟问题中所描述的全部过程和全部状态，来找出问题的解，算法模拟问题中所描述的全部过程和全部状态，来找出问题的解，并与经过数学建模后的算法进行效率上的比较。并与经过数学建模后的算法进行效率上的比较。 4 42 22 2 其它范例其它范例【例【例3 3】狱

47、吏问题狱吏问题 某国王对囚犯进行大赦，让一狱吏某国王对囚犯进行大赦，让一狱吏n n次通过一排锁着的次通过一排锁着的n n间牢房，每通过一次，按所定规则转动间牢房，每通过一次，按所定规则转动n n间牢房中的某些门间牢房中的某些门锁锁, , 每转动一次每转动一次, , 原来锁着的被打开原来锁着的被打开, , 原来打开的被锁上；原来打开的被锁上；通过通过n n次后，门锁开着的，牢房中的犯人放出，否则犯人不次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。得获释。 转动门锁的规则是这样的，第一次通过牢房，要转动每转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢

48、房时，从第二间一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第开始转动，每隔一间转动一次；第k k次通过牢房，从第次通过牢房，从第k k间开间开始转动，每隔始转动，每隔k-1 k-1 间转动一次；问通过间转动一次；问通过n n次后，那些牢房的次后，那些牢房的锁仍然是打开的？锁仍然是打开的？算法设计算法设计1 1：1 1）用用n n个空间的一维数组个空间的一维数组an,an,每个元素每个元素记录一个锁的状记录一个锁的状 态，态，1 1为为被锁上，被锁上，0 0为被打开。为被打开。2 2）用数学运算方便模拟开关锁的技巧，对）用数学运算方便模拟开关锁的技巧，对i i

49、号锁的一次开号锁的一次开 关锁可以转化为算术运算：关锁可以转化为算术运算：ai=1-aiai=1-ai。3 3）第一次转动的是）第一次转动的是1 1，2 2，3 3，n n号牢房；号牢房； 第二次转动的是第二次转动的是2 2，4 4，6 6，号牢房；号牢房； 第三次转动的是第三次转动的是3 3，6 6，9 9，号牢房；号牢房； 第第i i次转动的是次转动的是i i，2i2i，3i3i，4i4i，号牢房，是起号牢房，是起点为点为i i，公差为，公差为i i的等差数列。的等差数列。 4 4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关）不做其它的优化，用蛮力法通过循环模拟狱吏的开关 锁过程，最后

50、当第锁过程，最后当第i号牢房对应的数组元素号牢房对应的数组元素aiai为为0 0时，时， 该牢房的囚犯得到大赦。算法该牢房的囚犯得到大赦。算法1如下：如下： main1( )main1( )intint * *a,i,j,n;a,i,j,n; input(n); input(n); a= a=calloc(n+1,sizeof(intcalloc(n+1,sizeof(int);); 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) f

51、or (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(i,”is free.”); 算法分析：算法分析：以一次开关锁计算，算法的时间复杂度为以一次开关锁计算，算法的时间复杂度为n(1+1/2+1/3+n(1+1/2+1/3+1/n)=o(nlogn+1/n)=o(nlogn) )。问题分析：问题分析：转动门锁的规则可以有另一种理解，第一次转动转动门锁的规则可以有另一种理解，第一次转动的是编号为的是编号为1 1的

52、倍数的牢房；第二次转动的是编号为的倍数的牢房；第二次转动的是编号为2 2的倍的倍数的牢房；第三次转动的是编号为数的牢房；第三次转动的是编号为3 3的倍数的牢房；的倍数的牢房；则则狱吏问题是一个关于因子个数的狱吏问题是一个关于因子个数的问题。令问题。令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 编号与因数个数的关系编号与

53、因数个数的关系 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 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的牢房，所含的牢房，所含1 1i i之间的不重复因子个数为奇数时，牢房最后是打开的，之间的

54、不重复因子个数为奇数时，牢房最后是打开的，反之，牢房最后是关闭的。反之，牢房最后是关闭的。算法设计算法设计2:2:1 1）算法应该是求出每个牢房编号的不重复的因子个数，当它）算法应该是求出每个牢房编号的不重复的因子个数，当它为奇数时，这里边的囚犯得到大赦。为奇数时，这里边的囚犯得到大赦。2 2）一个数的因子是没有规律的，只能从）一个数的因子是没有规律的，只能从1 1n 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

55、=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） print(i,”is free.”); print(i,”is free.”); 算法分析：算法分析： 狱吏开关锁的主要操作是狱吏开关锁的主要操作是ai=1- ai;ai=1- ai;共执行了共执行了n n* *(1+1/2+1/3+(1+1/2+1/3+1/n)+1/n)次，时间近似为复杂度为次，时间近似为复杂度为o（n log n）。使用了

56、）。使用了n n个空间的一维数组。算法个空间的一维数组。算法2 2没有使用辅助没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其空间，但由于求一个编号的因子个数也很复杂，其主要操主要操作是判断作是判断i mod ji mod j是否为是否为0 0，共执行了，共执行了n n* *(1+2+3+(1+2+3+n)+n)次，时间复杂度为次，时间复杂度为o o（n n2 2）。）。 数学模型数学模型2 2：仔细观察表：仔细观察表4-34-3，发现当且仅当，发现当且仅当n n为完为完全平方数时全平方数时,d(n),d(n)为奇数；这是因为为奇数；这是因为n n的因子是成的因子是成对出现的对出现的,

57、 ,也即当也即当n=an=a* *b b且且abab时，必有两个因子时，必有两个因子a a，b; b; 只有只有n n为完全平方数，也即当为完全平方数，也即当n=an=a2 2时时, , 才会出才会出现现d(n)d(n)为奇数的情形。为奇数的情形。算法设计算法设计3 3：这时只需要找出小于：这时只需要找出小于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* *i=ni=n） prin

58、t(i,”is free.print(i,”is free.”);); else else break; break; 由此算法我们应当注意：在对运行效率要求较高的大规模的由此算法我们应当注意：在对运行效率要求较高的大规模的数据处理问题时，必须多动脑筋找出效率较高的数学模型及其数据处理问题时，必须多动脑筋找出效率较高的数学模型及其对应的算法。对应的算法。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

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

60、若干个规模较小，相互独立，与原问）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；题形式相同的子问题； 2）解决：若子问题规模较小而容易被解决则直接解，否则再）解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；继续分解为更小的子问题，直到容易解决； 3）合并：将已求解的各个子问题的解，逐步合并为原问题的）合并：将已求解的各个子问题的解，逐步合并为原问题的解。解。有时问题分解后，不必求解所有的子问题，也就不必作第三步有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中的操作。比如