循环与递归讲稿.ppt

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

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

2、设计要点3.1.2 递归设计要点递归设计要点3.1.3 递归与循环的比较递归与循环的比较3.1 循环与循环与递归递归第三页，讲稿共五十五页哦 1 1设计中要注意算法的效率设计中要注意算法的效率 2 2“自顶向下自顶向下”的设计方法的设计方法 3 3由具体到抽象设计循环结构由具体到抽象设计循环结构 第四页，讲稿共五十五页哦 循环体的特点是：循环体的特点是：“以不变应万变以不变应万变”。所谓所谓“不变不变”是指循环体内运算的表现形式是不变的是指循环体内运算的表现形式是不变的,如变量，控制结构如变量，控制结构，而每次具体的执行内容，而每次具体的执行内容数据数据却是不尽却是不尽相同的。在循环体内用不变

3、的运算表现形式去描述各种相似相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。的重复运算。1 1循环循环设计中要注意算法的效率设计中要注意算法的效率第五页，讲稿共五十五页哦【例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)!算法设计算法设计1 1：多数初学者会直接利用题目中累：多数初学者会直接利用题目中累加项通式，

4、构造出循环体不变式为：加项通式，构造出循环体不变式为：S=S+S=S+（-1-1）n+1n+1/(2n-1)!/(2n-1)!需要用二重循环来完成算法，算法需要用二重循环来完成算法，算法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 sign=sign*(-1);(-1);s=s+sign/t;s=s+sign/t;print(“Snm=”,s);print(“Snm=”,s);main()main()int i,n,j,sign=1;int i,n,j,sign=

5、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 for(j=1;j=2*i-1;j=j+1)i-1;j=j+1)t=tt=t*j;j;sign=1;sign=1;第七页，讲稿共五十五页哦算法分析：n以上算法是二重循环来完成以上算法是二重循环来完成，但算法的效率却太低是，但算法的效率却太低是O（n2）。）。当前一次循环已求出当前一次循环已求出7！，当这次要想求！，当这次要想求9！时，没必要再从！时，没必要再从1去累乘到

6、去累乘到9，只需要充分利用前一次的结果，用，只需要充分利用前一次的结果，用7！*8*9即可即可得到得到9！，模型为！，模型为An=An-1*1/(2*n-2)*(2*n-1)。另外运算。另外运算sign=sign*(-1);总共也要进行总共也要进行n*(n-1)/2次乘法，这也是次乘法，这也是没有必要的。下面我们就进行改进。没有必要的。下面我们就进行改进。第八页，讲稿共五十五页哦数学模型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=

7、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=tt=t*(2(2*i-2)i-2)*(2(2*i-1);t=ti-1);t=t*2 2*i i*(2(2*i+1);i+1);s=s+sign/t;s=s+sign/t;s=s+sign/t;s=s+sign/t;print(“Sum=”,s);print(“Sum=”,s);第九页，讲稿共五十五页哦算法分析

8、：按照数学模型2，只需一重循环就能解决问题算法的时间复杂性为O（n）。算法说明算法说明2 2第十页，讲稿共五十五页哦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是是“完数完数”。编算法找出。编算法找出1000

9、1000之内的所有完数，并按下面格式输之内的所有完数，并按下面格式输出其因子：出其因子：28 its factors are 128 its factors are 1，2 2，4 4，7 7，1414。第十一页，讲稿共五十五页哦1 1）这里不是要质因数，所以找到因数后也无需将其从数）这里不是要质因数，所以找到因数后也无需将其从数据中据中“除掉除掉”。2 2）每个因数只记一次，如）每个因数只记一次，如8 8的因数为的因数为1 1，2 2，4 4而不是而不是1 1，2 2，2 2，2 2（注：本题限定因数不包括这个数本身）（注：本题限定因数不包括这个数本身）第十二页，讲稿共五十五页哦1 1）顶层

10、算法）顶层算法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 是是“完数完数”第十三页，讲稿共五十五页哦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 m

11、od j=0)(j是是i i的因素的因素)s=s+j;)s=s+j;if if （s=is=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 if （s=is=i）按格式输出结果按格式输出结果 4）考虑输出格式判断i是否“完数”算法n考虑到要按格式输出结果，应该开辟数组存储考虑到要按格式输出结果，应该开辟数组存储数据数据i的所有因子，并

