第6讲 迭代法及蛮力法

1、Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms第四章第四章 基本的算法策略基本的算法策略4.1 4.1 迭代算法迭代算法4.2 4.2 蛮力算法蛮力算法4.3 4.3 分而治之算法分而治之算法4.4 4.4 贪婪算法贪婪算法4.5 4.5 动态规划动态规划 4.6 4.6 算法策略间的比较算法策略间的比较Design and Analysis of Computer Algorithms4.1 迭代算法迭代算法4.1.1 4.1.1 递推法递推法4.1.2 4.1.2 倒推

2、法倒推法4.1.3 4.1.3 迭代法解方程迭代法解方程大连海事大学Design and Analysis of Computer Algorithms411 递推递推法 【例例1】兔子繁殖问题兔子繁殖问题问题描述：一对兔子从出生后第三个月开始，每月生一对小兔问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。个月各有多少只兔子。问题分析：因一对兔子从出生后第三个月开始每月生

3、一对小兔问题分析：因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数子，则每月新下小兔子的对儿数(用斜体数字表示用斜体数字表示)显然由显然由前两个月的小兔子的对儿数决定。则繁殖过程如下：前两个月的小兔子的对儿数决定。则繁殖过程如下：大连海事大学一月一月二月二月三月三月四月四月五月五月六月六月111+1=22+1=33+2=55+3=8Design and Analysis of Computer Algorithms算法算法1 1： main( )main( ) int i,a=1,b=1; int i,a=1,b=1; print(a,b); print(a,b); f

4、or(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-1n-1+y+yn-2n-2，n=3n=3，4 4，5 5，。Design and Analysis of Computer Algorithms算法算法2 2： 表表4-1 4-1 递推迭代表达式递推迭代表达式1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9a b c=a+b a=b+c b=a+c c=a+

5、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 i,a=1,b=1; int 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; b=c+a; print(a,b,c); c=a+b; a=b+c; b=c+a;

6、print(a,b,c); 大连海事大学算法算法2 2，最后输出的，最后输出的并不是并不是1212项，而是项，而是2+32+3* *4 4共共1414项。项。 Design and Analysis of Computer Algorithms 表表4-2 4-2 递推迭代表达式递推迭代表达式1 21 2 3 4 5 6 7 8 93 4 5 6 7 8 9a b a=a+b b=a+b a=a+b b=a+b a 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;”做循环做循环“不变式不变式”，从而得到

7、以下算法从而得到以下算法3:3:main( )main( ) int i,a=1,b=1; int 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; b=a+b; print(a,b); a=a+b; b=a+b; print(a,b); 大连海事大学Design and Analysis of Computer Algorithms【例例2 2】求两个整数的最大公约数。求两个整数的最大公约数。数学建模：辗转相除法是根据递推策略设计的。数学建模：辗转相除法是根据递推策略设计的。不妨设两个整数不

8、妨设两个整数abab且且a a除以除以b b商商x x余余c c；则；则a-bx=ca-bx=c，不难看出，不难看出a a、b b的最大公约数也是的最大公约数也是c c的约数（一个数能整除等式左边就一定能整除的约数（一个数能整除等式左边就一定能整除等式的右边），则等式的右边），则a a、b b的最大公约数与的最大公约数与b b、c c的最大公约数相同。的最大公约数相同。同样方法推出同样方法推出b b、c c的最大公约数与的最大公约数与，直到余数为，直到余数为0 0时，除数即时，除数即为所求的最大公约数。为所求的最大公约数。算法设计：循环算法设计：循环“不变式不变式”第一次是求第一次是求a a、

9、b b相除的余数相除的余数c c，第二，第二次还是求次还是求“a a”“b b” 相除的余数，经相除的余数，经a=b,b=ca=b,b=c操作，就实现了第二次操作，就实现了第二次还是求还是求“a a”“b b” 相除的余数，这就找到了循环不变式。循环在余相除的余数，这就找到了循环不变式。循环在余数数c c为为0 0时结束。时结束。 大连海事大学Design and Analysis of Computer Algorithms大连海事大学算法如下：算法如下：mainmain（）（） int a, b; int a, b; input(a,b); input(a,b); if(b=0) if(b

10、=0) print(“data error”); 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; c=a mod b; print(b); print(b); Design and Analysis of Computer Algorithms4.1.2 4.1.2 倒推法倒推法 大连海事大学 所谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从所谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从 后向前推解问题的方法。如下面的例题，因不同方面的需求而采

11、后向前推解问题的方法。如下面的例题，因不同方面的需求而采用了倒推策略。用了倒推策略。例例1在不知前提条件的情况下，经过从后向前递推，从而求解问在不知前提条件的情况下，经过从后向前递推，从而求解问题。即由结果倒过来推解它的前提条件。又如例题。即由结果倒过来推解它的前提条件。又如例2由于存储的要由于存储的要求，而必须从后向前进行推算。另外，在对一些问题进行分析或求，而必须从后向前进行推算。另外，在对一些问题进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法（如例法（如例3），则问题容易理解和解决。下面分别看这几个例子：），则

12、问题容易理解和解决。下面分别看这几个例子：Design and Analysis of Computer Algorithms大连海事大学【例例1 1】猴子吃桃问题猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第到第1010天时就只有一个桃子了，求原有多少个桃？天时就只有一个桃子了，求原有多少个桃？数 学 模 型 ： 每 天 的 桃 子 数 为 ：数 学 模 型 ： 每 天 的 桃 子 数 为 ： a a1 01 0= 1 , a= 1 , a9 9= ( 1 + a= ( 1 + a1 01 0) ) * * 2 , 2 ,

13、 a a8 8=(1+a=(1+a9 9) )* *2,2,a a1010=1=1， 递推公式为：递推公式为：a ai i=(1+a=(1+ai+1i+1) )* *2 I = 9,8,7,62 I = 9,8,7,61 1算法如下算法如下 ： main( )main( ) int i,s; int 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)； Design and Analysis of Computer Algorithms【例例2 2】

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

