循环与递归精选PPT.ppt

《循环与递归精选PPT.ppt》由会员分享，可在线阅读，更多相关《循环与递归精选PPT.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、而每次具体的执行内容数据数据却是却是不尽相同的。在循环体内用不变的运算表现形式去描述各不尽相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。种相似的重复运算。1 1循环循环设计设计中要注意算法的效率中要注意算法的效率第5页，讲稿共55张，创作于星期六【例1】求1/1!-1/3!+1/5!-1/7!+（-1）n+1/(2n-1)!n分析：此问题中既有分析：此问题中既有累加累加又有又有累乘累乘，准确地说，准确地说累加的对象是累乘的结果。累加的对象是累乘的结果。数学模型数学模型1 1：Sn=Sn-1+Sn=Sn-1+（-1-1）n+1n+1/(2n-1)!/(2n-1)!算法设计算法设

4、计1 1：多数初学者会直接利用题目中累：多数初学者会直接利用题目中累加项通式，构造出循环体不变式为：加项通式，构造出循环体不变式为：S=S+S=S+（-1-1）n+1n+1/(2n-1)!/(2n-1)!需要用二重循环来完成算法，算法需要用二重循环来完成算法，算法1 1如下：如下：第6页，讲稿共55张，创作于星期六算法如下：求（求（-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(“Snm=”,s);print(“Snm=”,s);

5、main()main()int i,n,j,sign=1;int 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;求阶乘求阶乘 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页，讲稿共55张，创作于星期六算法分析：n以上算法是二重循环来完成以上算法是二重循环来完成，但算法的效率却太低是，但算法的效率却太低是O（n2）。）。当当前前一一次

6、次循循环环已已求求出出7！，当当这这次次要要想想求求9！时时，没没必必要要再再从从1去去累累乘乘到到9，只只需需要要充充分分利利用用前前一一次次的的结结果果，用用7！*8*9即即可可得得到到9！，模模型型为为An=An-1*1/(2*n-2)*(2*n-1)。另另外外运运算算sign=sign*(-1);总总共共也也要要进进行行n*(n-1)/2次次乘乘法法，这这也也是是没没有必要的。下面我们就进行改进。有必要的。下面我们就进行改进。第8页，讲稿共55张，创作于星期六数学模型2：Sn=Sn-1+（-1）n+1An；An=An-1*1/(2*n-2)*(2*n-1)main()main()int

7、 i,n,sign;int i,n,sign;float s,t=1;float s,t=1;input(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

8、/t;print(“Sum=”,s);print(“Sum=”,s);第9页，讲稿共55张，创作于星期六算法分析：按照数学模型2，只需一重循环就能解决问题算法的时间复杂性为O（n）。算法说明算法说明2 2第10页，讲稿共55张，创作于星期六2“自顶向下”的设计方法 自自顶顶向向下下的的方方法法是是从从全全局局走走向向局局部部、从从概概略略走走向向详详尽尽的的设设计计方方法法。自自上上而而下下是是系系统统分分解解和和细细化的化的过过程。程。【例例2 2】编算法找出编算法找出10001000以内所有完数以内所有完数例例如如，2828的的因因子子为为1 1、2 2、4 4、7 7，1414，而而28

9、=1+2+4+7+1428=1+2+4+7+14。因因此此2828是是“完完数数”。编编算算法法找找出出10001000之之内内的的所所有有完完数数，并并按按下下面面格格式式输出其因子：输出其因子：28 its factors are 128 its factors are 1，2 2，4 4，7 7，1414。第11页，讲稿共55张，创作于星期六1 1）这这里里不不是是要要质质因因数数，所所以以找找到到因因数数后后也也无无需需将将其其从从数数据据中中“除掉除掉”。2 2）每每个个因因数数只只记记一一次次，如如8 8的的因因数数为为1 1，2 2，4 4而而不不是是1 1，2 2，2 2，2

10、2（注：本题限定因数不包括这个数本身）（注：本题限定因数不包括这个数本身）第12页，讲稿共55张，创作于星期六1 1）顶层算法）顶层算法for(i=2;i=n;i=i+1)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页，讲稿共55张，创作于星期六3 3）进一步细化）进一步细化判断判断i i是否是否“

11、完数完数”算法算法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;)s=s+j;if if （s=is=i）i i是是“完数完数”;第14页，讲稿共55张，创作于星期六 定义数组定义数组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）考

