程序设计思想与方法——第三章(2)综述.ppt

数据处理的流程控制 循环控制结构 Lu Chaojun, SJTU 2 Lu Chaojun, SJTU 2 2 为什么需要循环? • 有时需要重复做相同或相似的事情,程序中如何 表达? – 例如:在屏幕上显示1~5 print 1 print 2 print 3 print 4 print 5 – 繁琐且不具有扩展性(显示1~10000怎么办?) • 循环:用很少的语句表达重复执行的很多语句. Lu Chaojun, SJTU 3 Lu Chaojun, SJTU 3 3 for循环 • 语法 for in : • 语义:令取遍中的每个 值,并对变量所取的每个值执行一遍循环体. • 例如: for i in [1,2,3,4,5]: print i – 显示1~10000:用[1,2,...,10000]显然不合适, 可以用range() Lu Chaojun, SJTU 4 Lu Chaojun, SJTU 4 4 for循环的流程图 for语句中序列的作用 • 计数器:序列只是用来控制循环的次数. for i in range(10): print "烦" – 循环体不引用循环变量. • 数据:序列本身是循环体处理的数据. for i in range(10): print i*i – 循环体引用循环变量. – 两种遍历方式(见下一片) Lu Chaojun, SJTU 5 用for处理序列数据 • 直接遍历序列 >>> data = [Born on:,July,2,2005] >>> for d in data: print d, • 通过索引遍历序列 >>> data = [Born on:,July,2,2005] >>> for i in range(len(data)): print data[i], – 可以更灵活地处理序列数据,如 >>> for i in range(0,len(data),3): ... Lu Chaojun, SJTU 6 用for处理各种序列数据 • 字符串 >>> for c in "hello world": print c • 元组 >>> for i in (1,2,3): print i • 嵌套序列:如元组的列表 >>> for t in [(1,2),(3,4),(5,6)]: print t,t[0],t[1] Lu Chaojun, SJTU 7 Lu Chaojun, SJTU 8 Lu Chaojun, SJTU 8 while循环 • for主要用于确定次数的循环 • 不确定次数的循环:while while : Lu Chaojun, SJTU Lu Chaojun, SJTU 9 Lu Chaojun, SJTU 9 9 while循环的特点 • 循环前测试条件 – 若不满足,则循环体一次都不执行 • 循环体必须影响下一次条件测试! – 否则导致无穷循环 – 例如:for循环改写成while循环 i = 0 while i = 0: sum = sum + x x = input("Input a number (-1 to quit): ") print "The sum is", sum Lu Chaojun, SJTU 12 哨兵循环例(2) • 正常数据是任何实数,则可以空串作为哨兵: eg3_12.py sum = 0 x = raw_input("Input a number ( to quit): ") while x != "": sum = sum + eval(x) x = raw_input("Input a number ( to quit): ") print "The sum is", sum Lu Chaojun, SJTU 13 常用循环模式:后测试循环 • 输入验证问题: – 检查用户输入是否符合要求,不符合就要求用户重新输入,直至 符合为止. • 这是一种后测试循环: – 执行循环体后才测试条件 – 循环体至少执行一次 – 直至条件成立才退出循环 – 有些语言提供repeat…until语句 • Python可用while实现 – 只需确保首次进入while时条件成立 x = 1 while x < 0: ... Lu Chaojun, SJTU 14 常用循环模式:while计数器循环 • 用while实现计数器循环 计数器count置为0 while count < n: 处理代码 count ＝ count + 1 Lu Chaojun, SJTU 15 i = 0 while i0: print i i = i-1 循环非正常中断:break • 中止本轮循环,结束break所处循环语句. – 常与while True形式的无穷循环配合使用 • 例1:输入合法性检查 while True: x = input("请输入非负数:") if x >= 0: break • 例2:break也可以跳出for循环 for i in range(10): print "烦" if i > 4: break • 慎用break!尤其是一个循环体中有多个break. 循环非正常中断:continue • 中止本轮循环,控制转移到所处循环语句的开头 "继续"下一轮循环. • 例:对列表中的奇数求和 a = [23,28,39,44,50,67,99] sum = 0 for i in a: if a % 2 == 0: continue sum = sum + i print sum 常用循环模式:嵌套循环 • 一个循环的循环体中有另一个循环. • 如果序列的成员本身又是序列,就需要嵌套循环 来处理. – 数学中向量是一维序列,矩阵是二维序列 • 用嵌套循环遍历矩阵元素: a = [[11,12,13,14],[21,22,23,24],[31,32,33,34]] sum = 0 for i in a: for j in i: sum = sum + j print sum 嵌套循环例 • 打印乘法口诀表 – 关键是输出的排列 >>> for i in range(1,10): for j in range(1,i+1): print "%dx%d=%-2d" % (j,i,j*i), print 1x1=1 1x2=2 2x2=4 1x3=3 2x3=6 3x3=9 1x4=4 2x4=8 3x4=12 4x4=16 1x5=5 2x5=10 3x5=15 4x5=20 5x5=25 1x6=6 2x6=12 3x6=18 4x6=24 5x6=30 6x6=36 1x7=7 2x7=14 3x7=21 4x7=28 5x7=35 6x7=42 7x7=49 1x8=8 2x8=16 3x8=24 4x8=32 5x8=40 6x8=48 7x8=56 8x8=64 1x9=9 2x9=18 3x9=27 4x9=36 5x9=45 6x9=54 7x9=63 8x9=72 9x9=81 程序设计的发展 • 早期:手工作坊式 – 程序规模小,功能简单 – 要在有限内存中尽快完成计算 – 凭借程序员的个人编程技巧 • 后来:作为工程来开发 – 程序规模大,功能复杂 – 内存和速度不是问题,软件正确性和开发效率 变得突出 – 依靠系统化的开发方法和工具 程序开发周期 • 明确需求:问题是什么?用户要求是什么? • 制定程序规格:描述“做什么”. • 设计程序逻辑:描述“怎么做”. • 实现:用编程语言编写代码. • 测试与排错:用样本数据执行程序,测试结 果是否与预期吻合.有错则排错. • 维护:根据用户需求持续改进程序. 什么是好的程序 • 解决同一个问题,可以设计出多种处理过 程,即编制多种程序. • 即使各种程序都正确,仍然有好坏之分. • 除了正确性,好的程序应该是: – 效率高 – 易理解 – 易维护 – 可扩展 如何得到好的程序 • 手工作坊阶段靠的是个人编程技巧 • 如今则依靠程序设计方法和工具 – 方法:结构化方法,模块化方法,面向对象方法 等 – 工具:建模工具,集成开发环境,项目管理工具 等 结构化程序设计(1) • 确保程序具有良好的文本结构, 使程序易 理解,易验证,易维护. • 基本原则 – 只使用顺序,分支,循环三种基本控制结构 – goto有害 好在goto不是必须的 break和continue有点类似goto,因此要慎用 结构化程序设计(2) – 单入口单出口的程序块 多条语句可以组合成程序块,只要是单入口单出 口,仍然可当作一条语句. 编程案例:求最大值(1) • 先考虑求三个数x1,x2,x3的最大值的问题 • 策略1:每个数都与其他数比较大小 if x1 >= x2 and x1 >= x3: max = x1 elif x2 >= x1 and x2 >= x3: max = x2 else: max = x3 – 此算法中各分支彼此独立.但实际上一个分支的信息 对其他分支是有用的! – 此算法不适合较大n的情况 Lu Chaojun, SJTU 26 编程案例:求最大值(2) • 策略2:判定树 if x1 >= x2: if x1 >= x3: max = x1 else: max = x3 else: if x2 >= x3: max = x2 else: max = x3 Lu Chaojun, SJTU 27 好处:只需两次比较,效率高. 坏处:结构复杂, 复杂度随n爆炸 式增长. 编程案例:求最大值(3) • 策略3:顺序处理,记录当前最大值. max = x1 if x2 >= max: max = x2 if x3 >= max: max = x3 – 效率高 – 易读易理解 – 可扩展到n Lu Chaojun, SJTU 28 n = input("How many numbers? ") max = input("Input a number: ") for i in range(n-1): x = input("Input a number: ") if x > max: max = x print "max =", max 编程案例:求最大值(4) • 策略4:利用现成代码. – Python提供内建函数max(x1, x2, ... , xn) >>> x1,x2,x3 = input("enter 3 numbers:") >>> print "max =", max(x1,x2,x3) Lu Chaojun, SJTU 29 小结 • 给给定问题问题 ,有多种解决方法 – 不要只凭第一感匆忙编编程,要多考虑虑是否有 更好算法; – 首先要正确,其次要结结构清晰,高效,可扩扩展,漂 亮. • 问问自己会如何解决问题问题 • 追求一般性 • 借鉴鉴,重用现现成算法 Lu Chaojun, SJTU 30 Lu Chaojun, SJTU 31 Lu Chaojun, SJTU 31 End 。