15、 11 3 3 11 3 3 11 14 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行行Design and Analysis of Computer Algorithms算法如下：算法如下：main( ) int n,i,j,a100;input(n); print(“1”); print(“换行符换行符”);a1=a2=1;print(a1,a2); print

16、(“换行符换行符”);for (i=3;i1，j=j-1) aj=aj+aj-1; for (j=1;j=i;j=j+1) print(aj); print(“换行符换行符”); 大连海事大学Design and Analysis of Computer Algorithms【例例3 3】穿越沙漠问题穿越沙漠问题 用一辆吉普车穿越用一辆吉普车穿越10001000公里的沙漠。吉普车的总装油量为公里的沙漠。吉普车的总装油量为500500加仑，耗油率为加仑，耗油率为1 1加仑加仑/ /公里。由于沙漠中没有油库，公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少必须先用这辆车

17、在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。油量。 大连海事大学问题分析：问题分析： 1 1）先看一简单问题：有一位探险家用）先看一简单问题：有一位探险家用5 5天的时间徒步天的时间徒步 横穿横穿A A、B B两村，两村间是荒无人烟的沙漠，如果一两村，两村间是荒无人烟的沙漠，如果一 个人只能担负个人只能担负3 3天的食物和水，那么这个探险家至天的食物和水，那么这个探险家至 少雇几个人才能顺利通过沙漠。少雇几个人才能顺利通过沙漠。 Design and Analysis of Computer Al

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

