算法设计与分析第三章循环与递归课件.ppt

《算法设计与分析第三章循环与递归课件.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析第三章循环与递归课件.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析第三章循算法设计与分析第三章循环与递归环与递归第1页，此课件共52页哦第三章第三章 算法基本工具和优化技巧算法基本工具和优化技巧 n利用算法的利用算法的基本机制基本机制循环和递归设计循环和递归设计算法算法n利用算法的利用算法的基本操作基本操作提高算法效率的技巧提高算法效率的技巧n利用数组提高算法质量利用数组提高算法质量n建立高效的数学模型建立高效的数学模型本章主要讲解如何充分利用这些基本的程序设计本章主要讲解如何充分利用这些基本的程序设计技术设计高质量的算法，在程序设计与算法设计之间技术设计高质量的算法，在程序设计与算法设计之间起承上启下的作用起承上启下的作用第2页，此课件共52

2、页哦3.1.1循环设计要点循环设计要点3.1.2 递归设计要点递归设计要点3.1.3递归与循环的比较递归与循环的比较3.1 循环与循环与递归递归第3页，此课件共52页哦311 循环设计要点循环设计要点 1 1设计设计中要注意算法的效率中要注意算法的效率 2 2“自自顶顶向下向下”的的设计设计方法方法 3 3由具体到抽象设计循环结构由具体到抽象设计循环结构 第4页，此课件共52页哦 循环体的特点是：循环体的特点是：“以不变应万变以不变应万变”。所谓所谓“不变不变”是指循环体内运算的表现形式是不变是指循环体内运算的表现形式是不变的的,如变量，控制结构如变量，控制结构，而每次具体的执行内容，而每次具

3、体的执行内容数据数据却是却是不尽相同的。在循环体内用不变的运算表现形式去描述不尽相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。各种相似的重复运算。1 1循环循环设计设计中要注意算法的效率中要注意算法的效率第5页，此课件共52页哦【例1】求1/1!-1/3!+1/5!-1/7!+（-1）n+1/(2n-1)!n分析：此问题中既有分析：此问题中既有累加累加又有又有累乘累乘，准确地说，准确地说累加的对象是累乘的结果。累加的对象是累乘的结果。数学模型数学模型1 1：Sn=Sn-1+（-1）n+1/(2n-1)!算法设计算法设计1 1：多数初学者会直接利用题目中累：多数初学者会直接利用

4、题目中累加项通式，构造出循环体不变式为：加项通式，构造出循环体不变式为：S=S+（-1）n+1/(2n-1)!需要用二重循环来完成算法，算法需要用二重循环来完成算法，算法1 1如下：如下：第6页，此课件共52页哦算法如下：求（求（-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(“Snm=Snm=”,s);,s);main()main()int i,n,j,sign=1;int i,n,j,sign=1;float s,

5、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;求阶乘求阶乘 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;第7页，此课件共52页哦算法分析：n以上算法是二重循环来完成以上算法是二重循环来完成，但算法的效率却太低是，但算法的效率却太低是O（n2）。）。当当前前一一次次循循环环已已求求出出7！，当当这这次次要要想想求求9！时时，没没必必要要再再从从1去去累累乘乘到到9，只只需需要要充

6、充分分利利用用前前一一次次的的结结果果，用用7！*8*9即即可可得得到到9！，模模型型为为An=An-1*1/(2*n-2)*(2*n-1)。另另外外运运算算sign=sign*(-1);总总共共也也要要进进行行n*(n-1)/2次次乘乘法法，这这也也是是没有必要的。下面我们就进行改进。没有必要的。下面我们就进行改进。第8页，此课件共52页哦数学模型2：Sn=Sn-1+（-1）n+1An；An=An-1*1/(2*n-2)*(2*n-1)main()main()int i,n,sign;int i,n,sign;float s,t=1;float s,t=1;input(n);input(n)

7、;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(print(“Sum=Sum=”,s);,s);第9页，此课件共52页哦算法分析：按照数学模型2，只需一重循环

8、就能解决问题算法的时间复杂性为O（n）。算法说明算法说明2 2第10页，此课件共52页哦2“自顶向下”的设计方法 自自顶顶向向下下的的方方法法是是从从全全局局走走向向局局部部、从从概概略略走走向向详详尽尽的的设设计计方方法法。自自上上而而下下是是系系统统分分解解和和细细化的化的过过程。程。【例例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之之内内的的所所有有完完数数，并

