第四章算法策略精选文档.ppt

《第四章算法策略精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章算法策略精选文档.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章算法策略本讲稿第一页，共八十二页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：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+)=1

3、0;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

4、+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+3*42+3*4共共1414项。项。本讲稿第五页，共八十二页 表表4-2 4-2 递推迭

5、代表达式递推迭代表达式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;

6、b=a+b;print(a,b);算法算法算法算法3 3 3 3：本讲稿第六页，共八十二页【例例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的的最最大大公公约约数

7、数相相同同。同同样样方方法法推推出出b b、c c的的最最大大公约数与公约数与，直到余数为，直到余数为0 0时，除数即为所求的最大公约数。时，除数即为所求的最大公约数。算算法法设设计计：循循环环“不不变变式式”第第一一次次是是求求a a、b b相相除除的的余余数数c c，第第二二次次还还是是求求“a a”“b b”相相除除的的余余数数，经经a=b,b=ca=b,b=c操操作作，就就实实现现了了第第二二次次还还是是求求“a a”“b b”相除的余数，这就找到了循环不变式。循环在余数相除的余数，这就找到了循环不变式。循环在余数c c为为0 0时结束。时结束。本讲稿第七页，共八十二页算法如下：算法如

8、下：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 倒推法倒推法 所所谓谓倒倒推推法法：是是对对某某些些特特殊殊问问题题所所采采用用的的违违反反通通常常习习惯惯的的，从从 后后向向前前推推解解问问题题的的方方法法。

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

10、个例子：分别看这几个例子：本讲稿第九页，共八十二页【例例1 1】猴子吃桃问题猴子吃桃问题一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第到第1010天时就只有一个桃子了，求原有多少个桃？天时就只有一个桃子了，求原有多少个桃？数数 学学 模模 型型：每每 天天 的的 桃桃 子子 数数 为为：a10=1,a10=1,a9=(1+a10)*2,a9=(1+a10)*2,a8=(1+a9)*2,a8=(1+a9)*2,a10=1a10=1，递推公式为：递推公式为：ai=(1+ai+1)*2 I=9,8,7,6ai=(1+ai+1)*2 I=9,8

11、,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)*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 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

13、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行行本讲稿第十一页，共八十二页算法如下：算法如下：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

14、+1)print(aj);print(“换行符换行符”);本讲稿第十二页，共八十二页【例例3 3】穿越沙漠问题穿越沙漠问题 用一辆吉普车穿越用一辆吉普车穿越10001000公里的沙漠。吉普车的总装油量为公里的沙漠。吉普车的总装油量为500500加仑，加仑，耗油率为耗油率为1 1加仑加仑/公里。由于沙漠中没有油库，必须先用这辆车公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。应在什么地方建油库，以及各处的贮油量。问题分析：问题分析：1 1）先看一简单问题：有一

15、位探险家用先看一简单问题：有一位探险家用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 BA 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 贮油点及贮油量示意贮油点及贮油量示意本讲稿第十六页，共八十二页综上分析综上分析，从终点开始分别间隔，从终点开始分别间隔 500

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

21、，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 print(print(“storepointstorepoint”,k,k,”distancedistance”,1000-dis,1000-dis,”oilquantityoilquantity”,oil),oil)；k=k+1;k=k+1;dis=dis+500/(2*k-1);dis=dis+500/(2*k-1);oi

22、l=500*k;oil=500*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)；本讲稿第十八页，共八十二页4.1.3 4.1.3 迭代法解方程迭代法解方程迭迭代代法法解解方方程程的的实实质质是是按按照照下下列列步步骤骤构构造造一一个个序序列列x x0 0,x,x1 1,x,xn n,来来逐步逼近方程逐步逼近方程f(x)=0f(

23、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的根。的根。本讲稿第十九

24、页，共八十二页【例例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为为解的精度解的精度,则则算法如下：算法如下：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)