19、二人的行程 大连海事大学2 2）贮油点问题要求要以最少的耗油量穿越沙漠，即到达终）贮油点问题要求要以最少的耗油量穿越沙漠，即到达终 点时，沙漠中的各临时油库和车的装油量均为点时，沙漠中的各临时油库和车的装油量均为0 0。这样只。这样只 能从终点开始向前倒着推解贮油点和贮油量。能从终点开始向前倒着推解贮油点和贮油量。Design and Analysis of Computer Algorithms数学模型：根据耗油量最少目标的分析，下面从后向前分段数学模型：根据耗油量最少目标的分析，下面从后向前分段讨论。讨论。第一段长度为第一段长度为500500公里且第一个加油点贮油为公里且第一个加油点贮油为

20、500500加仑。加仑。第二段中为了贮备油，吉普车在这段的行程必须有往返。下第二段中为了贮备油，吉普车在这段的行程必须有往返。下面讨论怎样走效率高：面讨论怎样走效率高：1 1）首先不计方向这段应走奇数次（保证最后向前走）。）首先不计方向这段应走奇数次（保证最后向前走）。2 2）每次向前行进时吉普车是满载。）每次向前行进时吉普车是满载。3 3）要能贮存够下一加油点的贮油量，路上耗油又最少。）要能贮存够下一加油点的贮油量，路上耗油又最少。大连海事大学Design and Analysis of Computer Algorithms下图是满足以上条件的最佳方案，此段共走下图是满足以上条件的最佳方案

21、，此段共走3 3次：第一、二次：第一、二次来回耗油次来回耗油2/32/3贮油贮油1/31/3，第三次耗油，第三次耗油1/31/3贮油贮油2/32/3，所以第，所以第二个加油点贮油为二个加油点贮油为10001000加仑。由于每公里耗油率为加仑。由于每公里耗油率为1 1加仑，加仑，则此段长度为则此段长度为500/3500/3公里。公里。第三段与第二段思路相同。下图是一最佳方案此段共走第三段与第二段思路相同。下图是一最佳方案此段共走5 5次：次：第一、二次来回耗油第一、二次来回耗油2/52/5贮油贮油3/53/5，第三、四次来回耗油，第三、四次来回耗油2/52/5贮油贮油3/53/5，第五次耗油，第

22、五次耗油1/51/5贮油贮油4/54/5，第三个加油点贮油，第三个加油点贮油为为15001500加仑。此段长度为加仑。此段长度为500/5500/5。 500/5500/5公里公里 第二第二 第三第三 终点终点贮油点（贮油点（500500）贮油点（贮油点（10001000）贮油点（贮油点（15001500）图图4-4 4-4 贮油点及贮油量示意贮油点及贮油量示意大连海事大学Design and Analysis of Computer Algorithms综上分析，从终点开始分别间隔综上分析，从终点开始分别间隔 500500，500/3500/3，500/5500/5，500/7500/7，（

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

24、学Design and Analysis of Computer Algorithmsdesertdesert（ ） int dis int dis，k k，oil,k;oil,k; dis=500;k=1;oil=500; dis=500;k=1;oil=500; do do print(print(“storepointstorepoint”,k,k,”distancedistance”,1000-dis,1000-dis,”oilquantityoilquantity”,oil),oil)； k=k+1;k=k+1; dis=dis+500/(2 dis=dis+500/(2* *k-1

25、);k-1); oil= 500 oil= 500* *k;k; while ( dis1000) while ( dis1000) oil=500*(k-1)+(1000-dis)*( 2*k-1); print(print(“storepointstorepoint”,k,k,”distancedistance”,0,0,”oilquantityoilquantity”,oil),oil)； 大连海事大学Design and Analysis of Computer Algorithms4.1.3 4.1.3 迭代法解方程迭代法解方程迭 代 法 解 方 程 的 实 质迭 代 法 解 方 程

26、 的 实 质 是 按 照 下 列 步 骤 构 造 一 个 序 列是 按 照 下 列 步 骤 构 造 一 个 序 列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)，如此反复迭代，就得到一个数列如此反复迭代，就得到一个数