12、虑输出格式判断i是否“完数”算法n考虑到要按格式输出结果，应该开辟数组存储考虑到要按格式输出结果，应该开辟数组存储数据数据i的所有因子，并记录其因子的个数，因的所有因子，并记录其因子的个数，因此算法细化如下：此算法细化如下：第15页，讲稿共55张，创作于星期六算法如下：算法如下：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,“itsfacto

13、rsare:”,1);for(j=0;ik;j+)print(“,”,ak);第16页，讲稿共55张，创作于星期六【例3】求一个矩阵的鞍点 (即在行上最小而在列上最大的点)。算法设计：算法设计：1）在第一行找最小值，并记录其列号。）在第一行找最小值，并记录其列号。2）然后验证其是否为所在列的最大值，如果是，则找到问）然后验证其是否为所在列的最大值，如果是，则找到问题的解；否则，则继续在下一行找最小值题的解；否则，则继续在下一行找最小值 。第17页，讲稿共55张，创作于星期六for(i=0;in;i=i+1)i=0;in;i=i+1)找第找第i i行上最小的元素行上最小的元素t t及所在列及所在

14、列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;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页，讲稿共55张，创作于星期六3 3）检验）检验t t是否第是否第minjminj列的最大值，是，则输出鞍点列的最大值，是，则输出鞍点;for(k=0

15、;kn;k=k+1)for(k=0;kt)break;if(akminjt)break;if(kn)continue;if(kn)continue;print(“the result is a“,i print(“the result is a“,i，“”,minj,“=”,minj,“=”，t);t);考考虑虑到到会会有有无无解解的的情情况况，设设置置标标志志量量kzkz，kz=0kz=0代代表表无无解解，找找到到一一个个解解后后，kzkz被赋值为被赋值为1 1，就不再继续找鞍点的工作。，就不再继续找鞍点的工作。请请考考虑虑是是否否有有多多解解的的可可能能性性吗吗？若若有有，请请改改写写算算

16、法法，找找出出矩矩阵阵中中所所有的鞍点。有的鞍点。第19页，讲稿共55张，创作于星期六算法如下：算法如下：buck()int a1010;int i,j,k,minj,t,n=10,kz=0;/*minj代表当前行中最小值的列下标；设置标志量kz*/readmtr(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(“the result is a“,i,“”,minj,“=”，aiminj);kz=1

17、;break;if(kz=0)print(“no solution!”);能否不用能否不用continue达到达到目的目的第20页，讲稿共55张，创作于星期六 对对于于不不太太熟熟悉悉的的问问题题，其其数数学学模模型型或或“机机械械化化操操作作步步骤骤”的的不易抽象，下面看一个由具体到抽象设计循环细节的例题。不易抽象，下面看一个由具体到抽象设计循环细节的例题。【例例4 4】编写算法：打印具有下面规律的图形。编写算法：打印具有下面规律的图形。1 1 5 2 5 2 8 6 3 8 6 3 10 9 7 4 10 9 7 4 3由具体到抽象设计循环结构第21页，讲稿共55张，创作于星期六容容易易发

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

19、围围为为1n+1-i1n+1-i）。这这样样循循环环的的执执行行过过程程正正好好与与“摆摆放放”自自然然数数的的顺顺序序相相同同。用用一一个个变变量量k k模模拟拟要要“摆摆放放”的的数数据据，下下面面的的问问题题就是怎么样将数据存储到对应的数组元素。就是怎么样将数据存储到对应的数组元素。算法设计：第22页，讲稿共55张，创作于星期六 数数组组元元素素的的存存取取，只只能能是是按按行行、列列号号操操作作的的。所所以以下下面面用用由由具具体体到到抽抽象象设设计循环的计循环的“归纳法归纳法”，找出数组元素的行号、列号与层号，找出数组元素的行号、列号与层号i i及层内序号及层内序号j j的关系：的关

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

21、j j增加而增加，由于编号起始为增加而增加，由于编号起始为1 1，i i层第层第j j个数据的列下标为个数据的列下标为i-1+ji-1+j。综合以上分析综合以上分析,i,i层第层第 j j个数据对应的数组元素是个数据对应的数组元素是ai-1+jjai-1+jj。第23页，讲稿共55张，创作于星期六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

22、;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阶的汉诺塔问题当作停止条件阶的汉诺塔问题当作停止条件*/2)hanoi(n-1,a,c,b);3)输出输出“Movedise”,n.”frompile”,a,”to”b);4)haboi(n-1,c,b,a);5)endif 第33页，讲稿共55张，创作于星期六【例例2 2】整数的分划问题整数的分划问题 对于一个正整数对于一个正整数n