25、;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;i=1e-4);while(fabs(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，则则c0c0为为方方程程f(x)=0f(x)=0的的根根；否否则则，若若f(a0)f(a0)与与f(c0)f(c0)异异号号，即即 f(a0)*f(c0)0

26、f(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时，就认为找到了方程的根。时，就认为找到了方程的根。用二分法求一元非线性方程用二分法求一元非线性方程f(x)=x3/2+2x2-8=0（其中（其中表示表示幂运算）在区间幂运算）在区间0，2上的近似实根上的近似实根r，精确到

27、，精确到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根的前提条件是：根的前提条件是：根的前提条件是：根的前提条件是：f(x)f(x)f(x)f(x)在求在求在求在求解的区解的区解的区解的区间间间间a,ba,ba,ba,b上是上是上是上是连续连续连续连续的，且已知的，且已知的，且已知的，且已知f(a)f

28、(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(print(“input a,b(f(a)*f(b)0)input a,b(f(a)*f(b)0)printf(No root);return;if(f1*f20)printf(No root);return;do do x=(x1+x2)/2;x=(x

29、1+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;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 其它范例其它范

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

31、蛮力策略具体应用。比较常用还有符串匹配等，都是蛮力策略具体应用。比较常用还有枚枚举举法法、盲目、盲目搜索算法等，本节介绍搜索算法等，本节介绍枚枚举举法法和其它一些小的范例，第五章介绍盲目搜索和其它一些小的范例，第五章介绍盲目搜索算法。算法。本讲稿第二十六页，共八十二页4 42 21 1 枚举法枚举法枚枚举举（enumerate）法法（穷穷举举法法）是是蛮蛮力力策策略略的的一一种种表表现现形形式式，也也是是一一种种使使用用非非常常普普遍遍的的思思维维方方法法。它它是是根根据据问问题题中中的的条条件件将将可可能能的的情情况况一一一一列列举举出出来来，逐逐一一尝尝试试从从中中找找出出满满足足问问题题

32、条条件件的的解解。但但有有时时一一一一列列举举出出的的情情况况数数目目很很大大，如如果果超超过过了了我我们们所所能能忍忍受受的的范范围围，则则需需要要进进一一步步考考虑虑，排排除除一一些些明明显显不不合合理理的的情情况况，尽尽可可能能减减少少问问题题可可能能解解的的列列举数目。举数目。用枚举法解决问题，通常可以从两个方面进行算法设计：用枚举法解决问题，通常可以从两个方面进行算法设计：1）找出枚举范围：分析问题所涉及的各种情况。找出枚举范围：分析问题所涉及的各种情况。2 2）找找出出约约束束条条件件：分分析析问问题题的的解解需需要要满满足足的的条条件件，并并用用逻逻辑辑表表达达式表示。式表示。本

33、讲稿第二十七页，共八十二页【例例1 1】百百钱钱百百鸡问题鸡问题。中国古代数学家。中国古代数学家张张丘建在他的丘建在他的算算经经中提中提出了著名的出了著名的“百百钱钱百百鸡问题鸡问题”：鸡鸡翁一，翁一，值钱值钱五；五；鸡鸡母一，母一，值钱值钱三；三；鸡鸡雏雏三，三，值钱值钱一；百一；百钱买钱买百百鸡鸡，翁、母、，翁、母、雏雏各几何各几何?算法设计算法设计1：通过对问题的理解，读者可能会想到列出两个三元一次方程，去解这个不通过对问题的理解，读者可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用定解方程，就能找出问题的解。这确实是一种办法，但这里

34、我们要用“懒懒惰惰”的枚举策略进行算法设计：的枚举策略进行算法设计：设设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*x+3*y+z/3=1005*x+3*y+z/3=100 本讲稿第二十八页，共八十二页算法算法1

35、如下：如下：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*x+3*y+z/3)if(100=x+y+z and 100=5*x+3*y+z/3)print(the cock number is,x)print(the cock number is,x)；print(the hen number is,y

36、)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如下：如下

37、：本讲稿第三十页，共八十二页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 5*x+3*y+z/3=100)if(z mod 3=0 and 5*x+3*y+z/3=100)print(the cock number is,x)print(the cock number is,x)；print(the hen number is,y)print(the h

38、en number is,y)；print(the chick number is z);print(the chick number is z);算法分析：算法分析：以上算法只需要枚举尝试以上算法只需要枚举尝试20*33=660次。实现时约束条件又次。实现时约束条件又限定限定Z能被能被3整除时，才会判断整除时，才会判断“5*x+3*y+z/3=1005*x+3*y+z/3=100”。这样这样省去了省去了z z不整不整除除3 3时时的算的算术计术计算和条件算和条件判断，判断，进进一步提高了算法的效率。一步提高了算法的效率。本讲稿第三十一页，共八十二页【例例2 2】解数字迷：解数字迷：A B C

39、 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*10000+B*1000+C*100+A*10+BA*10000+B*1000+C*100+A*10+B，共尝试共尝试800800次。次。2)2)约束条件为：约束条件为：每次尝试，先求六位数与每次尝试，先求六位数与A A的积，再测试积的各位是否相的积，再测试积的各位是否相 同，若相同则

40、找到了问题的解。同，若相同则找到了问题的解。测试积的各位是否相同比较简单的方法是，从低位开始，测试积的各位是否相同比较简单的方法是，从低位开始，每次都取数据的个位，然后整除每次都取数据的个位，然后整除1010，使高位的数字不断变，使高位的数字不断变 成个位，并逐一比较。成个位，并逐一比较。本讲稿第三十二页，共八十二页算法算法1 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

41、;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是否各个位的数字都相同。鉴于要是否各个位的数字都相同。鉴于要输出结果，所以不要改变计算结果，而另设变量输出结果，所以不要改变计算结果，而另设变量E1E1，用于测试运算。，用于测试运算。算

42、法分析算法分析算法分析算法分析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：将算式变形为除法：将算式变形为除法：DDDDDD/A=ABCABDDDDDD/A=ABCAB。此时。此时只需枚举只需枚举A A：3 39 D9 D

43、：1 19 9，共尝试，共尝试7*9=637*9=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*100000+D*10000+D*1000+D*100+D*10+D;E=D*100000+D*10000+D*1

44、000+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例例1及本及本章下一节章下一节4.3.3例例4的算法的算法1等。本节将通过蛮力策略，用算法模拟问题等。本

45、节将通过蛮力策略，用算法模拟问题中所描述的全部过程和全部状态，来找出问题的解，并与经过数学建模后中所描述的全部过程和全部状态，来找出问题的解，并与经过数学建模后的算法进行效率上的比较。的算法进行效率上的比较。4 42 22 2 其它范例其它范例本讲稿第三十六页，共八十二页【例例3 3】狱吏问题狱吏问题 某国王对囚犯进行大赦，让一狱吏某国王对囚犯进行大赦，让一狱吏n n次通过一排锁着的次通过一排锁着的n n间牢间牢房，每通过一次，按所定规则转动房，每通过一次，按所定规则转动n n间牢房中的某些门锁间牢房中的某些门锁,每转动一每转动一次次,原来锁着的被打开原来锁着的被打开,原来打开的被锁上；通过原

46、来打开的被锁上；通过n n次后，门锁开次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第隔一间转动一次；第k k次通过牢房，从第次通过牢房，从第k k间开始转动，每隔间开始转动，每隔k-1 k-1 间间转动一次；问通过转动一次；问通过n n次后，那些牢房的锁仍然是打开的？次后，那些牢房的锁仍然是打开的？本讲稿第

47、三十七页，共八十二页算法设计算法设计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

48、，号牢房；号牢房；第第i i次次转转动动的的是是i i，2i2i，3i3i，4i4i，号号牢牢房房，是是起起点点为为i i，公差为公差为i i的等差数列。的等差数列。4 4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关）不做其它的优化，用蛮力法通过循环模拟狱吏的开关 锁过程，最后当第锁过程，最后当第i号牢房对应的数组元素号牢房对应的数组元素aiai为为0 0时，时，该牢房的囚犯得到大赦。算法该牢房的囚犯得到大赦。算法1如下：如下：本讲稿第三十八页，共八十二页main1()main1()int*a,i,j,n;int*a,i,j,n;input(n);input(n);a=calloc(n+1

49、,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,if(ai=0)print(i,”is free.is free.”););算算 法法 分分 析析：以以 一一 次次 开开 关关 锁锁 计计 算算，算算 法法 的的 时时 间间 复复 杂杂

50、 度度 为为n(1+1/2+1/3+n(1+1/2+1/3+1/n)=O(nlogn)+1/n)=O(nlogn)。本讲稿第三十九页，共八十二页问题分析：问题分析：转动门锁的规则可以有另一种理解，第一次转动的是转动门锁的规则可以有另一种理解，第一次转动的是编号为编号为1 1的倍数的牢房；第二次转动的是编号为的倍数的牢房；第二次转动的是编号为2 2的倍数的牢房；的倍数的牢房；第三次转动的是编号为第三次转动的是编号为3 3的倍数的牢房；的倍数的牢房；则则狱吏问题是一个狱吏问题是一个关于因子个数的关于因子个数的问题。令问题。令d(n)d(n)为自然数为自然数n n的因子个数，这里不的因子个数，这里不