27、列x0，x1，xn，若这个数列收敛，即存在极值，且函数，若这个数列收敛，即存在极值，且函数(x)连续，则很容易得到这个极限值连续，则很容易得到这个极限值 x*就是方程就是方程f(x)=0的根。的根。 大连海事大学Design and Analysis of Computer Algorithms【例例1 1】迭代法求方程组根迭代法求方程组根算法说明：算法说明：方程组解的初值方程组解的初值X=X=（x0 x0，x1x1，xn-1xn-1）, ,迭代关迭代关系方程组为：系方程组为：xi=gi(X)(i=0,1,n-1),wxi=gi(X)(i=0,1,n-1),w为解的精度为解的精度, ,则则算法

28、算法如下：如下： forfor(i=0;in;i+)(i=0;in;i+)xi=xi=初始近似根初始近似根; ;do k=k+1;do k=k+1; for for(i=0;in;i (i=0;in;i yi=xi;yi=xi; forfor(i=0;in;i+) (i=0;in;i+) xi=gi(X);xi=gi(X); forfor(i=0;in;i+) c=c+fabs(yi-xi)(i=0;iw and kw and kmaxn )；forfor(i=0;in;i+)(i=0;in;i+) print(iprint(i，“变量的近似根是变量的近似根是”，xi)xi)； 大连海事大学D

29、esign and Analysis of Computer Algorithms【例例2 2】牛顿迭代法牛顿迭代法 牛顿迭代法又称为切线法，它比一般的迭代法有更高的收敛速度，牛顿迭代法又称为切线法，它比一般的迭代法有更高的收敛速度，如图如图4-54-5所示。首先所示。首先, , 选择一个接近函数选择一个接近函数f(x)f(x)零点的零点的x0, x0, 计算相应计算相应的的f(x0)f(x0)和切线斜率和切线斜率f f(x0)(x0)（这里（这里f f表示函数表示函数f f的导数）。然后我的导数）。然后我们计算穿过点们计算穿过点(x0,f(x0)(x0,f(x0)且斜率为且斜率为f f(x0

30、)(x0)的直线方程为：的直线方程为：和和x x轴的交点的轴的交点的x x坐标坐标, , 也就是求如下方程的解：也就是求如下方程的解：大连海事大学)()(000 xxxfxfy0000)()(xxxfxf图图4-5 4-5 牛顿迭代法牛顿迭代法示意图示意图Design and Analysis of Computer Algorithms迭代公式可化简为：迭代公式可化简为：此公式就是有名的牛顿迭代公式此公式就是有名的牛顿迭代公式。已经证明。已经证明, , 如果如果f f是连是连续的续的, , 并且待求的零点并且待求的零点x x是孤立的是孤立的, , 那么在零点那么在零点x x周围存在周围存在一

31、个区域一个区域, , 只要初始值只要初始值x0 x0位于这个邻近区域内位于这个邻近区域内, , 那么牛顿那么牛顿法必定收敛。法必定收敛。 下面给出用牛顿迭代法，求形如下面给出用牛顿迭代法，求形如ax3+bx2+cx+d=0方程方程根的算法，系数根的算法，系数a、b、c、d的值依次为的值依次为1、2、3、4，由，由主函数输入。求主函数输入。求x在在1附近的一个实根。求出根后由主函数输附近的一个实根。求出根后由主函数输出。出。 大连海事大学Design and Analysis of Computer Algorithmsmain( ) float a , b, c, d, fx; p r i n

32、 t ( 输 入 系 数输 入 系 数 a,b,c,d:); input(a,b,c,d); fx=f(a,b,c,d); printf(方程的根为：方程的根为：,fx);大连海事大学Design and Analysis of Computer Algorithms 令令a0,b0=a,ba0,b0=a,b，c0=(a0+b0)/2c0=(a0+b0)/2，若，若f(c0)=0f(c0)=0，则，则c0c0为方为方程程 f ( x ) = 0f ( x ) = 0 的 根 ； 否 则 ， 若的 根 ； 否 则 ， 若 f ( a 0 )f ( a 0 ) 与与 f ( c 0 )f ( c

33、0 ) 异 号 ， 即异 号 ， 即 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时，就认为找到了方程的根。时，就认为找到了方程的根。 用二分法求一元非线性方程用二分法求一元非线性方程f(x)= x3/2+2x2-8=0（其

34、中（其中表示幂运算）在区间表示幂运算）在区间0，2上的近似实根上的近似实根r，精确到，精确到0.0001.算法如下：算法如下：大连海事大学图图4-6 4-6 二分法二分法求求解解方程方程示意示意Design and Analysis of Computer Algorithmsmain( )main( ) float x,x1=0,x2=2,f1,f2,f; float x,x1=0,x2=2,f1,f2,f; print( print(“input a,b (f(a)input a,b (f(a)* *f(b)0)f(b)0) printf(No root); return;f20) pri

35、ntf(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(fabs(f)=1e-4);while(fabs(f)=1e-4);print(root=,x); prin

36、t(root=,x); 大连海事大学Design and Analysis of Computer Algorithms4.2 蛮力法蛮力法4.2.1 4.2.1 枚举法枚举法4.2.2 4.2.2 其它范例其它范例大连海事大学 蛮力法是基于计算机运算速度快这一特性，在解决问题时采蛮力法是基于计算机运算速度快这一特性，在解决问题时采取的一种取的一种“ “懒惰懒惰” ”的策略。这种策略不经过（或者说是经过很少的）的策略。这种策略不经过（或者说是经过很少的）思考，把问题的所有情况或所有过程交给计算机去一一尝试，从思考，把问题的所有情况或所有过程交给计算机去一一尝试，从中找出问题的解。蛮力策略的应用

37、很广，具体表现形式各异，数中找出问题的解。蛮力策略的应用很广，具体表现形式各异，数据结构课程中学习的：选择排序、冒泡排序、插入排序、顺序查据结构课程中学习的：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等，都是蛮力策略具体应用。比较常用还找、朴素的字符串匹配等，都是蛮力策略具体应用。比较常用还有有枚举法枚举法、盲目搜索算法等，本节介绍、盲目搜索算法等，本节介绍枚举法枚举法和其它一些小的范和其它一些小的范例，第五章介绍盲目搜索算法。例，第五章介绍盲目搜索算法。Design and Analysis of Computer Algorithms4 42 21 1 枚举法枚举法 大连海事

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

39、能解的列举数目。用枚举法解决问题，通常可以从两个方面进行算法设计：用枚举法解决问题，通常可以从两个方面进行算法设计： 1）找出枚举范围：分析问题所涉及的各种情况。找出枚举范围：分析问题所涉及的各种情况。 2 2）找出约束条件：分析问题的解需要满足的条件，并用逻辑）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。表达式表示。Design and Analysis of Computer Algorithms大连海事大学【例例1 1】百钱百鸡问题。中国古代数学家张丘建在他的百钱百鸡问题。中国古代数学家张丘建在他的算经算经中提出了著名的中提出了著名的“百钱百鸡问题百钱百鸡问题”：鸡翁一

40、，值钱五；鸡母一，：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何? ?算法设计算法设计1：通过对问题的理解，读者可能会想到列出两个三元一次方程，通过对问题的理解，读者可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用但这里我们要用“懒惰懒惰”的枚举策略进行算法设计：的枚举策略进行算法设计： 设设x，y，z分别为公鸡、母鸡、小鸡的数量。分别为公鸡、母鸡、小鸡的数量。 尝试范围：由尝试范围：由题意给定共题意给

41、定共100钱要买百鸡，若全买公鸡最多钱要买百鸡，若全买公鸡最多买买100/5=100/5=20只，显然只，显然x的取值范围的取值范围120之间；同理，之间；同理，y的取值范的取值范围在围在133之间，之间，z z的取值范围的取值范围在在11001100之间之间。 约束条件：约束条件： x+y+z=100 x+y+z=100 且且 5 5* *x+3x+3* *y+z/3=100y+z/3=100 Design and Analysis of Computer Algorithms大连海事大学算法算法1如下：如下：main( )main( ) int x,y,z; int x,y,z;for(x

42、=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) print(the cock number is,x)print(the cock number is,x)； print(the hen number is, y)print(the hen number is, y)；pri

43、nt(the chick number is z);print(the chick number is z); Design and Analysis of Computer Algorithms大连海事大学算法分析：以上算法需要枚举尝试算法分析：以上算法需要枚举尝试20*34*100=68000次。次。算法的效率显然太低算法的效率显然太低算法设计算法设计2：在公鸡（在公鸡（x x）、母鸡（）、母鸡（y y）的数量确定后，小鸡）的数量确定后，小鸡的数量的数量z就固就固定为定为100-x-y，无需再进行枚举了，无需再进行枚举了此时此时约束条件只有一个：约束条件只有一个： 5*x+3*y+z/3=

44、100算法算法2如下：如下： Design and Analysis of Computer Algorithmsmain( )main( ) int x,y,z; int 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 5if(z mod 3=0 and 5* *x+3x+3* *y+z/3=100)y+z/3=100)print(the cock number is,x)print(the coc

45、k 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=100y+z/3=100”。这。这样省去了样省去了z z不整除不整除3 3时的算术计算和条件时的算术计算和条件判断，判断，

46、进一步提高了算法进一步提高了算法的效率。的效率。 大连海事大学Design and Analysis of Computer Algorithms【例例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+

47、A* *10+B10+B， 共尝试共尝试800800次。次。2)2)约束条件为：约束条件为： 每次尝试，先求六位数与每次尝试，先求六位数与A A的积，再测试积的各位是否相的积，再测试积的各位是否相 同，若相同则找到了问题的解。同，若相同则找到了问题的解。 测试积的各位是否相同比较简单的方法是，从低位开始，测试积的各位是否相同比较简单的方法是，从低位开始， 每次都取数据的个位，然后整除每次都取数据的个位，然后整除1010，使高位的数字不断变，使高位的数字不断变 成个位，并逐一比较。成个位，并逐一比较。 大连海事大学Design and Analysis of Computer Algorithm

48、s算法算法1 1如下：如下：main（ ） int A,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=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); 大连海事大学Design and Analysis of Computer Al

49、gorithms大连海事大学算法中对枚举出的每一个五位数与算法中对枚举出的每一个五位数与A A相乘，结果相乘，结果存储在变量存储在变量E E中。然后，测试得到的六位数中。然后，测试得到的六位数E E是否各个位的数是否各个位的数字都相同。鉴于要输出结果，所以不要改变计算结果，而另字都相同。鉴于要输出结果，所以不要改变计算结果，而另设变量设变量E1E1，用于测试运算。，用于测试运算。算法设计算法设计2 2：将算式变形为除法：将算式变形为除法：DDDDDD/A=ABCABDDDDDD/A=ABCAB。此时。此时只需枚举只需枚举A A：3 39 D9 D：1 19 9，共尝试，共尝试7 7* *9=6

50、39=63次。每次次。每次尝试，测试商的万位、十位与除数是否相同，千位与个位尝试，测试商的万位、十位与除数是否相同，千位与个位是否相同，都相同时为解。是否相同，都相同时为解。算法算法2 2如下如下: :Design and Analysis of Computer Algorithms大连海事大学mainmain（）（）int A,B,C,D,E,F;int 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+D10

51、000+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 mod 10) if(F1000=F mod 10) print( F print( F，”* *”，A A，”=”=”，E);E); Design and Analysis of Computer Algorithms4 42 22 2 其它范例其它范例大连海事大学 蛮

52、力法的表现形式非常多，如第三章蛮力法的表现形式非常多，如第三章3.2.4例题、例题、3.2.5例例1及本章下一节及本章下一节4.3.3例例4的算法的算法1等。本节将通过蛮力策略，用等。本节将通过蛮力策略，用算法模拟问题中所描述的全部过程和全部状态，来找出问题的解，算法模拟问题中所描述的全部过程和全部状态，来找出问题的解，并与经过数学建模后的算法进行效率上的比较。并与经过数学建模后的算法进行效率上的比较。Design and Analysis of Computer Algorithms【例例3 3】狱吏问题狱吏问题 某国王对囚犯进行大赦，让一狱吏某国王对囚犯进行大赦，让一狱吏n n次通过一排锁

53、着的次通过一排锁着的n n间牢房，每通过一次，按所定规则转动间牢房，每通过一次，按所定规则转动n n间牢房中的某些门间牢房中的某些门锁锁, , 每转动一次每转动一次, , 原来锁着的被打开原来锁着的被打开, , 原来打开的被锁上；原来打开的被锁上；通过通过n n次后，门锁开着的，牢房中的犯人放出，否则犯人不次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。得获释。 转动门锁的规则是这样的，第一次通过牢房，要转动每转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；

54、第开始转动，每隔一间转动一次；第k k次通过牢房，从第次通过牢房，从第k k间开间开始转动，每隔始转动，每隔k-1 k-1 间转动一次；问通过间转动一次；问通过n n次后，那些牢房的次后，那些牢房的锁仍然是打开的？锁仍然是打开的？大连海事大学Design and Analysis of Computer Algorithms算法设计算法设计1 1：1 1）用用n n个空间的一维数组个空间的一维数组an,an,每个元素每个元素记录一个锁的状记录一个锁的状 态，态，1 1为为被锁上，被锁上，0 0为被打开。为被打开。2 2）用数学运算方便模拟开关锁的技巧，对）用数学运算方便模拟开关锁的技巧，对i

55、i号锁的一次开号锁的一次开 关锁可以转化为算术运算：关锁可以转化为算术运算：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）不做其它的优化，用蛮力法通过循环模拟狱吏的开关）不做其它的优化，用蛮力法通过循环模拟狱吏的开关 锁过程，最

56、后当第锁过程，最后当第i号牢房对应的数组元素号牢房对应的数组元素aiai为为0 0时，时， 该牢房的囚犯得到大赦。算法该牢房的囚犯得到大赦。算法1如下：如下： 大连海事大学Design and Analysis of Computer Algorithmsmain1( )main1( )int int * *a,i,j,n;a,i,j,n; input(n); input(n); a=calloc(n+1,sizeof(int); a=calloc(n+1,sizeof(int); for (i=1; i=n;i+) for (i=1; i=n;i+) ai=1; ai=1; for (i=1

57、; 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, if (ai=0) print(i,”is free.is free.”);); 算法分析：算法分析：以一次开关锁计算，算法的时间复杂度为以一次开关锁计算，算法的时间复杂度为n(1+1/2+1/3+n(1+1/2+1/3+1/n)=O(nlogn)+1/n)=O(nlogn)。大连海事大学Design and Analysis of Computer Algorithms问题分析：问题分析：转动门锁的规则可以有另一种理解，第一次转动转动门锁的规则可以有另一种理解，第一次转动的是编号为的是编号为1 1的倍数的牢房；第二次转动的是编号为的倍数的牢房；第二次转动的是编号为2 2的倍的倍数的牢房；第三次转动的是编号为数的牢房；第三次转动的是编号为3 3的倍数的牢房；的倍数的牢房；则则狱吏问题是一个关于因子个数的狱吏问题是一个关于因子个数的问题。令问题。令d(n)d(n)为自然数为自然数n n的因子个数，这里不计重复的因子，如的因子个数，这里不计重复的因子，如4 4的因子为的因子为1 1，2