算法策略课件

算法策略第四章第四章 基本的算法策略基本的算法策略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】兔子繁殖问题】兔子繁殖问题问题描述：问题描述：一对兔子从出生后第三个月开始，每月生一对小兔一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。个月各有多少只兔子。问题分析：问题分析：因一对兔子从出生后第三个月开始每月生一对小兔因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数子，则每月新下小兔子的对儿数(用斜体数字表示用斜体数字表示)显然由前显然由前两个月的小兔子的对儿数决定。则繁殖过程如下：两个月的小兔子的对儿数决定。则繁殖过程如下： 一月一月 二月二月 三月三月 四月四月 五月五月 六月六月 1 1 1+1=2 2+1=3 3+2=5 5+3=8 算法策略算法算法1 1： 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=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，。算法策略算法算法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+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; 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 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;”做循环做循环“不变式不变式”，从而得到以下算法从而得到以下算法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); 算法策略【例【例2 2】求两个整数的最大公约数。求两个整数的最大公约数。数学建模：数学建模：辗转相除法是根据递推策略设计的。辗转相除法是根据递推策略设计的。不妨设两个整数不妨设两个整数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、b b相除的余数相除的余数c c，第二第二次次还是求还是求“a”“b” a”“b” 相除的余数，经相除的余数，经a=b,b=ca=b,b=c操作，就实现了第操作，就实现了第二次还是求二次还是求“a”“b” a”“b” 相除的余数，这就找到了循环不变式。循相除的余数，这就找到了循环不变式。循环在余数环在余数c c为为0 0时结束。时结束。 算法策略算法如下：算法如下：mainmain（）（） int a, b; int 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=c; b=c; c=a mod b; c=a mod b; print(b); print(b); 算法策略4.1.2 4.1.2 倒推法倒推法 所谓所谓倒推法倒推法：是对某些特殊问题所采用的违反通常习惯的，从：是对某些特殊问题所采用的违反通常习惯的，从 后向前推解问题的方法。如下面的例题，因不同方面的需求而采后向前推解问题的方法。如下面的例题，因不同方面的需求而采用了倒推策略。用了倒推策略。例例1在不知前提条件的情况下，经过从后向前递推，从而求解问在不知前提条件的情况下，经过从后向前递推，从而求解问题。即由结果倒过来推解它的前提条件。又如例题。即由结果倒过来推解它的前提条件。又如例2由于存储的要由于存储的要求，而必须从后向前进行推算。另外，在对一些问题进行分析或求，而必须从后向前进行推算。另外，在对一些问题进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法（如例法（如例3），则问题容易理解和解决。下面分别看这几个例子：），则问题容易理解和解决。下面分别看这几个例子：算法策略【例【例1 1】猴子吃桃问题猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第到第1010天时就只有一个桃子了，求原有多少个桃？天时就只有一个桃子了，求原有多少个桃？数学模型：数学模型：每天的桃子数为：每天的桃子数为：a10=1, a9=(1+a10)a10=1, a9=(1+a10)* *2, 2, a8=(1+a9)a8=(1+a9)* *2,a10=12,a10=1， 递推公式为：递推公式为：ai=(1+ai+1)ai=(1+ai+1)* *2 I = 9,8,7,612 I = 9,8,7,61算法如下算法如下 ： 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)； 算法策略【例【例2 2】 输出如图输出如图4-14-1的杨辉三角形（限的杨辉三角形（限定用一个一维数组完成）。定用一个一维数组完成）。数学模型：数学模型：上下层规律较明显，中间的数上下层规律较明显，中间的数等于上行左上、右上两数之和。等于上行左上、右上两数之和。问题分析：问题分析：题目中要求用一个一维数组即题目中要求用一个一维数组即完成。数组空间一定是由下标从小到大完成。数组空间一定是由下标从小到大利用的，这样其实杨辉三角形是按下图利用的，这样其实杨辉三角形是按下图4-24-2形式存储的。若求形式存储的。若求n n层，则数组最多层，则数组最多存储存储n n个数据。个数据。1 11 11 11 2 11 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-1; for (j=1;j=i;j=j+1) print(aj); print(“换行符换行符”); 算法策略【例【例3 3】穿越沙漠问题穿越沙漠问题 用一辆吉普车穿越用一辆吉普车穿越10001000公里的沙漠。吉普车的总装油量为公里的沙漠。吉普车的总装油量为500500加仑，耗油率为加仑，耗油率为1 1加仑加仑/ /公里。由于沙漠中没有油库，公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。油量。 问题分析：问题分析： 1 1）先看一简单问题：有一位探险家用先看一简单问题：有一位探险家用5 5天的时间徒步天的时间徒步 横穿横穿A A、B B两村，两村间是荒无人烟的沙漠，如果一两村，两村间是荒无人烟的沙漠，如果一 个人只能担负个人只能担负3 3天的食物和水，那么这个探险家至天的食物和水，那么这个探险家至 少雇几个人才能顺利通过沙漠。少雇几个人才能顺利通过沙漠。 算法策略 A A城雇用一人与探险家同带城雇用一人与探险家同带3 3天食物同行一天，然后被雇天食物同行一天，然后被雇 人带一天食物返回，并留一天食物给探险家，这样探险人带一天食物返回，并留一天食物给探险家，这样探险 家正好有家正好有3 3天的食物继续前行，并于第三天打电话雇天的食物继续前行，并于第三天打电话雇B B城城 人带人带3 3天食物出发，第四天会面他们会面，探险家得到一天食物出发，第四天会面他们会面，探险家得到一 天的食物赴天的食物赴B B城。如图城。如图4-34-3主要表示了被雇用二人的行程。主要表示了被雇用二人的行程。 A BA B 图图4-3 4-3 被雇用二人的行程被雇用二人的行程 2 2）贮油点问题要求要以最少的耗油量穿越沙漠，即到达终贮油点问题要求要以最少的耗油量穿越沙漠，即到达终 点时，沙漠中的各临时油库和车的装油量均为点时，沙漠中的各临时油库和车的装油量均为0 0。这样只。这样只 能从终点开始向前倒着推解贮油点和贮油量。能从终点开始向前倒着推解贮油点和贮油量。算法策略数学模型：数学模型：根据耗油量最少目标的分析，下面从后向前分段根据耗油量最少目标的分析，下面从后向前分段讨论。讨论。第一段长度为第一段长度为500500公里且第一个加油点贮油为公里且第一个加油点贮油为500500加仑。加仑。第二段中为了贮备油，吉普车在这段的行程必须有往返。第二段中为了贮备油，吉普车在这段的行程必须有往返。下下面讨论怎样走效率高：面讨论怎样走效率高：1 1）首先不计方向这段应走奇数次（保证最后向前走）。首先不计方向这段应走奇数次（保证最后向前走）。2 2）每次向前行进时吉普车是满载。每次向前行进时吉普车是满载。3 3）要能贮存够下一加油点的贮油量，路上耗油又最少。要能贮存够下一加油点的贮油量，路上耗油又最少。算法策略下图是满足以上条件的最佳方案，此段共走下图是满足以上条件的最佳方案，此段共走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，第五次耗油，第五次耗油1/51/5贮油贮油4/54/5，第三个加油点贮油，第三个加油点贮油为为15001500加仑。此段长度为加仑。此段长度为500/5500/5。 500/5500/5公里公里 第二第二 第三第三 终点终点贮油点（贮油点（500500）贮油点（贮油点（10001000）贮油点（贮油点（15001500）图图4-4 4-4 贮油点及贮油量示意贮油点及贮油量示意算法策略综上分析综上分析，从终点开始分别间隔，从终点开始分别间隔 500500，500/3500/3，500/5500/5，500/7500/7，（公里）设立贮油点，直到总距离超过（公里）设立贮油点，直到总距离超过10001000公里。每个贮油点的油量为公里。每个贮油点的油量为500500，10001000，15001500，。 算法设计：算法设计：由模型知道此问题并不必用倒推算法解决（只由模型知道此问题并不必用倒推算法解决（只是分析过程用的是倒推法），只需通过累加算法就能解决。是分析过程用的是倒推法），只需通过累加算法就能解决。变量说明：变量说明：disdis表示距终点的距离，表示距终点的距离，1000- dis1000- dis则表示距起则表示距起点的距离，点的距离，k k表示贮油点从后到前的序号。表示贮油点从后到前的序号。算法策略desertdesert（ ） int dis int dis，k k，oil,k;oil,k; dis=500;k=1;oil=500; dis=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,”oilquantity”,oil)dis,”oilquantity”,oil)； k=k+1;k=k+1; dis=dis+500/(2 dis=dis+500/(2* *k-1);k-1); oil= 500 oil= 500* *k;k; while ( dis1000) while ( dis1000) oil=500*(k-1)+(1000-dis)*( 2*k-1); print(“storepoint”,k,”distance”,0,”oilquantity”,oil)print(“storepoint”,k,”distance”,0,”oilquantity”,oil)； 算法策略4.1.3 4.1.3 迭代法解方程迭代法解方程迭 代 法 解 方 程 的 实 质迭 代 法 解 方 程 的 实 质 是 按 照 下 列 步 骤 构 造 一 个 序 列是 按 照 下 列 步 骤 构 造 一 个 序 列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)，如此反复迭代，就得到一个数列如此反复迭代，就得到一个数列x0， x1，xn，若这个数列收敛，即存在极值，且函数，若这个数列收敛，即存在极值，且函数 (x)连续，则很容易得到这个极限值连续，则很容易得到这个极限值 x*就是方程就是方程f(x)=0的根。的根。 算法策略【例【例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为解的精度为解的精度, ,则则算法如下：算法如下： for (i=0;in;i+)for (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(X); for (i=0;in;i+) xi=gi(X); for (i=0;in;i+) c=c+fabs(yi-xi) 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】牛顿迭代法】牛顿迭代法 牛顿迭代法又称为切线法，它比一般的迭代法有更高的收敛速度，牛顿迭代法又称为切线法，它比一般的迭代法有更高的收敛速度，如图如图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坐标坐标, , 也就是求如下方程的解：也就是求如下方程的解：)()(000 xxxfxfy0000)()(xxxfxf图图4-5 4-5 牛顿迭代法牛顿迭代法 示意图示意图算法策略迭代公式可化简为：迭代公式可化简为：此公式就是有名的牛顿迭代公式此公式就是有名的牛顿迭代公式。已经证明。已经证明, , 如果如果ff是连是连续的续的, , 并且待求的零点并且待求的零点x x是孤立的是孤立的, , 那么在零点那么在零点x x周围存在周围存在一个区域一个区域, , 只要初始值只要初始值x0 x0位于这个邻近区域内位于这个邻近区域内, , 那么牛顿那么牛顿法必定收敛。法必定收敛。 下面给出用牛顿迭代法，求形如下面给出用牛顿迭代法，求形如ax3+bx2+cx+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)=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时，就认为找到了方程的根。时，就认为找到了方程的根。 用二分法求一元非线性方程用二分法求一元非线性方程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) printf(No root); return;f20) printf(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); print(root=,x); 算法策略4.2 蛮力法蛮力法4.2.1 4.2.1 枚举法枚举法4.2.2 4.2.2 其它范例其它范例 蛮力法蛮力法是基于计算机运算速度快这一特性，在解决问题时采是基于计算机运算速度快这一特性，在解决问题时采取的一种取的一种“ “懒惰懒惰” ”的策略。这种策略不经过（或者说是经过很少的）的策略。这种策略不经过（或者说是经过很少的）思考，把问题的所有情况或所有过程交给计算机去一一尝试，从思考，把问题的所有情况或所有过程交给计算机去一一尝试，从中找出问题的解。蛮力策略的应用很广，具体表现形式各异，数中找出问题的解。蛮力策略的应用很广，具体表现形式各异，数据结构课程中学习的：选择排序、冒泡排序、插入排序、顺序查据结构课程中学习的：选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等，都是蛮力策略具体应用。比较常用还找、朴素的字符串匹配等，都是蛮力策略具体应用。比较常用还有有枚举法枚举法、盲目搜索算法等，本节介绍、盲目搜索算法等，本节介绍枚举法枚举法和其它一些小的范和其它一些小的范例，第五章介绍盲目搜索算法。例，第五章介绍盲目搜索算法。 算法策略4 42 21 1 枚举法枚举法 枚举枚举（ enumerate）法（穷举法）是蛮力策略的一种表现形式，）法（穷举法）是蛮力策略的一种表现形式，也是一种使用非常普遍的思维方法。它是根据问题中的条件将可能也是一种使用非常普遍的思维方法。它是根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。可能解的列举数目。用枚举法解决问题，通常可以从两个方面进行算法设计：用枚举法解决问题，通常可以从两个方面进行算法设计： 1）找出枚举范围：分析问题所涉及的各种情况。找出枚举范围：分析问题所涉及的各种情况。 2 2）找出约束条件：分析问题的解需要满足的条件，并用逻辑）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。表达式表示。算法策略【例【例1 1】百钱百鸡问题。中国古代数学家张丘建在他的百钱百鸡问题。中国古代数学家张丘建在他的算经算经中提出了著名的中提出了著名的“百钱百鸡问题百钱百鸡问题”：鸡翁一，值钱五；鸡母一，：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何? ?算法设计算法设计1：通过对问题的理解，读者可能会想到列出两个三元一次方程，通过对问题的理解，读者可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用但这里我们要用“懒惰懒惰”的枚举策略进行算法设计：的枚举策略进行算法设计： 设设x，y，z分别为公鸡、母鸡、小鸡的数量。分别为公鸡、母鸡、小鸡的数量。 尝试范围：由尝试范围：由题意给定共题意给定共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 算法策略算法算法1如下：如下： main( )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=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)；print(the chick number is z);print(the chick number is z); 算法策略算法分析算法分析：以上算法需要枚举尝试：以上算法需要枚举尝试20*34*100=68000次。次。算法的效率显然太低算法的效率显然太低算法设计算法设计2：在公鸡（在公鸡（x x）、母鸡（）、母鸡（y y）的数量确定后，小鸡）的数量确定后，小鸡 的数量的数量 z就固就固定为定为100-x-y，无需再进行枚举了，无需再进行枚举了 此时此时约束条件只有一个：约束条件只有一个： 5*x+3*y+z/3=100 算法算法2如下：如下： 算法策略main( )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 if(z mod 3=0 and 5 5* *x+3x+3* *y+z/3=100) y+z/3=100) 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*33=660次。实现时约次。实现时约束条件又限定束条件又限定Z能被能被3整除时，才会判断整除时，才会判断“5 5* *x+3x+3* *y+z/3=100”y+z/3=100”。这样省去了这样省去了z z不整除不整除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 A* *10000+B10000+B* *1000+C1000+C* *100+A100+A* *10+B10+B， 共尝试共尝试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; 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是否各个位的数是否各个位的数字都相同。鉴于要输出结果，所以不要改变计算结果，而另字都相同。鉴于要输出结果，所以不要改变计算结果，而另设变量设变量E1E1，用于测试运算。，用于测试运算。算法设计算法设计2 2：将算式变形为除法：将算式变形为除法：DDDDDD/A=ABCABDDDDDD/A=ABCAB。此时。此时只需枚举只需枚举A A：39 D39 D：1919，共尝试，共尝试7 7* *9=639=63次。每次次。每次尝试，测试商的万位、十位与除数是否相同，千位与个位尝试，测试商的万位、十位与除数是否相同，千位与个位是否相同，都相同时为解。是否相同，都相同时为解。算法算法2 2如下如下: :算法策略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+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 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】狱吏问题狱吏问题 某国王对囚犯进行大赦，让一狱吏某国王对囚犯进行大赦，让一狱吏n n次通过一排锁着的次通过一排锁着的n n间牢房，每通过一次，按所定规则转动间牢房，每通过一次，按所定规则转动n n间牢房中的某些门间牢房中的某些门锁锁, , 每转动一次每转动一次, , 原来锁着的被打开原来锁着的被打开, , 原来打开的被锁上；原来打开的被锁上；通过通过n n次后，门锁开着的，牢房中的犯人放出，否则犯人不次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。得获释。 转动门锁的规则是这样的，第一次通过牢房，要转动每转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第开始转动，每隔一间转动一次；第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号锁的一次开号锁的一次开 关锁可以转化为算术运算：关锁可以转化为算术运算：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）不做其它的优化，用蛮力法通过循环模拟狱吏的开关）不做其它的优化，用蛮力法通过循环模拟狱吏的开关 锁过程，最后当第锁过程，最后当第i号牢房对应的数组元素号牢房对应的数组元素aiai为为0 0时，时， 该牢房的囚犯得到大赦。算法该牢房的囚犯得到大赦。算法1如下：如下： 算法策略main1( )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; 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(i,”is free.”); 算法分析：算法分析：以一次开关锁计算，算法的时间复杂度为以一次开关锁计算，算法的时间复杂度为n(1+1/2+1/3+1/n)=O(nlogn)n(1+1/2+1/3+1/n)=O(nlogn)。算法策略问题分析：问题分析：转动门锁的规则可以有另一种理解，第一次转动转动门锁的规则可以有另一种理解，第一次转动的是编号为的是编号为1 1的倍数的牢房；第二次转动的是编号为的倍数的牢房；第二次转动的是编号为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 编号与因数个数的关系编号与因数个数的关系 n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 d(n) 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 d(n) 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 数学模型数学模型1 1：上表中的上表中的d(n)d(n)有的为奇数，有的为偶数，有的为奇数，有的为偶数，由于由于牢房的门开始是关着的，这样编号为牢房的门开始是关着的，这样编号为i i的牢房，所含的牢房，所含11i i之间的不重复因子个数为奇数时，牢房最后是打开的，之间的不重复因子个数为奇数时，牢房最后是打开的，反之，牢房最后是关闭的。反之，牢房最后是关闭的。算法策略算法设计算法设计2:2:1 1）算法应该是求出每个牢房编号的不重复的因子个数，当它）算法应该是求出每个牢房编号的不重复的因子个数，当它为奇数时，这里边的囚犯得到大赦。为奇数时，这里边的囚犯得到大赦。2 2）一个数的因子是没有规律的，只能从）一个数的因子是没有规律的，只能从1n1n枚举尝试。算枚举尝试。算法法2 2如下：如下：main2( )main2( )int s,i,j,n;int 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） print(i,”is free.”); print(i,”is free.”); 算法策略算法分析：算法分析： 狱吏开关锁的主要操作是狱吏开关锁的主要操作是ai=1- ai;ai=1- ai;共执行了共执行了n n* *(1+1/2+1/3+1/n)(1+1/2+1/3+1/n)次，时间近似为复杂度为次，时间近似为复杂度为O（n log n）。使用了）。使用了n n个空间的一维数组。算法个空间的一维数组。算法2 2没有使用辅助没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其空间，但由于求一个编号的因子个数也很复杂，其主要操主要操作是判断作是判断i mod ji mod j是否为是否为0 0，共执行了，共执行了n n* *(1+2+3+n)(1+2+3+n)次，时间复杂度为次，时间复杂度为O O（n n2 2）。）。 数学模型数学模型2 2：仔细观察表：仔细观察表4-34-3，发现当且仅当，发现当且仅当n n为完为完全平方数时全平方数时,d(n),d(n)为奇数；这是因为为奇数；这是因为n n的因子是成的因子是成对出现的对出现的, ,也即当也即当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( )int s,i,j,n;int 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） print(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算法设计思想算法设计思想分治法求解问题的过程是，将整个问题分解成若干个小问题后分分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。题的解。分治法的基本步骤在每一层递归上都有三个步骤：分治法的基本步骤在每一层递归上都有三个步骤：1）分解：将原问题分解为若干个规模较小，相互独立，与原问）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；题形式相同的子问题； 2）解决：若子问题规模较小而容易被解决则直接解，否则再）解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；继续分解为更小的子问题，直到容易解决； 3）合并：将已求解的各个子问题的解，逐步合并为原问题的）合并：将已求解的各个子问题的解，逐步合并为原问题的解。解。算法策略有时问题分解后，不必求解所有的子问题，也就不必作第三步有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中的操作。比如折半查找，在判别出问题的解在某一个子问题中后，其它的子问题就不必求解了，问题的解就是最后（最小）后，其它的子问题就不必求解了，问题的解就是最后（最小）的子问题的解。分治法的这类应用，又称为的子问题的解。分治法的这类应用，又称为“减治法减治法”。 多数问题需要所有子问题的解，并由子问题的解，使用恰多数问题需要所有子问题的解，并由子问题的解，使用恰当的方法合并成为整个问题的解，比如合并排序，就是不断将当的方法合并成为整个问题的解，比如合并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。子问题中已排好序的解合并成较大规模的有序子集。 算法策略2适合用分治法策略的问题适合用分治法策略的问题当求解一个输入规模为当求解一个输入规模为n且取值又相当大的问题时，用蛮力策且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。治法来提高解决问题的效率。1） 能将这能将这n个数据分解成个数据分解成k个不同子集合，且得到个不同子集合，且得到k个子集合个子集合是可以独立求解的子问题，其中是可以独立求解的子问题，其中1kn；2） 分解所得到的子问题与原问题具有相似的结构，便于利分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；用递归或循环机制；在求出这些子问题的解之后，就可以推解出原问题的解；在求出这些子问题的解之后，就可以推解出原问题的解； 算法策略分治法的一般的算法设计模式如下：分治法的一般的算法设计模式如下：Divide-and-Conquer(int n) /nDivide-and-Conquer(int n) /n为问题规模为问题规模/ / if if （nn0nn0） /n0 /n0 为可解子问题的规模为可解子问题的规模/ / 解子问题；解子问题； return(return(子问题的解子问题的解) )； for for （i=1 ;i=k;i+i=1 ;i=k;i+） / /分解为较小子问题分解为较小子问题p1,p2,pk/p1,p2,pk/ yi=Divide-and-Conquer(|Pi|); / yi=Divide-and-Conquer(|Pi|); /递归解决递归解决Pi/Pi/ T =MERGE(y1,y2,.,yk); / T =MERGE(y1,y2,.,yk); /合并子问题合并子问题/ / return(T); return(T); 其中其中|P|P|表示问题表示问题P P的规模；的规模；n0n0为一阈值，表示当问题为一阈值，表示当问题P P的规的规模不超过模不超过n0n0时，问题已容易直接解出，不必再继续分解。算法时，问题已容易直接解出，不必再继续分解。算法MERGE(y1,y2,.,yk)MERGE(y1,y2,.,yk)是该分治法中的合并子算法，用于将是该分治法中的合并子算法，用于将P P的的子问题子问题P1 ,P2 ,.,PkP1 ,P2 ,.,Pk的相应的解的相应的解y1,y2,.,yky1,y2,.,yk合并为合并为P P的解。的解。在一些问题中不需要这一步。如析半查找、在一些问题中不需要这一步。如析半查找、4 43 32 2中的例中的例1 1、例、例2 2等。等。算法策略432 二分法二分法 不同于现实中对问题（或工作）的分解，可能会考虑问题不同于现实中对问题（或工作）的分解，可能会考虑问题（或工作）的重点、难点、承担人员的能力等来进行问题的分（或工作）的重点、难点、承担人员的能力等来进行问题的分解和分配。在算法设计中每次一个问题分解成的子问题个数一解和分配。在算法设计中每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。当每次都将般是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解策略，数据结构课程中的折半查找、归并排序法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。等算法都是采用此策略实现的。算法策略【例【例1 1】金块问题：】金块问题： 老板有一袋金块老板有一袋金块( (共共n n块块) )，最优秀的雇员得，最优秀的雇员得到其中最重的一块