第三章 蛮力法.ppt

《第三章 蛮力法.ppt》由会员分享，可在线阅读，更多相关《第三章 蛮力法.ppt（54页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第三章第三章第三章第三章算法算法基本工具和优化技巧基本工具和优化技巧利用算法的利用算法的基本机制基本机制循环和递归设计循环和递归设计算法算法利用算法的利用算法的基本操作基本操作提高算法效率的技巧提高算法效率的技巧利用数组利用数组提高算法质量提高算法质量建立高效的数学模型建立高效的数学模型31循环与递归循环与递归33算法优化基本技巧算法优化基本技巧32算法与数据结构算法与数据结构34优化算法的数学模型优化算法的数学模型311循环设计要点循环设计要点312 递归设计要点递归设计要点313递归与循环的比较递归与循环的比较31 循环与循环与递归递归311 循环设计要点循环设计要点 1 1设计设计中要注

2、意算法的效率中要注意算法的效率 2 2“自自顶顶向下向下”的的设计设计方法方法 3 3由具体到抽象设计循环结构由具体到抽象设计循环结构 循环体的特点是：循环体的特点是：“以不变应万变以不变应万变”。所谓所谓“不变不变”是指循环体内运算的表现是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是形式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现不尽相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。形式去描述各种相似的重复运算。1 1循环循环设计设计中要注意算法的效率中要注意算法的效率【例例1 1】求求1/1!-1/3!+1/5!-1/7!+1/1!-

3、1/3!+1/5!-1/7!+（-1 1）n+1/(2n-1)!n+1/(2n-1)!分析：此问题中既有累加又有累乘，准确地说累加分析：此问题中既有累加又有累乘，准确地说累加的对象是累乘的结果。的对象是累乘的结果。数学模型数学模型1 1：SnSn=Sn-1+=Sn-1+（-1-1）n+1n+1/(2n-1)!/(2n-1)!算法设计算法设计1 1：多数初学者会直接利用题目中累加项：多数初学者会直接利用题目中累加项通式，构造出循环体不变式为：通式，构造出循环体不变式为：S=S+S=S+（-1-1）n+1/(2n-1)!n+1/(2n-1)!需要用二重循环来完成算法，算法需要用二重循环来完成算法，

4、算法1 1如下：如下：算法如下：算法如下：求（求（-1-1）n+1 for(j=1;j=i+1;j=j+1)for(j=1;j=i+1;j=j+1)sign=sign*(-1);sign=sign*(-1);s=s+sign/t;s=s+sign/t;print(print(“SnmSnm=”,s);,s);main()main()intint i,n,j,sign=1;i,n,j,sign=1;float s,t=1;float s,t=1;input(n);input(n);s=1s=1；for(i=2;i=n;i=i+1)for(i=2;i=n;i=i+1)t=1;t=1;求阶乘求阶乘

5、for(j=1;j=2*i-1;j=j+1)for(j=1;j=2*i-1;j=j+1)t=t*j;t=t*j;sign=1;sign=1;算法分析算法分析：以上算法是以上算法是二重循环二重循环来完成来完成 ，但算，但算法的效率却太低是法的效率却太低是O（n2）。其其原原因因是是，当当前前一一次次循循环环已已求求出出7 7！，当当这这次次要要想想求求9 9！时时，没没必必要要再再从从1 1去去累累乘乘到到9 9，只只需需要要充充分分利利用用前前一一次次的的结结果果，用用7 7！*8*9*8*9即即可可得得到到9 9！，模模型型为为A An n=A=An-1n-1*1/(2*n-2)*(2*n-

6、1)*1/(2*n-2)*(2*n-1)。另另外外运运算算sign sign=sign sign*(-1);(-1);总总共共也也要要进进行行n*(n-1)/2n*(n-1)/2次次乘乘法法，这这也也是是没没有有必必要的。下面我们就进行改进。要的。下面我们就进行改进。数学模型数学模型2 2：S Sn n=S=Sn-1n-1+（-1-1）n+1n+1A An n；A An n=A=An-1 n-1*1/(2*n-2)*(2*n-1)*1/(2*n-2)*(2*n-1)main()main()intint i,n,sign;i,n,sign;float s,t=1;float s,t=1;inpu