12、记录其因子的个数，因的所有因子，并记录其因子的个数，因此算法细化如下：此算法细化如下：第十五页，讲稿共五十五页哦算法如下：算法如下：main()int i,k,j,s,a20;for(i=1;i=1000;i+)s=1;/*两个赋初值语句两个赋初值语句s=1,k=0 k=0;一定要位于外部循环的内部一定要位于外部循环的内部*/for(j=2;ji;j+)if(i mod j)=0)s=s+j;ak=j;k+;if(i=s)print(s,“its factors are:”,1);for(j=0;ik;j+)print(“,”,ak);第十六页，讲稿共五十五页哦【例3】求一个矩阵的鞍点 (即在

13、行上最小而在列上最大的点)。算法设计：算法设计：1）在第一行找最小值，并记录其列号。）在第一行找最小值，并记录其列号。2）然后验证其是否为所在列的最大值，如果是，则找到问）然后验证其是否为所在列的最大值，如果是，则找到问题的解；否则，则继续在下一行找最小值题的解；否则，则继续在下一行找最小值 。第十七页，讲稿共五十五页哦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;

14、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 第十八页，讲稿共五十五页哦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(“th

15、e result is a“,i print(“the result is a“,i，“”,minj,“=”,minj,“=”，t);t);考虑到会有无解的情况，设置标志量考虑到会有无解的情况，设置标志量kzkz，kz=0kz=0代表无解，找到一个解后，代表无解，找到一个解后，kzkz被赋值为被赋值为1 1，就不再继续找鞍点的工作。，就不再继续找鞍点的工作。请考虑是否有多解的可能性吗？若有，请改写算法，找出矩阵中所有的鞍请考虑是否有多解的可能性吗？若有，请改写算法，找出矩阵中所有的鞍点。点。第十九页，讲稿共五十五页哦算法如下：算法如下：buck()int a1010;int i,j,k,min

16、j,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;break;if(kz=0)print(“no solution!”);能否不用能否不用continue达到达到目的目的第二十页，讲稿共五十五页哦 对于不太熟悉的

17、问题，其数学模型或对于不太熟悉的问题，其数学模型或“机械化操作步骤机械化操作步骤”的不易抽象，下面看一个由具体到抽象设计循环细节的例的不易抽象，下面看一个由具体到抽象设计循环细节的例题。题。【例例4 4】编写算法：打印具有下面规律的图形。编写算法：打印具有下面规律的图形。1 1 5 2 5 2 8 6 3 8 6 3 10 9 7 4 10 9 7 4 3由具体到抽象设计循环结构第二十一页，讲稿共五十五页哦容易发现图形中自然数在矩阵中排列的规律，题目中容易发现图形中自然数在矩阵中排列的规律，题目中1 1，2 2，3 3，4 4所所在位置我们称为第在位置我们称为第1 1层（主对角线），例图中层（

18、主对角线），例图中5 5，6 6，7 7所在位置我们称为所在位置我们称为第二层，第二层，。一般地，第一层有。一般地，第一层有n n个元素，第二层有个元素，第二层有n-1n-1个元素个元素基于以上数据变化规律，以层号作为外层循环，循环变量为基于以上数据变化规律，以层号作为外层循环，循环变量为i i（范围为（范围为1n1n）；以层内元素从左上到右下的序号作为内循环，循环变量为）；以层内元素从左上到右下的序号作为内循环，循环变量为j j（范围为（范围为1n+1-i1n+1-i）。这样循环的执行过程正好与）。这样循环的执行过程正好与“摆放摆放”自然自然数的顺序相同。用一个变量数的顺序相同。用一个变量k

19、 k模拟要模拟要“摆放摆放”的数据，下面的问题就的数据，下面的问题就是怎么样将数据存储到对应的数组元素。是怎么样将数据存储到对应的数组元素。算法设计：第二十二页，讲稿共五十五页哦 数组元素的存取，只能是按行、列号操作的。所以下面用由具体到抽象数组元素的存取，只能是按行、列号操作的。所以下面用由具体到抽象设计循环的设计循环的“归纳法归纳法”，找出数组元素的行号、列号与层号，找出数组元素的行号、列号与层号i i及层内序号及层内序号j j的的关系：关系：1.1.每层内元素的列号都与其所在层内的序号每层内元素的列号都与其所在层内的序号j j是相同的。因为每层的是相同的。因为每层的序号是从第一列开始向右

