C语言课件第9部分递归程序设计.ppt
《C语言课件第9部分递归程序设计.ppt》由会员分享,可在线阅读,更多相关《C语言课件第9部分递归程序设计.ppt(49页珍藏版)》请在装配图网上搜索。
第九部分递归程序设计技术,学习程序设计需要注意规律性的东西,本章内容,递归与循环递归函数的执行过程递归函数效率,循环与递归,循环程序用于描述需要重复进行计算高级语言里,也常见用递归来实现重复的计算。递归recursion,recursivealgorithm函数或过程调用自身C语言允许递归,可以在函数内调用自身,常常使程序更简单清晰。,1.阶乘和乘幂,例:定义计算整数阶乘的函数12(n-1)n本例中,乘的次数依赖于n,计算所需的次数定义时无法确定。这是一种典型循环情况计算“次数”依赖某些参数的值。,程序,longfact1(longn)longfac,i;for(fac=1,i=1;i=n;i+)fac*=i;returnfac;,阶乘函数的精确定义,是一种递归定义的形式要解决规模为n的问题,要先解决规模为n-1的子问题,依此类推。如果高级语言允许递归定义函数,就可以直接翻译为程序。C允许递归定义在函数定义内直接或间接地调用被定义函数本身。,写成递归函数,longfact(longn)returnn=0?1:n*fact(n-1);longfact(longn)if(n=1)return1;returnn*fact(n-1);,longfact(1)if(1=1)return1;return1*fact(1-1);,longfact(2)if(2=1)return1;return2*fact(2-1);,longfact(3)if(3=1)return1;return3*fact(3-1);,main()printf(“%d”,fact(3);,蓝线:函数调用线路黄线:函数内部执行路线红线:函数执行结束返回主调函数的路线,longfact(longn)if(n1)1,1,2,3,5,8,13,21,34,65,99,用递归程序实现,longfib(intn)returnn2?1:fib(n-1)+fib(n-2);,问题分析:这个程序好不好?一方面,很好!程序与数学定义的关系很清晰,正确性容易确认,定义易读易理解,例fib(5)调用过程,fib(5),fib(4),fib(3),fib(3),fib(2),fib(2),fib(1),fib(1),fib(0),fib(1),fib(0),fib(2),fib(1),fib(1),fib(0),存在什么问题?,问题,存在大量重复计算,参数越大重复计算越多。有关系吗?随着参数增大,计算中重复增长迅速,最快的微机上一分钟大约可以算出fib(45)参数加1,fib多用近一倍时间(指数增长)。最快的微机一小时算不出fib(55),算fib(100)要数万年计算需要时间,复杂计算需要很长时间。这是计算机的本质特征和弱点。说明它不是万能,有些事情“不能”做。,计算复杂度,人们发现了许多实际问题,理论上说可用计算机解决(可写出计算它的程序),但对规模大的情况(“大的参数n”),人类永远等不到计算完成。这时能说问题解决了吗?计算中有一大类问题被称为的“难解问题”,其中有许多很实际的问题,如规划、调度、优化等。解决这些问题,需要理论和实际技术的研究。另外,对于许多问题的实用的有效算法,有极大的理论价值和实际价值。计算复杂性,难解问题,“P=NP?”问题。,阅读材料:NP问题,AproblemisassignedtotheNP(nondeterministicpolynomialtime)classifitissolvableinpolynomialtimebyanondeterministicTuringmachine.AP-problem(whosesolutiontimeisboundedbyapolynomial)isalwaysalsoNP.IfaproblemisknowntobeNP,andasolutiontotheproblemissomehowknown,thendemonstratingthecorrectnessofthesolutioncanalwaysbereducedtoasingleP(polynomialtime)verification.IfPandNParenotequivalent,thenthesolutionofNP-problemsrequires(intheworstcase)anexhaustivesearch.Linearprogramming,longknowntobeNPandthoughtnottobeP,wasshowntobePbyL.Khachianin1979.ItisanimportantunsolvedproblemtodetermineifallapparentlyNPproblemsareactuallyP.AproblemissaidtobeNP-hardifanalgorithmforsolvingitcanbetranslatedintooneforsolvinganyotherNP-problem.ItismucheasiertoshowthataproblemisNPthantoshowthatitisNP-hard.AproblemwhichisbothNPandNP-hardiscalledanNP-completeproblem.,为计算过程计时,统计程序或程序片段的计算时间有助于理解程序性质。许多语言或系统都提供了内部计时功能。有关函数在time.h,统计程序时间时程序头部应写#include在程序里计时,通常写表达式clock()/CLOCKS_PER_SEC得到从程序开始到表达式求值时所经历的秒数。,确定计算fib(45)所需要的时间的程序#include#includelongfib(intn)returnn=1?1:fib(n-1)+fib(n-2);intmain()doublex;x=clock()/CLOCKS_PER_SEC;fib(45);x=clock()/CLOCKS_PER_SEC-x;printf(Timingfib(45):%f.n,x);return0;,Fibonacci数的迭代计算,Fibonacci数的递推计算,易见1)f1和f2是12)知道fn-2和fn-1连续两个Fibonacci数,就可算出下一个fn递推计算方式逐个往后推,可用循环实现,递推方案,longfib1(intn)longf1=1,f2=1,f3,i;if(n=1)return1;for(f3=f2+f1,i=2;in;+i)f1=f2;f2=f3;f3=f1+f2;returnf3;,做一次递推,fn,fn-1,fn-2,程序分析,for(f3=f2+f1,i=2;in;+i)f1=f2;f2=f3;f3=f1+f2;循环结束时i等于n,这时c的值是fn。要得到此结论,可设法证明:每次判断i的值时f3正是fi。,归纳证明,第一次判断时i的值是2,f3的值2,正是fi(且f1的值是fi-1,f2的值是fi-2)若某次判断时i值是k(小于n),循环体中的语句使f1变成fk-1,f2变成fk,f3变成fk+1。i值增1使我们又有f1为fi-2,f2变成fi-1,f3变成fi根据归纳法,每次判断i的值时f3正是fi。,如何保证循环的正确执行,循环实现重复性计算,循环体可能执行多次。如何保证对各种数据都能正确完成计算?循环中变量不断变化。写循环要考虑变量间的关系,保证某些关系在循环中不变:循环的不变关系。写循环时最重要的就是想清循环中应维持变量间的什么关系才能保证循环结束时变量能处在所需状态。写完循环后应仔细检查是否满足要求。循环不变关系(循环不变量)是理解循环、写好循环的关键。,问题,本例中用循环的函数比用递归定义的好吗?新函数在计算时间上有极大优越性。计算时间由循环次数确定。循环体执行次数大致为n。fib(100)只需约100次循环,几乎察觉不到所花费时间。新函数定义较复杂,有复杂的循环。要理解程序意义,确认函数对任何参数都算出Fibonacci值,需要借助“循环不变关系”的概念和细致分析。,注意:这个例子并不是说明递归比循环的效率低。完全可以写出计算fib的同样高效的递归定义的函数,最大公约数,求两个整数的最大公约数(greatestcommondivisor,GCD),写函数longgcd(long,long)解法1从某个数开始,逐个判断当前数是否能同时整除m和n,在这个过程中记录下能同时整除m和n的最大整数。需要用一个辅助变量k记录当前需要判断的数。用一个循环实现k顺序取值初值设为1每次判断完后增1直到k大于m和n中其中的一个为止记下循环过程中出现的新的m和n的公约数,作为新的最大公约数用变量d表示当前的最大公约数初值1(是公约数),遇到新的公约数(一定更大)时记入d,程序,有了d及其初值,k可以从2开始循环。函数定义longgcd(longm,longn)longd=1,k=2;for(;kn?n:m);/把k设为n的较小者m%k!=0|n%k!=0;k-);/*空循环体*/returnk;/*循环结束时k是最大公约数*/,过程示例,两种方式比较,本方法比前一方法简单一些。两种方法的共同点是重复测试。这类方法的缺点是效率较低,参数大时循环次数很多。,解法2辗转相除法,求GCD有著名的欧几里德算法(欧氏算法,辗转相除法)。最大公约数的递归定义:,例,例1gcd1(70,30)m=70,n=30m%n10gcd(30,10)m=30,n=10m%n0例2gcd1(65,15)m=65,n=15m%n5gcd1(15,5)m=15,n=5m%n0,递归程序解决,函数定义与数学定义直接对应longgcd(longm,longn)returnm%n=0?n:gcd(n,m%n);假设第二个参数非0,且参数都不小于0。对欧氏算法的研究保证了本函数能结束,对较大的数计算速度也很快,远远优于顺序检查。,加入特殊情况处理,longgcd(longm,longn)if(m0)m=-m;if(n%cn,from,to);voidhenoi(intn,charfrom,charto,charby)if(n=1)moveone(from,to);elsehenoi(n-1,from,by,to);moveone(from,to);henoi(n-1,by,to,from);,moveone定义为函数是为了方便。函数调用:henoi(6,a,b,c);,hanio(3,a,b,c);hanio(2,a,c,b);moveone(a,b);hanio(2,c,b,a);,hanio(2,a,c,b)hanio(1,a,b,c);moveone(a,c);hanio(1,b,c,a);,hanio(1,a,b,c)moveone(a,b);,hanio(1,b,c,a)moveone(b,c);,hanio(2,c,b,a)hanio(1,c,a,b);moveone(c,b);hanio(1,a,b,c);,hanio(1,c,a,b)moveone(c,a);,hanio(1,a,b,c)moveone(a,b);,常见方法,设法确认程序对最基本的情况能正常工作解决了基本情况后再考虑更复杂的情况设法找出出错的规律性,检查出错时数据经过的执行流,逐步缩小可疑范围在程序中加入输出语句,检查重要变量的值的变化情况利用IDE的排错功能,本章要求,掌握递归的概念递归函数的编写方法理解递归函数的效率,本章结束,- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 课件 部分 递归 程序设计
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文