9、并按按下下面面格格式式输出其因子：输出其因子：28 it28 its factors are 1s factors are 1，2 2，4 4，7 7，1414。第11页，此课件共52页哦1 1）这这里里不不是是要要质质因因数数，所所以以找找到到因因数数后后也也无无需需将将其其从从数数据据中中“除掉除掉”。2 2）每每个个因因数数只只记记一一次次，如如8 8的的因因数数为为1 1，2 2，4 4而而不不是是1 1，2 2，2 2，2 2（注：本题限定因数不包括这个数本身）（注：本题限定因数不包括这个数本身）第12页，此课件共52页哦1 1）顶层算法）顶层算法for(i=2;i=n;i=i+1)

10、i=2;i=n;i=i+1)判断判断i i是否是是否是“完数完数”;是是“完数完数”则按格式输出则按格式输出;2 2）判断）判断i i是否是是否是“完数完数”的算法的算法 for(j=2;ji;j=j+1)for(j=2;ji;j=j+1)找找i i的的因因子子，并并累累加加，如如果果累累加加值值等等于于i,i i,i 是是“完数完数”第13页，此课件共52页哦3 3）进一步细化）进一步细化判断判断i i是否是否“完数完数”算法算法s=1for(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;

11、)s=s+j;if if （s=is=i）i i是是“完数完数”;第14页，此课件共52页哦 定义数组定义数组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 if （s=is=i）按格式输出结果按格式输出结果 4）考虑输出格式判断i是否“完数”算法n考虑到要按格式输出结果，应该开辟数组存储考虑到要按格式输出结果，应该开辟数组存储数据数据i的所有因子，并记录其因子的个数，因的所有因子，并记录其因子的个数，因

12、此算法细化如下：此算法细化如下：第15页，此课件共52页哦算法如下：算法如下：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);第16页，此课件共52页哦【例3】求一个矩阵的鞍点 (即在行上最小而在列上最大的点)。算法设计：算法设计：1）在第一行找最小

13、值，并记录其列号。）在第一行找最小值，并记录其列号。2）然后验证其是否为所在列的最大值，如果是，则找到问）然后验证其是否为所在列的最大值，如果是，则找到问题的解；否则，则继续在下一行找最小值题的解；否则，则继续在下一行找最小值。第17页，此课件共52页哦for(i=0;in;i=i+1)i=0;in;i=i+1)找第找第i i行上最小的元素行上最小的元素t t及所在列及所在列minj;minj;检验检验t t是否第是否第minj minj 列的最大值，是则输出鞍点列的最大值，是则输出鞍点;t=ai0;minj=1;t=ai0;minj=1;for(j=1;jn;j=j+1)for(j=1;jn

14、;j=j+1)if(aijt)if(aijt)t=aij;t=aij;minj=j;minj=j;1 1）顶层算法）顶层算法 2 2）找第）找第i i行上最小的元素行上最小的元素t t及所在列及所在列minj minj 第18页，此课件共52页哦3 3）检验）检验t t是否第是否第minjminj列的最大值，是，则输出鞍点列的最大值，是，则输出鞍点;for(k=0;kn;k=k+1)for(k=0;kt)break;if(akminjt)break;if(kn)continue;if(kn)continue;print(print(“the result is athe result is a

15、“,i,i，“”,minj,minj,“=”，t);t);考考虑虑到到会会有有无无解解的的情情况况，设设置置标标志志量量kzkz，kz=0kz=0代代表表无无解解，找找到到一一个个解解后后，kzkz被赋值为被赋值为1 1，就不再继续找鞍点的工作。，就不再继续找鞍点的工作。请考虑是否有多解的可能性吗？若有，请改写算法，找出矩阵中所有的鞍点。请考虑是否有多解的可能性吗？若有，请改写算法，找出矩阵中所有的鞍点。第19页，此课件共52页哦算法如下：算法如下：buck()inta1010;inti,j,k,minj,t,n=10,kz=0;/*minj代表当前行中最小值的列下标；设置标志量kz*/rea

16、dmtr(a,n);prntmtr(a,n);for(i=0;in;i+)t=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!”);能否不用能否不用continue达到达到目的目的第20页，此课件共52页哦 对对于于不不太太熟熟悉悉的的问问题题，其其数数学学模模型型或或“机机械械化化操操作作步步骤骤”的不易抽象，下面看一

17、个由具体到抽象设计循环细节的例题。的不易抽象，下面看一个由具体到抽象设计循环细节的例题。【例例4 4】编写算法：打印具有下面规律的图形。编写算法：打印具有下面规律的图形。1 1 5 2 5 2 8 6 3 8 6 3 10 9 7 4 10 9 7 4 3由具体到抽象设计循环结构第21页，此课件共52页哦容容易易发发现现图图形形中中自自然然数数在在矩矩阵阵中中排排列列的的规规律律，题题目目中中1 1，2 2，3 3，4 4所所在在位位置置我我们们称称为为第第1 1层层（主主对对角角线线），例例图图中中5 5，6 6，7 7所所在在位位置置我我们们称称为为第第二二层，层，。一般地，第一层有。一般