7、t(n);input(n);s=1s=1；sign=1;sign=1;for(i=2;i=n;i=i+1)for(i=2;i=n;i=i+1)或或 for(i=1;i=n-1;i=i+1)for(i=1;i=n-1;i=i+1)sign=-sign;sign=-sign;t=t*(2*i-2)*(2*i-1);t=t*2*i*(2*i+1);t=t*(2*i-2)*(2*i-1);t=t*2*i*(2*i+1);s=s+sign/t;s=s+sign/t;s=s+sign/t;s=s+sign/t;print(“Sum=”,s);print(“Sum=”,s);算法说明算法说明2 2：构造循构

8、造循环环不不变变式式时时，一定要注意循，一定要注意循环变环变量的意量的意义义，如当，如当i i不是不是项项数序号数序号时时（右（右边边的循的循环环中）有关中）有关t t的的累乘累乘式与式与i i是是项项数序号数序号时时就不能相同。就不能相同。算法分析：算法分析：按照数学模型按照数学模型2 2，只需，只需一重循环一重循环就能解决问题就能解决问题算法的算法的时间时间复复杂杂性性为为O O（n n）。2 2“自自顶顶向下向下”的的设计设计方法方法 自自顶顶向下的方法是从全局走向局部、从向下的方法是从全局走向局部、从概略概略走向走向详详尽的尽的设计设计方法。自上而下是系方法。自上而下是系统统分解和分解

9、和细细化的化的过过程。程。【例例2 2】编算法找出编算法找出10001000以内所有完数以内所有完数例例如如，2828的的因因子子为为1 1、2 2、4 4、7 7，1414，而而28=1+2+4+7+1428=1+2+4+7+14。因因此此2828是是“完完数数”。编编算算法法找找出出10001000之之内内的的所所有有完完数数，并并按按下下面面格格式式输输出出其其因因子子：28 28 its its factors are 1factors are 1，2 2，4 4，7 7，1414。1 1）这这里里不不是是要要质质因因数数，所所以以找找到到因因数数后后也也无无需需将将其其从从数据中数据

10、中“除掉除掉”。2 2）每每个个因因数数只只记记一一次次，如如8 8的的因因数数为为1 1，2 2，4 4而而不不是是1 1，2 2，2 2，2 2，4 4。（注注：本本题题限限定定因因数数不不包包括括这这个个数数本本身）身）1）顶层算法 for(i=0;in;i=i+1)找第i行上最小的元素t及所在列minj;检验t是否第minj 列的最大值，是则输出这个鞍点;2）找第i行上最小的元素t及所在列minj t=ai0;minj=1;for(j=1;jn;j=j+1)if(aijt)t=aij;minj=j;3）进一步细化判断i是否“完数”算法s=1for(j=2;ji;j=j+1)if(i m

11、od j=0)(j是i的因素)s=s+j;if （s=i）i是“完数”;4 4）考虑输出格式）考虑输出格式判断判断i i是否是否“完数完数”算法算法 考考虑虑到到要要按按格格式式输输出出结结果果，应应该该开开辟辟数数组组存存储储数数据据i i的所有因子，并记录其因子的个数，因此算法细化如下：的所有因子，并记录其因子的个数，因此算法细化如下：定义数组定义数组a，s=1;k=0;for(j=2;ji;j=j+1)j=2;ji;j=j+1)if(i mod j=0)(j if(i mod j=0)(j是是i i的因素的因素)s=s+j;ak=j;k=k+1;s=s+j;ak=j;k=k+1;if i

12、f （s=is=i）按格式输出结果按格式输出结果 算法如下：算法如下：main()inti,k,j,s,a20;for(i=1;i=1000;i+)s=1;/*两个赋初值语句两个赋初值语句s=1,k=0k=0;一定要位于外部循环的内部一定要位于外部循环的内部*/for(j=2;ji;j+)if(imodj)=0)s=s+j;ak=j;k+;if(i=s)print(s,“itsfactorsare:”,1);for(j=0;ik;j+)print(“,”,ak);【例例3 3】求一个矩阵的鞍点求一个矩阵的鞍点 (即在行上最小而在列上最大的点即在行上最小而在列上最大的点)。算法设计算法设计：1