23、 n的分划就是把的分划就是把n n写成一系列正整数之和的表达式。例如，写成一系列正整数之和的表达式。例如，对于正整数对于正整数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+1+1,2+1+1+1+1 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，第六行的数据不，第六

24、行的数据不超过超过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页，讲稿共55张，创作于星期六模型建立模型建立：一般地一般地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-

25、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)表示被加数中包含表示被加数中包含(注意不是小于注意不是小于)m)m的分划的数目，的分划的数目，递归的停止条件：递归的停止条件：1)Q(n,1)=11)Q(n,1)=1，表示当最大的被加数是，表示当最大的被加数是1 1时，该整数时，该整数n n只有一种分划，只有一种分划，即即n n个个1 1相加；相加；2)Q(1,m)

26、=12)Q(1,m)=1，表示整数，表示整数n=1n=1只有一个分划，不管最大被加数的上只有一个分划，不管最大被加数的上限限m m是多大。是多大。第35页，讲稿共55张，创作于星期六算法如下算法如下：Divinteger(n,Divinteger(n,m)m)if if（n n 1 1 or or m m n1 or m n）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

27、 if（n n =10)while(n=10)print(n mod 10);print(n mod 10);n=n10;n=n10;print(n);print(n);第39页，讲稿共55张，创作于星期六递归算法如下：递归算法如下：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);循环算法如下：循环算法如下：第42页，讲稿共55张，创作于星期六与

28、与f2f2不不同同，递递归归算算法法是是先先递递归归地地求求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)a

29、nd(ij)and(jk)t=t+1;t=t+1;print(i,j,k);print(i,j,k);print(total=,t);print(total=,t);第47页，讲稿共55张，创作于星期六constitute2constitute2（）（）int n=5,r=3,i,j,k,t;int n=5,r=3,i,j,k,t;t=0;t=0;for(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

30、;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）print(“Inputn,rerror!”);elsea0=r;comb(n,r);/调用递归过程调用递归过程/第53页，讲稿共55张，创作于星期六分析：分析：算法算法2 2递归的深度是递归的深度是r r，每个算法要递归，每个算法要递归m-k+1m-k+1次，所以的时间复杂性是次，所以的时间复杂性是O（r*nr*n）。）。递递归归是是一一

31、种种强强有有力力的的算算法法设设计计方方法法。递递归归是是一一种种比比循循环环更更强强、更更好好用用的的实实现现“重重复复操操作作”的的机机制制。因因为为递递归归不不需需要要编编程程者者（算算法法设设计计者者）自自己己构构造造“循循环环不不变变式式”，而而只只需需要要找找出出递递归归关关系系和和最最小小问问题题的的解解。递递归归在在很很多多算算法法策策略略中中得得以以运运用用，如如：分分治治策策略略、动动态态规规划划、图图的搜索等算法策略。的搜索等算法策略。综合以上讨论，可以得出以下结论：综合以上讨论，可以得出以下结论：第54页，讲稿共55张，创作于星期六感感谢谢大大家家观观看看第55页，讲稿共55张，创作于星期六