18、地，第一层有n n个元素，第二层有个元素，第二层有n-1n-1个元素个元素基基于于以以上上数数据据变变化化规规律律，以以层层号号作作为为外外层层循循环环，循循环环变变量量为为i i（范范围围为为1 1n n）；以以层层内内元元素素从从左左上上到到右右下下的的序序号号作作为为内内循循环环，循循环环变变量量为为j j（范范围围为为1 1n+1-in+1-i）。这这样样循循环环的的执执行行过过程程正正好好与与“摆摆放放”自自然然数数的的顺顺序序相相同同。用用一一个个变变量量k k模模拟拟要要“摆摆放放”的的数数据据，下下面面的问题就是怎么样将数据存储到对应的数组元素。的问题就是怎么样将数据存储到对应

19、的数组元素。算法设计：第22页，此课件共52页哦 数数组组元元素素的的存存取取，只只能能是是按按行行、列列号号操操作作的的。所所以以下下面面用用由由具具体体到到抽抽象象设设计计循循环环的的“归归纳纳法法”，找找出出数数组组元元素素的的行行号号、列列号号与与层层号号i i及及层层内内序序号号j j的关系：的关系：1.1.每每层层内内元元素素的的列列号号都都与与其其所所在在层层内内的的序序号号j j是是相相同同的的。因因为为每每层层的的序号是从第一列开始向右下进行。序号是从第一列开始向右下进行。2.2.元素的行与其所在的层号及在层内的序号均有关系元素的行与其所在的层号及在层内的序号均有关系,具体地

20、：具体地：第一层行号第一层行号1 1n n，行号与，行号与j j同；同；第二层行号第二层行号2 2n n，行号比，行号比j j大大1 1；第三层行号第三层行号3 3n n，行号比，行号比j j大大2 2；行行号号起起点点随随层层号号i i增增加加而而增增加加，层层内内其其它它各各行行的的行行号号又又随随层层内内序序号号j j增增加加而而增加，由于编号起始为增加，由于编号起始为1 1，i i层第层第j j个数据的列下标为个数据的列下标为i-1+ji-1+j。综合以上分析综合以上分析,i,i层第层第 j j个数据对应的数组元素是个数据对应的数组元素是ai-1+jjai-1+jj。第23页，此课件共

21、52页哦main()main()int i,j,a100100,n,k;int 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;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阶的汉诺塔问题当作停止条件阶

22、的汉诺塔问题当作停止条件*/2)hanoi(n-1,a,c,b);3)输出输出“Movedise”,n.”frompile”,a,”to”b);4)haboi(n-1,c,b,a);5)endif第33页，此课件共52页哦【例例2 2】整数的分划问题整数的分划问题 对于一个正整数对于一个正整数n n的分划就是把的分划就是把n n写成一系列正整数之和的表达式。写成一系列正整数之和的表达式。例如，对于正整数例如，对于正整数n=6n=6，它可以分划为：，它可以分划为：6 6 5+1 5+1 4+2,4+2,4+1+1 4+1+1 3+3,3+3,3+2+1,3+2+1,3+1+1+1 3+1+1+1

23、 2+2,2+2,2+2+1+1,2+2+1+1,2+1+1+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的的“任何被加数都不超过任何被加数都不超过m m”的分划的数目，的分划的数目，n n的所有分划的数目的所有分划的数目P(n)=Q(n,n)P(n)=Q(n,n)。第34页，此课件共52页哦模型

24、建立模型建立：一般地一般地Q(n.m)Q(n.m)有以下递归关系：有以下递归关系：1)Q(n,n)=1+Q(n,n-1)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)Q(n,m)=Q(n,m-1)+Q(n-m,m)(mn)2)Q(n,m)=Q(n,m-1)+Q(n-m,m)(mn)Q(n,n-1)Q(n,n-1)表示被加数中不包含表示被加数中不包含m m的分划的数目；的分划的数目；Q(n-m,m)Q(n-m,m)表示被加数中包含表示被加数中包含(

25、注意不是小于注意不是小于)m)m的分划的数目，的分划的数目，递归的停止条件：递归的停止条件：1)Q(n,1)=11)Q(n,1)=1，表示当最大的被加数是，表示当最大的被加数是1 1时，该整数时，该整数n n只有一种分只有一种分划，即划，即n n个个1 1相加；相加；2)Q(1,m)=12)Q(1,m)=1，表示整数，表示整数n=1n=1只有一个分划，不管最大被加数的上限只有一个分划，不管最大被加数的上限m m是多大。是多大。第35页，此课件共52页哦算法如下算法如下：Divinteger(n,Divinteger(n,m)m)if if（n n 1 1 or or m m n1 or m n