13、1）在第一行找最小值，并记录其列号。在第一行找最小值，并记录其列号。2 2）然后验证其是否为所在列的最大值，如果是，则然后验证其是否为所在列的最大值，如果是，则找到问题的解；否则，则继续在下一行找最小值找到问题的解；否则，则继续在下一行找最小值 。for(i=0;in;i=i+1)找第i行上最小的元素t及所在列minj;检验t是否第minj 列的最大值，是则输出这个鞍点;t=ai0;minj=1;for(j=1;jn;j=j+1)if(aijt)t=aij;minj=j;1）顶层算法 2）找第i行上最小的元素t及所在列minj 3）检验t是否第minj 列的最大值，是，则输出这个鞍点;for(

14、k=0;kt)break;if(kn)continue;print(“the result is a“,i，“”,minj,“=”，t);考虑到会有无解的情况，设置标志量kz，kz=0代表无解，找到一个解后，kz被赋值为1，就不再继续找鞍点的工作。请读者考虑是否有多解的可能性吗？若有，请改写算法，找出矩阵中所有的鞍点。算法如下：算法如下：buck()inta1010;inti,j,k,minj,t,n=10,kz=0;/*minj代表当前行中最小值的列下标；设置标志量代表当前行中最小值的列下标；设置标志量kz*/readmtr(a,n);prntmtr(a,n);for(i=0;in;i+)t

15、=ai0;minj=1;for(j=1;jn;j+)if(aijt)t=aij;minj=j;for(k=0;kaiminj)break;if(kn)continue;print(“theresultisa“,i,“”,minj,“=”，aiminj);kz=1;break;if(kz=0)print(“nosolution!”);对于不太熟悉的问题，其数学模型或“机械化操作步骤”的不易抽象，下面看一个由具体到抽象设计循环细节的例题。【例4】编写算法：打印具有下面规律的图形。1 5 2 8 6 3 10 9 7 4 3 3由具体到抽象设计循环结构由具体到抽象设计循环结构算算法法设设计计：容容易

16、易发发现现图图形形中中自自然然数数在在矩矩阵阵中中排排列列的的规规律律，题题目目中中1 1，2 2，3 3，4 4所所在在位位置置我我们们称称为为第第1 1层层（主主对对角角线线），例例图图中中5 5，6 6，7 7所所在在位位置置我我们们称称为为第第二二层层，。一一般般地地，第一层有第一层有n n个元素，第二层有个元素，第二层有n-1n-1个元素个元素基基于于以以上上数数据据变变化化规规律律，以以层层号号作作为为外外层层循循环环，循循环环变变量量为为i i（范范围围为为11n n）；以以层层内内元元素素从从左左上上到到右右下下的的序序号号作作为为内内循循环环，循循环环变变量量为为j j（范范

17、围围为为11n+1-in+1-i）。这这样样循循环环的的执执行行过过程程正正好好与与“摆摆放放”自自然然数数的的顺顺序序相相同同。用用一一个个变变量量k k模模拟拟要要“摆摆放放”的的数数据据，下下面面的的问问题题就就是是怎怎么么样将数据存储到对应的数组元素。样将数据存储到对应的数组元素。数数组组元元素素的的存存取取，只只能能是是按按行行、列列号号操操作作的的。所所以以下下面面用用由由具具体体到到抽抽象象设设计计循循环环的的“归归纳纳法法”，找找出出数数组组元元素素的的行行号号、列列号号与与层层号号i i及层内序号及层内序号j j的关系：的关系：1.1.每每层层内内元元素素的的列列号号都都与与

