《python-裘宗燕-第三章1-ppt》由会员分享，可在线阅读，更多相关《python-裘宗燕-第三章1-ppt（23页珍藏版）》请在金锄头文库上搜索。
1、python-python-裘宗燕裘宗燕- -第三章第三章1-1-pptppt从问题到程序（Python程序设计）裘宗燕，2017/-2-学习编程学习编程n学编程并不是简单的经验积累，多写也未必就能把程序写好学编程并不是简单的经验积累，多写也未必就能把程序写好q需要学习前人编程中总结出的规律、模式、方法和技术需要学习前人编程中总结出的规律、模式、方法和技术q正确的好程序不是随便写出来的，也不应该是修修补补凑出正确的好程序不是随便写出来的，也不应该是修修补补凑出来的。需要认真的思考、评价、选择和决策来的。需要认真的思考、评价、选择和决策q通过认真学习怎样写好一个个小程序，掌握编程工作的基本通过认
2、真学习怎样写好一个个小程序，掌握编程工作的基本方法和技术，才可能在将来写出更大更复杂的程序方法和技术，才可能在将来写出更大更复杂的程序n初学编程，需要克服一些难点：初学编程，需要克服一些难点：q重复计算和循环是第一个难点，其中牵涉的因素比较多重复计算和循环是第一个难点，其中牵涉的因素比较多q第一个问题是函数定义，如何选择、设计、实现和使用第一个问题是函数定义，如何选择、设计、实现和使用这些是本章的主题这些是本章的主题从问题到程序（Python程序设计）裘宗燕，2017/-3-重复操作和循环程序重复操作和循环程序n本次课首先集中讨论循环程序的的设计和实现本次课首先集中讨论循环程序的的设计和实现q
3、直线型代码很容易写，分支代码也比较简单直线型代码很容易写，分支代码也比较简单q初学编程，最先遇到的难点是理解和掌握循环初学编程，最先遇到的难点是理解和掌握循环没有循环的程序都是平凡的程序。任何复杂一点的计算过程中没有循环的程序都是平凡的程序。任何复杂一点的计算过程中必然会出现重复性计算，需要用循环描述必然会出现重复性计算，需要用循环描述n为什么写循环？有很多情况。典型如：为什么写循环？有很多情况。典型如：q有一批类似数据，需要按同样方式处理有一批类似数据，需要按同样方式处理q需要以同样方式计算出一批结果需要以同样方式计算出一批结果q需要反复累积一些（按同样方式算出或获得的）数据需要反复累积一些
4、（按同样方式算出或获得的）数据q需要按同样方式反复从已有数据推算下一个（下一批）数据需要按同样方式反复从已有数据推算下一个（下一批）数据q从问题到程序（Python程序设计）裘宗燕，2017/-4-重复操作和循环程序重复操作和循环程序n写循环的前提是发现计算中需要（应该用）循环写循环的前提是发现计算中需要（应该用）循环q注意识别计算中需要重复执行的类似动作注意识别计算中需要重复执行的类似动作q引进循环，可以统一描述（完成）计算中的一批类似工作引进循环，可以统一描述（完成）计算中的一批类似工作n需要循环的一些情况需要循环的一些情况q需要多次做类似操作，次数较多，适合用循环需要多次做类似操作，次数
5、较多，适合用循环循环可能缩短程序，并容易检查循环可能缩短程序，并容易检查/维护维护/修改修改q重复操作的次数不能确定，结束条件由数据变化的情况决定，重复操作的次数不能确定，结束条件由数据变化的情况决定，就必须用循环就必须用循环q决定重复操作的因素来自函数参数或输入，必须用循环描述决定重复操作的因素来自函数参数或输入，必须用循环描述n生成华氏到摄氏温度的对照表，是典型的第一种情况生成华氏到摄氏温度的对照表，是典型的第一种情况n通过迭代改进求平方根，典型的第二种情况（通过迭代改进求平方根，典型的第二种情况（函数定义函数定义）从问题到程序（Python程序设计）裘宗燕，2017/-5-循环程序的因素
6、循环程序的因素n写循环的前提是看到了计算中需要重复操作，而且有规律可循写循环的前提是看到了计算中需要重复操作，而且有规律可循n写循环需要考虑的一些问题，基础是需要做什么写循环需要考虑的一些问题，基础是需要做什么q为完成循环计算需要引进哪些变量？怎样控制循环？为完成循环计算需要引进哪些变量？怎样控制循环？q循环开始前它们应该取什么值？循环开始前它们应该取什么值？q循环体中（一次迭代计算中）它们的值应该如何变化？循环体中（一次迭代计算中）它们的值应该如何变化？q在什么条件下结束（或继续）循环？在什么条件下结束（或继续）循环？q循环结束后怎么得到所需结果？循环结束后怎么得到所需结果？n具体问题是选择
7、哪种循环结构？具体问题是选择哪种循环结构？q循环的次数和方式清晰，可以通过一个循环变量和一个迭代循环的次数和方式清晰，可以通过一个循环变量和一个迭代器（如器（如range调用调用）控制，用控制，用for语句更简单清晰语句更简单清晰q不能确知循环的次数，循环方式复杂时，必须用不能确知循环的次数，循环方式复杂时，必须用while从问题到程序（Python程序设计）裘宗燕，2017/-6-循环程序的设计循环程序的设计n每个循环都可能用多种不同方式描述每个循环都可能用多种不同方式描述n例：求例：求13到到26的整数之和的整数之和q应该采用最简单，最清晰的描述方式应该采用最简单，最清晰的描述方式q尽可能
8、采用尽可能采用for语句和向上循环（循环变量值递增）语句和向上循环（循环变量值递增）n注意注意Python里整数范围的描述和意义（左闭右开）里整数范围的描述和意义（左闭右开）q说说“从从m到到n”总指总指m,.,n-1，即整数区间即整数区间m,n)qrange(n)，range(m,n)，range(m,n,d)都是都是n假设要写假设要写while循环，要求变量值大于循环，要求变量值大于20时结束时结束用用n=20或或n21作为条件都正确作为条件都正确按照按照Python的习惯，人们赞成后者（左闭右开）的习惯，人们赞成后者（左闭右开）n下面考虑一些典型的循环情况（下面考虑一些典型的循环情况（仅
9、供参考，不要当作教条仅供参考，不要当作教条）从问题到程序（Python程序设计）裘宗燕，2017/-7-循环：完成重复性工作循环：完成重复性工作n采用循环的最简单情况：需要重复做一批类似但相互无关的工作采用循环的最简单情况：需要重复做一批类似但相互无关的工作q对一系列数据做相同的计算，分别得到结果对一系列数据做相同的计算，分别得到结果q反复输出一批数据，反复输出一批数据，q例如前面的温度转换（生成各种表格），等等例如前面的温度转换（生成各种表格），等等n关键：关键：q计算或操作有统一模式，可以用一段代码描述计算或操作有统一模式，可以用一段代码描述q不同计算之间从差异就是一个或几个变量的取值，而
10、这些取不同计算之间从差异就是一个或几个变量的取值，而这些取值可以按一定的规律产生出来值可以按一定的规律产生出来n重复工作重复工作q识别和描述比较简单识别和描述比较简单q关键是总结共同计算模式，确定循环中变量取值的变化规律关键是总结共同计算模式，确定循环中变量取值的变化规律从问题到程序（Python程序设计）裘宗燕，2017/-8-循环：累积循环：累积n累积工作的特点是在重复性的工作中累积工作的特点是在重复性的工作中q需要用一个或几个变量去累积迭代中得到的数据需要用一个或几个变量去累积迭代中得到的数据q每次迭代把一些数据的信息每次迭代把一些数据的信息“记入记入”累积变量累积变量q它（它们）的值将
11、是循环的主要结果它（它们）的值将是循环的主要结果n累积中常用的操作如累积中常用的操作如+或或*经常能用到扩展赋值运算符经常能用到扩展赋值运算符+=，*=等等n累积程序的实例累积程序的实例q求整数求整数1到到100的立方和的立方和q数项级数前数项级数前n项的计算，如项的计算，如从问题到程序（Python程序设计）裘宗燕，2017/-9-循环：累积（带条件）循环：累积（带条件）n循环中的累积也可能还有条件。一般情况是，循环中的累积也可能还有条件。一般情况是，q通过某种统一方式枚举（生成、计算）出一些数据通过某种统一方式枚举（生成、计算）出一些数据q如果满足条件就将其如果满足条件就将其“记入记入”累
12、积数据累积数据n简单实例：简单实例：q求求100以内以内7的倍数中不能整除的倍数中不能整除3的整数之和的整数之和q输入的输入的10个整数中的偶数之和个整数中的偶数之和n这是一种典型的计算模式，称为这是一种典型的计算模式，称为“生成和筛选生成和筛选”q生成：产生出一批候选数据生成：产生出一批候选数据q筛选：从生成数据中选出满足某些条件的合格数据筛选：从生成数据中选出满足某些条件的合格数据q有时难以直接生成所需要的数据（序列），可以考虑生成更有时难以直接生成所需要的数据（序列），可以考虑生成更多数据，从中选出所需数据多数据，从中选出所需数据从问题到程序（Python程序设计）裘宗燕，2017/-1
13、0-循环：递推循环：递推n递推是在循环的每次迭代中，基于某个（些）变量的当前值，按递推是在循环的每次迭代中，基于某个（些）变量的当前值，按某种统一方式算出它（们）的下一个值。常见描述形式某种统一方式算出它（们）的下一个值。常见描述形式d=f(d,.)d的下个值需要通过的下个值需要通过d和其他数据，通过某种方法算出和其他数据，通过某种方法算出n求求x平方根程序是典型的递推，从一个近似值求出下一近似值平方根程序是典型的递推，从一个近似值求出下一近似值q数学定义：数学定义：x的平方根就是满足的平方根就是满足y*y=x的非负数的非负数yq计算的说明：计算的说明：1)任取任取z2)求出求出y=x/z3)
14、如果如果y*y足够接近足够接近x，那么那么y就是就是x平方根的近似值平方根的近似值4)取取z=(z+y)/2，回到回到2)重复重复从问题到程序（Python程序设计）裘宗燕，2017/-11-例：求例：求sin函数的值（通项计算和递推）函数的值（通项计算和递推）n已知已知考虑利用这个公式求考虑利用这个公式求sin(x)的近似值的近似值用项的绝对值小于用项的绝对值小于1e-6作为结束条件作为结束条件n一种朴素想法：一种朴素想法：定义函数定义函数term(x,n)计算级数的项，再用一个主循环计算级数的项，再用一个主循环whileTrue:t=term(x,n)iffabs(t)1e-6:结束循环结
15、束循环s+=tn+=1考虑考虑term的定义的定义考虑考虑sin的定义的定义也可以写成一个函数定也可以写成一个函数定义，其中用嵌套循环义，其中用嵌套循环从问题到程序（Python程序设计）裘宗燕，2017/-12-例：求例：求sin函数的值（通项计算和递推）函数的值（通项计算和递推）n仔细观察不难看到仔细观察不难看到t0=x。利用这个递推公式，可以节省大量计算。利用这个递推公式，可以节省大量计算可以定义项递推函数可以定义项递推函数nextTerm(x,n,t)，函数参数函数参数t表示表示tn-1。采用与前面类似的主循环结构采用与前面类似的主循环结构在代码文件里直接写出计算，没有另外定义函数在代
16、码文件里直接写出计算，没有另外定义函数n请分析这个函数的计算过程和进一步改进：请分析这个函数的计算过程和进一步改进：q大的参数值会带来很大的计算误差大的参数值会带来很大的计算误差自己做试验，并想想为什么自己做试验，并想想为什么q可以用可以用fmod(x,pi)把参数归化到最小把参数归化到最小0.0,2)从问题到程序（Python程序设计）裘宗燕，2017/-13-素数判断素数判断n素数是重要数学概念：大于素数是重要数学概念：大于1的自然数如果没有除的自然数如果没有除1及其自身外的及其自身外的其他因子（没有其他因子（没有真因子真因子），就是），就是素数素数（或称质数）（或称质数）n的因子就是能整
17、除的因子就是能整除n的正整数。的正整数。k整除整除n即是即是n除以除以k余数为余数为0。这一条件可以用表达式这一条件可以用表达式n%k=0描述描述n素数判断是一个问题，考虑如何通过计算解决素数判断是一个问题，考虑如何通过计算解决根据定义可得到一种朴素方法：对给定的根据定义可得到一种朴素方法：对给定的n，取从，取从2开始的整数，开始的整数，检查是否检查是否n的因子。发现的因子。发现n的真因子说明它不是素数。如果试验的真因子说明它不是素数。如果试验足够多，能确定足够多，能确定n无有真因子无有真因子,就可以断定就可以断定n是素数是素数n检查一些数可以通过循环实现，问题就变成：从哪儿开始检查？检查一些
18、数可以通过循环实现，问题就变成：从哪儿开始检查？下一个数怎么得到？何时结束？下一个数怎么得到？何时结束？n根据需要，可以考虑从根据需要，可以考虑从2开始，逐一检查更大的数开始，逐一检查更大的数检查到检查到n一定能做出判断，实际上检查到一定能做出判断，实际上检查到n的平方根就够了的平方根就够了从问题到程序（Python程序设计）裘宗燕，2017/-14-素数判断素数判断n综合上述考虑，可定义出下面判断函数：综合上述考虑，可定义出下面判断函数：defis_prime(n):ifn2:returnFalse#小于小于2的数都不是素数的数都不是素数k=2whilek*k=n:#至多做到至多做到m的平方
19、大于的平方大于nifn%k=0:returnFalsek+=1returnTruen这种函数完成判断，返回这种函数完成判断，返回bool类型的值，称为类型的值，称为谓词谓词n可以利用这个函数检查著名的歌德巴赫是否有反例可以利用这个函数检查著名的歌德巴赫是否有反例n存在许多判断素数的方法，近年一个重要进展是存在许多判断素数的方法，近年一个重要进展是AKS算法算法从问题到程序（Python程序设计）裘宗燕，2017/-15-迭代器、浮点数与循环迭代器、浮点数与循环n注意，注意，for语句只在语句开始时算出迭代器。例如：语句只在语句开始时算出迭代器。例如：foriinrange(0,10,2):pr
20、int(i)i-=1输出输出0、2、4、6、8。修改循环变量不会影响迭代取值。修改循环变量不会影响迭代取值生成迭代器的生成迭代器的range不能用浮点数作为参数不能用浮点数作为参数n浮点数计算有误差，不能用浮点数相等作为循环结束条件。例：浮点数计算有误差，不能用浮点数相等作为循环结束条件。例：x=0.0value=0.0whilex!=3.0:#循环不会结束，循环不会结束，0.03加加100次不能等于次不能等于3.0value+=sin(x*x+1)*cos(x)*0.03x+=0.03从问题到程序（Python程序设计）裘宗燕，2017/-16-浮点数与循环控制浮点数与循环控制n不要用浮点数
21、作为控制循环范围的数值依据不要用浮点数作为控制循环范围的数值依据x=0.0value=0.0whilex3.0:#循环能结束，但不能保证迭代循环能结束，但不能保证迭代100次次value+=sin(x*x+1)*cos(x)*0.03x+=0.03n应该用整数控制循环。一种解决方法：应该用整数控制循环。一种解决方法：value=0.0forninrange(100):x=n*0.03value+=sin(x*x+1)*cos(x)*0.03从问题到程序（Python程序设计）裘宗燕，2017/-17-输入循环输入循环n一类常见循环是输入循环一类常见循环是输入循环q在循环中，程序从外部获得一批数
22、据，用于计算在循环中，程序从外部获得一批数据，用于计算q得到足够数据后结束循环，继续下步工作得到足够数据后结束循环，继续下步工作n控制循环的进行和结束？两种典型情况控制循环的进行和结束？两种典型情况n情况情况1：编程时知道需要的数据项数或知道何时应该结束。由程：编程时知道需要的数据项数或知道何时应该结束。由程序内部控制，这是简单的序内部控制，这是简单的“循环输入循环输入”q例：程序需要读入一年中各月的降雨量（由用户提供的例：程序需要读入一年中各月的降雨量（由用户提供的12个个实数），计算出它们的平均值实数），计算出它们的平均值q例：需要读入一些数，求出前例：需要读入一些数，求出前10项非负数的
23、平均值项非负数的平均值n情况情况2：需要以某种方式处理用户输入需要以某种方式处理用户输入的的数据，但不知道用户将数据，但不知道用户将提供多少数据提供多少数据，用户自由决定在任何时刻结束输入。对这种情况，用户自由决定在任何时刻结束输入。对这种情况，就需要为用户提供通知结束的方法就需要为用户提供通知结束的方法从问题到程序（Python程序设计）裘宗燕，2017/-18-输入控制的循环输入控制的循环n需将输入分为正常输入和通知结束的特殊输入。处理模式：需将输入分为正常输入和通知结束的特殊输入。处理模式：whileTrue:data=input()ifdata是表示结束的特殊输入是表示结束的特殊输入:
24、break正常输入的处理正常输入的处理n编程时需要定义（约定）结束方式（这是与用户的协议）编程时需要定义（约定）结束方式（这是与用户的协议）q例如约定输入例如约定输入0表示要求结束表示要求结束这个约定也导致这个约定也导致“正式数据正式数据”里不能存在里不能存在0q约定某个不是数的输入作为结束约定某个不是数的输入作为结束n注意：这种约定决定了程序的写法和用法注意：这种约定决定了程序的写法和用法n程序示例程序示例从问题到程序（Python程序设计）裘宗燕，2017/-19-递归定义的函数递归定义的函数n有一种函数定义比较特殊，就是在函数体里调用自身有一种函数定义比较特殊，就是在函数体里调用自身q利
25、用自己的功能完成自己的一部分工作利用自己的功能完成自己的一部分工作q这种定义称为这种定义称为函数的递归定义函数的递归定义，定义的函数称为，定义的函数称为递归函数递归函数n考虑求阶乘的函数考虑求阶乘的函数阶乘：阶乘：这是一个分情况定义（数学定义这是一个分情况定义（数学定义），而且是，而且是“递归的定义递归的定义”，n的阶乘基于的阶乘基于n-1的阶乘定义的阶乘定义Python允许在函数体里调用被定义函数（允许以递归的方式定允许在函数体里调用被定义函数（允许以递归的方式定义函数），上面数学定义可直接翻译为义函数），上面数学定义可直接翻译为Python的函数定义的函数定义（看程序）（看程序）从问题到程
26、序（Python程序设计）裘宗燕，2017/-20-递归程序递归程序n递归定义的阶乘函数，看起来是一个简单分支型程序递归定义的阶乘函数，看起来是一个简单分支型程序q但它在一个分支里调用自己，每次递归调用执行函数里的一但它在一个分支里调用自己，每次递归调用执行函数里的一条执行路径（总体而言可能多次条执行路径（总体而言可能多次重复执行重复执行函数里的语句）函数里的语句）q运行中总的执行路径长度由递归调用这个函数的次数确定运行中总的执行路径长度由递归调用这个函数的次数确定（由调用的参数决定，如阶乘函数）（由调用的参数决定，如阶乘函数）n理论结果：理论结果：q由基本语句、顺序组合、条件语句、递归、函数
27、定义构成的由基本语句、顺序组合、条件语句、递归、函数定义构成的语言已经足够强大，足以描述所有可能的计算语言已经足够强大，足以描述所有可能的计算q基本语句、顺序组合和循环构成的语言也足够强大基本语句、顺序组合和循环构成的语言也足够强大n实际情况：实际情况：在实用的编程语言里，还需要引进另一些机制（控制机制和数在实用的编程语言里，还需要引进另一些机制（控制机制和数据机制），以方便实际的程序开发据机制），以方便实际的程序开发从问题到程序（Python程序设计）裘宗燕，2017/-21-求幂函数求幂函数n求求xn需要做多少次乘法？需要做多少次乘法？最简单想法是需要做最简单想法是需要做n次或次或n-1次
28、次n考虑考虑x8=(x2)4=(x2)2)2，只需做，只需做3次乘法，不需要做次乘法，不需要做7次次似乎有办法减少做乘法的次数似乎有办法减少做乘法的次数n一般的认识：一般的认识：q特殊情况：特殊情况：x0=1，x1=xq一般情况：一般情况：x2n=(x2)n，x2n+1=x2nxn利用这种看法，可以定义求幂函数（见代码文件）利用这种看法，可以定义求幂函数（见代码文件）q可以采用递归定义可以采用递归定义q也可以写采用循环的方式定义也可以写采用循环的方式定义从问题到程序（Python程序设计）裘宗燕，2017/-22-递归和循环递归和循环n前面讨论了循环，又提出递归定义的函数，其中没出现循环，但前
29、面讨论了循环，又提出递归定义的函数，其中没出现循环，但也能导致反复计算：通过递归调用多次执行同一个函数体也能导致反复计算：通过递归调用多次执行同一个函数体n问题：递归和循环能做的事情类似，两者可以相互替代吗？问题：递归和循环能做的事情类似，两者可以相互替代吗？n理论研究的结论：如果一个语言包含基本语句、顺序和条件语句，理论研究的结论：如果一个语言包含基本语句、顺序和条件语句，而且允许以递归方式定义函数，这个语言足够了，足以描述所有而且允许以递归方式定义函数，这个语言足够了，足以描述所有计算。另一方面，包含基本语句、顺序和循环的语言也足够了计算。另一方面，包含基本语句、顺序和循环的语言也足够了n
30、还有，针对任何循环都能定义一个递归函数，用这个函数的调用还有，针对任何循环都能定义一个递归函数，用这个函数的调用取代原循环得到同样效果。反过来：递归定义的函数可以改写为取代原循环得到同样效果。反过来：递归定义的函数可以改写为不用递归定义的函数，但有时做起来比较复杂不用递归定义的函数，但有时做起来比较复杂n上面结果说明递归和循环只需其一。但为方便程序开发，各种编上面结果说明递归和循环只需其一。但为方便程序开发，各种编程语言都有些冗余机制，程语言都有些冗余机制，Python既有循环结构也允许递归定义既有循环结构也允许递归定义实际编程中可以根据需要选用实际编程中可以根据需要选用n考虑将前面求幂函数改写为循环程序考虑将前面求幂函数改写为循环程序结束语结束语谢谢大家聆听！谢谢大家聆听！23