26、）Error(Error(“输入参数错误输入参数错误”)；/*n/*n，m1 Q(n,m)m1 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)while(n=10)print(n mod 10);print(n mod 10);n=n10;n=n10;print(n);print(n);第39页，此课件共52页哦递归算法如下：递归算法如下：f2(n)f2(n)if(n10)if(n=10)while(n=10)ai=n mod 10;ai=n

27、 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);循环算法如下：循环算法如下：第42页，此课件共52页哦与与f2f2不不同同，递递归归算算法法是是先先递递归归地地求求n10n10的的个个位位数数字字，然然后后再再求求个个位位数数字字n n的的个个位位数数字字并并输输出出。这这样样输输出出操操作作是是在在回回溯溯时时完完成成的的。递递归归停停止止条条件件与与f2f2相同为相同为n10n10。递归算法如下：递归算法如下：f4(n)f4(n)if(n10)

28、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)and(jk)t=t+1;t=t+1;print(i,j,k);print(i,j,k);print(total=,t);print(total=,t);第47页，此课件共52页哦constitute2constitute2（）（）int n=5,r=3,i,j,k,t;int n=5,r=3,i,j,k,t;t=0;t=0;for(

29、i=1;i=n-r+1;i=i+1)for(i=1;i=n-r+1;i=i+1)for(j=i+1;j=n-r+2;j=j+1)for(j=i+1;j=n-r+2;j=j+1)for(k=j+1;k=n-r+3;k=k+1)for(k=j+1;k=n-r+3;k=k+1)t=t+1;t=t+1;print(i,j,k);print(i,j,k);print(total=,t);print(total=,t);第48页，此课件共52页哦 在循在循环环算法算法设计设计中，中，对对n=5n=5的的实实例，每个例，每个组组合中的数据从合中的数据从小到大排列或从大到小排列一小到大排列或从大到小排列一样样

30、可以可以设计设计出相出相应应的算法。的算法。但用但用递归递归思想思想进进行行设计时设计时，每个，每个组组合中的数据从大到小排合中的数据从大到小排列却是必列却是必须须的；因的；因为递归为递归算法算法设计设计是要找出大是要找出大规规模模问题问题与与小小规规模模问题问题之之间间的关系。的关系。用递归法设计此题：用递归法设计此题：第49页，此课件共52页哦 total=10total=10例如，当例如，当n=,r=3时，所有组合为：时，所有组合为：第50页，此课件共52页哦分析n=5,r=3时的10组组合数1 1）首首先先固固定定第第一一个个数数，其其后后就就是是n=4,r=2n=4,r=2的的组组合

31、合数数，共共6 6个个组组合。合。2 2）其其次次固固定定第第一一个个数数4 4，其其后后就就是是n=3,r=2n=3,r=2的的组组合合数数，共共3 3个个组合。组合。3 3）最后固定第一个数）最后固定第一个数3 3，其后就是，其后就是n=2,r=2n=2,r=2的组合数，共的组合数，共1 1个个组合。组合。至此找到了至此找到了“个数中个数的组合个数中个数的组合”与与“个数中个数中个数的组合、个数的组合、3 3个数中个数的组合、个数中个数的组合、2 2个数中个数的组合个数中个数的组合”的递归关系。的递归关系。第51页，此课件共52页哦则递归算法的三个步骤为：则递归算法的三个步骤为：1 1）一

32、一般般地地：n n个个数数中中r r个个数数组组合合递递推推到到“n-1n-1个个数数中中r-1r-1个个数数有有组组合合，n-2n-2个个数数中中r-1r-1个个数数有有组组合合，,r-1,r-1个个数数中中r-1r-1个个数有组合数有组合”，共，共n-r+1 n-r+1 次递归。次递归。2 2）递归的边界条件是的）递归的边界条件是的r=1r=1。3 3）函函数数的的主主要要操操作作就就是是输输出出，每每当当递递归归到到r=1r=1时时就就有有一一组组新新的的组合产生，输出它们和一个换行符。组合产生，输出它们和一个换行符。注注意意n=5,r=3n=5,r=3的的例例子子中中的的递递归归规规律律，先先固固定定5 5，然然后后要要进进行行多多次次递递归归也也就就是是说说，数数字字5 5要要多多次次输输出出，所所以以要要用用数数组组存存储储以以备备每每一一次次递递归归到到r=1r=1时时输输出出。同同样样每每次次向向下下递递归归都都要要用用到到数组，所以将数组设置为全局变量数组，所以将数组设置为全局变量。第52页，此课件共52页哦