18、其其所所在在层层内内的的序序号号j j是是相相同同的的。因因为为每每层的序号是从第一列开始向右下进行。层的序号是从第一列开始向右下进行。2.2.元素的行与其所在的层号及在层内的序号均有关系元素的行与其所在的层号及在层内的序号均有关系,具体地：具体地：第一层行号第一层行号11n n，行号与行号与j j同；同；第二层行号第二层行号22n n，行号比行号比j j大大1 1；第三层行号第三层行号33n n，行号比行号比j j大大2 2；行行号号起起点点随随层层号号i i增增加加而而增增加加，层层内内其其它它各各行行的的行行号号又又随随层层内内序序号号j j增增加加而而增增加加，由由于于编编号号起起始始

19、为为1 1，i i层层第第j j个个数数据据的的列列下下标标为为i-i-1+j1+j。综合以上分析综合以上分析,i i层第层第 j j个数据对应的数组元素是个数据对应的数组元素是ai-1+jjai-1+jj。main()main()intint i,j,a100100,n,k;i,j,a100100,n,k;input(n);input(n);k=1;k=1;for(i=1;i=n;i=i+1)for(i=1;i=n;i=i+1)for(j=1;j=n+1-i;j=j+1)for(j=1;j=n+1-i;j=j+1)ai-1+jj=k;ai-1+jj=k;k=k+1;k=k+1;for(i=1

20、;i=n;i=i+1)for(i=1;i=n;i=i+1)print(“print(“换行符换行符”);”);for(j=1;j=i;j=j+1)for(j=1;j0)/*0阶的汉诺塔问题当作停止条件阶的汉诺塔问题当作停止条件*/2)hanoi(n-1,a,c,b);3)输出输出“Movedise”,n.”frompile”,a,”to”b);4)haboi(n-1,c,b,a);5)endif 【例例2 2】整数的分划问题整数的分划问题 对于一个正整数对于一个正整数n n的分划就是把的分划就是把n n写成一系列正整数之和的表达写成一系列正整数之和的表达式。例如，对于正整数式。例如，对于正整数

21、n=6n=6，它可以分划为：它可以分划为：6 6 5+1 5+1 4+2,4+1+1 4+2,4+1+1 3+3,3+2+1,3+1+1+1 3+3,3+2+1,3+1+1+1 2+2+2,2+2+1+1,2+1+1+1+1 2+2+2,2+2+1+1,2+1+1+1+1 1+1+1+1+1+11+1+1+1+1+1 根据例子发现根据例子发现“包括第一行以后的数据不超过包括第一行以后的数据不超过6 6，包括，包括第二行的数据不超过第二行的数据不超过5 5，第六行的数据不超过，第六行的数据不超过1”1”。因此，定义一个函数因此，定义一个函数Q(n,m)Q(n,m)，表示整数表示整数n n的的“任

22、何被加任何被加数都不超过数都不超过m”m”的分划的数目，的分划的数目，n n的所有分划的数目的所有分划的数目P(n)=Q(n,n)P(n)=Q(n,n)。模型建立：模型建立：一般地一般地Q(n.m)Q(n.m)有以下递归关系：有以下递归关系：1)1)Q(n,n)=1+Q(n,n-1)Q(n,n)=1+Q(n,n-1)（m=nm=n）Q(n,n-1)Q(n,n-1)表示表示n n的所有其他分划，即最大被加数的所有其他分划，即最大被加数m=n-1m=n-1的划分。的划分。2)2)Q(n,m)=Q(n,m-1)+Q(n-m,m)Q(n,m)=Q(n,m-1)+Q(n-m,m)(mn)(mn)Q(n,

23、n-1)Q(n,n-1)表示被加数中不包含表示被加数中不包含m m的分划的数目；的分划的数目；Q(n-m,m)Q(n-m,m)表示被加数中包含表示被加数中包含(注意不是小于注意不是小于)m m的分划的数目，的分划的数目，递归的停止条件：递归的停止条件：1)1)Q(n,1)=1Q(n,1)=1，表示当最大的被加数是表示当最大的被加数是1 1时，该整数时，该整数n n只有一只有一种分划，即种分划，即n n个个1 1相加；相加；2)2)Q(1,m)=1Q(1,m)=1，表示整数表示整数n=1n=1只有一个分划，不管最大被加只有一个分划，不管最大被加数的上限数的上限m m是多大。是多大。算法如下：算法