20、下进行。序号是从第一列开始向右下进行。2.2.元素的行与其所在的层号及在层内的序号均有关系元素的行与其所在的层号及在层内的序号均有关系,具体地：具体地：第一层行号第一层行号1n1n，行号与，行号与j j同；同；第二层行号第二层行号2n2n，行号比，行号比j j大大1 1；第三层行号第三层行号3n3n，行号比，行号比j j大大2 2；行号起点随层号行号起点随层号i i增加而增加，层内其它各行的行号又随层内序号增加而增加，层内其它各行的行号又随层内序号j j增加而增加，由于编号起始为增加而增加，由于编号起始为1 1，i i层第层第j j个数据的列下标为个数据的列下标为i-1+ji-1+j。综合以上

21、分析综合以上分析,i,i层第层第 j j个数据对应的数组元素是个数据对应的数组元素是ai-1+jjai-1+jj。第二十三页，讲稿共五十五页哦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)pri

22、nt(“print(“换行符换行符”););for(j=1;j=i;j=j+1)for(j=1;j0)/*0阶的汉诺塔问题当作停止条件阶的汉诺塔问题当作停止条件*/2)hanoi(n-1,a,c,b);3)输出输出“Move dise”,n.”from pile”,a,”to”b);4)haboi(n-1,c,b,a);5)endif 第三十三页，讲稿共五十五页哦【例例2 2】整数的分划问题整数的分划问题 对于一个正整数对于一个正整数n n的分划就是把的分划就是把n n写成一系列正整数之和的表达式。例写成一系列正整数之和的表达式。例如，对于正整数如，对于正整数n=6n=6，它可以分划为：，它可

23、以分划为：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，第六行的数据不超，第六行的数据不超过过1”1”。因此，定义一个函数因此，定义一个函数Q(n,m)Q(n,m)，表示整数表示整数n n的的“任何被加数都不超过任何被加数都不超过m”m

24、”的分划的数目，的分划的数目，n n的所有分划的的所有分划的数目数目P(n)=Q(n,n)P(n)=Q(n,n)。第三十四页，讲稿共五十五页哦模型建立模型建立：一般地一般地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

25、,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)=12)Q(1,m)=1，表示整数，表示整数n=1n=1只有一个分划，不管最大被加数的上只有一个分划，不管最大被加数的上限限m m是多大。是多大。第三十五页，讲稿共五十五

26、页哦算法如下算法如下：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 if（n n =10)while(n=10)print(n mod 10);print(n mod 10);n=n10;n=n10;print(n);print(n);第三十九

27、页，讲稿共五十五页哦递归算法如下：递归算法如下：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不同，递归算法是先递归地求不同，递归算法是先递归地求n10n10的个位数字，然后再求个的个位数字，然后再求个位数字位数字n n的个位数字并输出。这样输出操作是在回溯时完成的。递归停的个

28、位数字并输出。这样输出操作是在回溯时完成的。递归停止条件与止条件与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)and(jk)t=t+1;t=t+1;print(i,j,k);print(i,j,k);print(total=,t);print(total=,t);第四十七页，讲稿共五

29、十五页哦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;k=k;i-)ak=i;if(k1)comb(i-1,k-1);else for(j=a0;j0;j-)print(aj);print(“换行符换行符”);constitute3()int n

30、,r;print(“n,r=”);input(n,r);if（rn）print(“Input n,r error!”);else a0=r;comb(n,r);/调用递归过程调用递归过程/第五十三页，讲稿共五十五页哦分析：分析：算法算法2 2递归的深度是递归的深度是r r，每个算法要递归，每个算法要递归m-k+1m-k+1次，所以的时间复杂性是次，所以的时间复杂性是O（r r*n n）。）。递归是一种强有力的算法设计方法。递归是一种比递归是一种强有力的算法设计方法。递归是一种比循环更强、更好用的实现循环更强、更好用的实现“重复操作重复操作”的机制。因为递的机制。因为递归不需要编程者（算法设计者）自己构造归不需要编程者（算法设计者）自己构造“循环不变式循环不变式”，而只需要找出递归关系和最小问题的解。递归在很，而只需要找出递归关系和最小问题的解。递归在很多算法策略中得以运用，如：分治策略、动态规划、图多算法策略中得以运用，如：分治策略、动态规划、图的搜索等算法策略。的搜索等算法策略。综合以上讨论，可以得出以下结论：综合以上讨论，可以得出以下结论：第五十四页，讲稿共五十五页哦感谢大家观看感谢大家观看第五十五页，讲稿共五十五页哦