python裘宗燕2ppt.ppt

基本编程技术-2,递归与循环计算Fibonacci的函数函数运行时间求最大公约数两个递归函数实例河内塔问题，换硬币问题简单递归和相互递归程序终止性,Fibonacci序列（递归程序示例）,Fibonacci（斐波那契）序列是一个重要的整数序列因意大利数学家而斐波那契(1175-1250)命名，最早源于印度有大量数学结果，在计算领域有许多特别重要的应用Fibonacci序列的定义F0=0,F1=1（基础情况）Fn=Fn-1+Fn-2,对所有n1（一般情况）序列的前几项：0,1,1,2,3,5,8,13,21,34,55,.Fibonacci序列的定义是递归定义基础情况，一般情况可归结到更简单情况（下标更小）可以直接做出一个递归定义的函数函数定义和计算试验（用38、39、40等实验）,计算的时间,函数fib的定义很好，与数学定义直接对应，简单、易理解但也不好：计算要花费很长时间（计算fib(100)需要百万年）现在的计算机非常快，但计算也要花时间有些程序的计算可能花很长时间解决某些复杂问题的程序必然需要非常长的时间看计算fib(5)的情况存在大量重复计算,计算有代价,实际计算由现实世界中的设备（目前是电子计算机）完成不是数学，不是抽象的理论每步计算都有代价，即使非常小但也不为0，累积起来就可能超过给定的任意大的数（这是数学）有代价是计算的一种本质特征，相关理论问题后面讨论一些情况：可能存在从理论上看能用计算机解决的问题，但我们不可能等到计算机给出解的那个时间编程时需要考虑计算的时间，寻找解决问题的高效方法（算法）永远有意义有些实际问题对计算完成的时间非常敏感例：ABS/EBD(电子制动分配)系统，天气预报系统等,为计算计时,统计程序或程序片段的计算时间，有助于理解程序的性质，实际中常需要做。现在介绍Python标准库的计时功能标准库包time提供了计时函数time，调用它得到从1970年1月1日开始的秒数。两次调用time就能为一段计算计时。例如：fromtimeimporttimedeftest_fib(n):t=time()f=fib(n)print(Fib+str(n)+=,f,Timing:,str(time()-t)+sn)函数的输出计算fib(n)的时间如果发现一个程序很慢，不能满足实际需要，可能做的一件事就是仔细检查程序，估计其中各部分的时间开销，设法改进,再看Fibonacci序列：另一种算法,对Fibonacci数的计算，换一种看法：基本情况已直接给定，由Fn-1和Fn可以递推得到Fn+1考虑定义一个基于递推循环的函数，从F0和F1出发，一步步向前递推，直至得到所需要的Fn考虑循环中的变量安排：用f1和f2记录已知的两个相邻Fibonacci值f1+f2是下一个Fib值需要知道算到第几个Fib值，k记录变量f1的值是Fkf1,f2和k需要在每次循环中更新f1,f2=f2,f1+f2k+=1,也可以用递归函数描述这种计算存在更快的算法,循环不变式,怎么确定下面循环能算出正确的结果？f1,f2=0,1#开始时分别表示F_0和F_1k=0whilek=0,n0，容易写出函数定义如果允许参数是任何整数（包括负数），需要加一些前处理,求最大公约数：辗转相除,还可以从大到小循环检查找到的第一个能同时整除两个数的d就是最大公约数求最大公约数的经典算法是辗转相除法，又称为欧几里得算法。它利用下面关系,利用这个关系实现一个求gcd的函数改造得到的函数，增加检查，可以能得到一个可以对任一对整数求最大公约数的函数,求最大公约数：辗转相除,函数定义（递归实现）：defgcd(m,n):ifn%m=0:returnmreturngcd(n%m,m)函数定义（循环实现）：defgcd(m,n):ifm=0:returnnwhilen%m!=0:m,n=n%m,mreturnm还要加上特殊情况处理。还需考虑如何论证循环程序的正确性（同样需要借助循环不变式的概念）,递归和循环,是不是递归函数一定比循环函数慢？为什么考虑递归程序有价值？回答：不一定例如Fibonacci的递归和循环实现采用了不同算法，完全可以用递归实现第二种算法为什么需要递归定义？不少算法用递归的方式描述简单而自然，正确性很容易看清楚。用循环方式描述却很难/复杂/意义不清晰后面学习中还会看到，在计算中需要处理的许多结构本身就是递归的，用递归的方式处理非常自然,河内塔（梵塔）问题,问题描述：神庙有三根细长玉石圆柱，64个大小不等的有孔金盘，下大上小套在圆柱A上（梵塔）。需要把圆盘从该圆柱搬到圆柱B，规则是每次搬一个圆盘，不允许把大盘放到小盘上。要求写程序模拟这个过程初步想想好像没有明显的规律解决问题关键是看到问题的递归性质,假设能把63个圆盘从A搬到C（用B辅助），把A的最后圆盘直接搬到B，再把C上63个圆盘搬到B，搬63个与搬64个类似。分步：这样就把搬64个圆盘的问题归结为两次搬63个圆盘的问题不难定义解决问题的递归函数，需要引进表示圆盘个数的参数不容易把这个问题转为循环程序（可以做，但比较复杂）,递归实例：换硬币,一个递归程序实例也可以用循环的方式写程序，但比较复杂，也不那么清晰人民币硬币有1分、2分、5分、10分、50分和100分。给定一定款额，问将其换成硬币有多少种不同兑换方式递归的看法：币值n的兑换方式数等于用了一个硬币a之后na的兑换方式数，加上不用硬币a时n的兑换方式数上面是递归。有几种（基础）情况可以直接得到结果：n等于0，说明找到一种兑换方式（1种兑换方式）n小于0，说明没找到兑换方式（0种兑换方式）货币数等于0说明没找到兑换方式（0种兑换方式）,递归实例：换硬币,考虑算法的实现，其中有些问题需要解决为取得硬币的币值，把硬币排顺序后编号1到6对应到1分到100分的硬币定义一个函数，实现这种对应。减一种硬币时编号范围减一前面有关分析可以直接翻译为一个递归定义的函数ccoins定义一个主函数，调用ccoins(6,n)这个函数用递归的方式写，很简单函数定义直接对应于前面的分析也可以用循环的方式写出程序，但比较复杂，也不那么清晰。有编程经验的同学自己试试，需要用一些高级技术,兑换硬币,硬币编号函数：defamount(k):ifk=1:return1ifk=2:return2ifk=3:return5ifk=4:return10ifk=5:return50ifk=6:return100主要函数：defccoins(k,n):ifn=0:return1ifk=0orn0:return0returnccoins(k,n-amount(k)+ccoins(k-1,n)defnum_coins(n):returnccoins(6,n),相互递归,有时需要两个或多个函数相互调用例如在f里调用g，在g里调用f这样的函数称为相互递归的函数Python（只）要求函数在使用时必须有定义前面定义的函数可以调用后面定义的函数只要实际调用时被调用函数已经定义定义函数时，用到的函数可以没定义，但在执行程序中调用函数时，被调用的函数必须有定义举例：两个相互递归的函数,终止性和循环程序,写程序时，需要考虑程序是否必定终止（对所有可能的输入都终止）。程序不保证终止，就不保证能给出最后结果直线型和分支程序必然终止（只要每个基本语句终止）循环程序则可能不终止（即使每个基本语句都终止）有些程序可能需要运行很长时间例：调和级数部分和，计算这个级数的前多少项之和能超过某个给定的数有关终止性的理论结果：程序终止性问题是不可判定的不存在判断任何程序对任何输入是否终止的有效方法直观说，就是无法写出一个软件，判断任意的一个程序对任意一个输入是否终止,循环程序和终止性,例（Collatzconjecture，猜想下面