24、如下：DivintegerDivinteger(n,(n,m)m)if if（n n 1 1 or or m m n1 or m n）Error(Error(“输入参数错误输入参数错误”)；/*/*nm Q(n,m)nm Q(n,m)是无意义的是无意义的*/*/else else if if（n n=1 1 or or m m=1 1）returnreturn（1 1）；）；else else if if（n n =10)print(n mod 10);n=n10;print(n);递归算法设计：递归算法设计：1 1）同同上上，算算法法从从低低位位到到高高位位逐逐位位求求出出各各位位数数字字并

25、并输输出出，求求个个位位数数字的算式为字的算式为 n mod 10n mod 10，下一步则是递归地求下一步则是递归地求n10n10的个位数字。的个位数字。2 2）当）当n10n10时，时，n n为一位数停止递归。为一位数停止递归。递归算法如下：递归算法如下：f2(n)f2(n)if(n10)if(n=10)while(n=10)ai=n mod 10;ai=n mod 10;i=i+1;i=i+1;n=n10;n=n10;ai=n;ai=n;for(j=i;j=0;j=j-1)for(j=i;j=0;j=j-1)print(aj);print(aj);递归算法设计：递归算法设计：与与f2f2

26、不不同同，递递归归算算法法是是先先递递归归地地求求n10n10的的个个位位数数字字，然然后后再再求求个个位位数数字字n n的的个个位位数数字字并并输输出出。这这样样输输出出操操作作是是在在回回溯溯时时完完成成的的。递递归停止条件与归停止条件与f2f2相同为相同为n10n10。递归算法如下：递归算法如下：f4(n)f4(n)if(n10)if(n=n;i-)for(i=1;i=n;i-)for(j=1;j=n;j-)for(j=1;j=n;j-)for(k=1;k=n;k-)for(k=1;k=n;k-)if(ij)and(ik)and(ij)and(jk)if(ij)and(ik)and(ij

27、)and(jk)t=t+1;t=t+1;print(i,j,k);print(i,j,k);print(total=,t);print(total=,t);或者constitute2（）int n=5,r=3,i,j,k,t;t=0;for(i=1;i=n-r+1;i=i+1)for(j=i+1;j=n-r+2;j=j+1)for(k=j+1;k=k;i-)ak=i;if(k1)comb(i-1,k-1);elsefor(j=a0;j0;j-)print(aj);print(“换行符换行符”);constitute3()intn,r;print(“n,r=”);input(n,r);if（rn

28、）print(“Inputn,rerror!”);elsea0=r;comb(n,r);/调用递归过程调用递归过程/分析分析：算法算法2 2递归的深度是递归的深度是r r，每个算法要递归每个算法要递归m-k+1m-k+1次，所以的时间复杂性是次，所以的时间复杂性是O（r*nr*n）。递递归归是是一一种种强强有有力力的的算算法法设设计计方方法法。递递归归是是一一种种比比循循环环更更强强、更更好好用用的的实实现现“重重复复操操作作”的的机机制制。因因为为递递归归不不需需要要编编程程者者（算算法法设设计计者者）自自己己构构造造“循循环环不不变变式式”，而而只只需需要要找找出出递递归归关关系系和和最最小小问问题题的的解解。递递归归在在很很多多算算法法策策略略中中得得以以运运用用，如如：分分治治策策略略、动动态规划、图的搜索等算法策略。态规划、图的搜索等算法策略。综合以上讨论，可以得出以下结论：综合以上讨论，可以得出以下结论：递归递归非递归非递归程序可读性程序可读性易易难难代码量大小代码量大小小小大大时间时间长长短短占用空间占用空间大大小小适用范围适用范围广广窄窄设计难度设计难度易易难难