PPT
【文档说明】程序设计思想与方法python讲义课件.ppt，共(248)页，920.523 KB，由小橙橙上传
转载请保留链接：https://www.ichengzhen.cn/view-44431.html
以下为本文档部分文字说明：
程序设计思想与方法6～13章潘理Email:panlisjtu.edu定义函数什么是函数为什么需要函数函数和参数带有返回值的函数函数和程序结构什么是函数?函数是一种程序构件，是构成大程序的小程序.函数定义：将一组完成某个特定功能的语句组合起来，取一个名字函数调用
：通过函数名执行者组语句函数的输入称为参数函数的输出称为返回值我们已经熟悉的函数:自己编的函数，如常用的main()Python内建函数，如abs()Python标准库函数，如math.sqrt()和string.split()对象的方法，如win
.close()和p.draw()3定义函数什么是函数为什么需要函数函数和参数带有返回值的函数函数和程序结构为什么需要函数?编程更容易把握复杂程序分解成较小部件代码可重用提高开发效率更易维护代码更简洁程序更易理解5编程实例:生日歌用函数减少重复代码defmain():pr
int“Happybirthdaytoyou!”print“Happybirthdaytoyou!”print“Happybirthday,dearFred.”print“Happybirthdaytoyou!”重复代码的坏处:1.费时
费力2.代码维护的一致性defhappy():print"happybirthdaytoyou!"defsingFred():happy()happy()print"Happybirthday,dearFred."happy()defmain():singFred()main(
)定义函数什么是函数为什么需要函数函数和参数带有返回值的函数函数和程序结构函数和参数如果要为tom唱一首数据生日歌，必须另外写一个函数singTomsingTom和singFred的区别在于第三个语句将Tom或Fred写成一个变量，这两个函数变成一个函数。这个变量称为
函数的参数，它是函数的输入。编程实例:生日歌(续)defhappy():print"happybirthdaytoyou"defsing(person):happy()happy()print“appybirthday,dear”,person,"."happy()prin
t"“defmain():sing("Fred")sing("Lucy")sing("Elmer")main()参数实例:计算利息计算利息程序中两处画柱子的代码是类似的循环外的初始柱子循环内的每年
的柱子解决方法：定义一个函数defdrawBar(win,year,height):bar=Rectangle(Point(year+1,1),Point(year+2,height))bar.setFill('green')bar.dr
aw(win)11完整的程序defmain():win=GraphWin("InvestmentGrowthChart",512,384)win.setCoords(0.0,0.0,14.0,6.0)Text(P
oint(0.5,1),'0.0K').draw(win)Text(Point(0.5,2),'2.5K').draw(win)Text(Point(0.5,3),'5.0K').draw(win)Text(Point(0.5,4),'7.5K').draw(win)Text(Point(0
.5,5),'10.0K').draw(win)principal=input("enterinitialprincipal:")apr=input("enterinterestrate:")drawBar(win,0,1+principal*0.0004)for
yearinrange(1,11):principal=principal*(1+apr)drawBar(win,year,1+principal*0.0004)raw_input("pressanykeytoquit:")win.close()main()形参和实参函数定义：defdrawB
ar(window,year,height)window,year,height成为形式参数，表示函数执行时的输入函数调用：drawBar(win,0,1+principal*0.0004)win,0,1+principal*0.0004称为实际参数，代表某次函数函数执行的输入参数
传递：将实际参数赋给形式参数函数调用过程函数定义def<函数名>(<形参列表>):<函数体>函数调用<函数名>(<实参列表>)调用程序暂停函数形参被赋值为实参(按位置对应)执行函数体控制返回调用点的下一条语句函数调用过程图解定义函数什么是函数为什么需要函数函数和参数
带有返回值的函数函数和程序结构带返回值的函数函数的返回值：函数执行的结果函数与调用者之间的沟通:通过参数从调用者输入值通过返回值向调用者输出值定义def<函数名>(形参):……return<表达式列表>Python遇见return语句时即退出函数,并计算表达式将结果返回
给调用者使用x=<函数名>(<实参>)编程实例：factorial计算n！该函数是一个有参数又有返回值的函数。参数是n，返回值是n！#coding=gbkdefp(n):x=1foriinrange(1,n+1):x=x*ireturn
xdefmain():n=input(“请输入一个整数：")printn,"!的值为：",p(n)main()定义函数什么是函数为什么需要函数函数和参数带有返回值的函数函数和程序结构函数与程序结构函数不只是为了减少重复代码.函数还使程序
更加模块化(modular).即使增加了代码量!编程实例：计算利率将主程序中并未重复出现的语句序列改写成了一个函数，原地方改成一个函数调用。代码量不减反增，但程序可读性大大增强!defcreateWin():win=GraphWi
n("InvestmentGrowthChart",512,384)win.setCoords(0.0,0.0,14.0,6.0)Text(Point(0.5,1),'0.0K').draw(win)Text(Point(0.5,2),'2.
5K').draw(win)Text(Point(0.5,3),'5.0K').draw(win)Text(Point(0.5,4),'7.5K').draw(win)Text(Point(0.5,5),'10.0K').draw(win)returnwindefm
ain():win=createWin()principal=input("enterinitialprincipal:")apr=input("enterinterestrate:")drawBar(win,0,1+principal*0.0004)foryearinrange(
1,11):principal=principal*(1+apr)drawBar(win,year,1+principal*0.0004)raw_input("pressanykeytoquit:")win.close()main()END分支程序设计前面出现的所有程序的执行过程都是从第一个语
句执行到最后一个语句，这称为顺序执行。例如求一元二次方程的解#equation1.pyimportmathdefmain():a,b,c=input("Enterthreecoefficients:")discRoot=math.sqrt(b*b-4*a*c)r1=(-b+discRoot)
/(2*a)r2=(-b-discRoot)/(2*a)print"Thesolutionsare:",r1,r2main()当b*b–4*a*c<0时，程序执行出错！！！分支程序设计单分支多分支异常处理单分支程序设计分支语句的基本格式及应用条件
执行303030单分支决策语法if<condition>:<body><condition>:布尔表达式<body>:语句序列.语义：计算<condition>的真假.若为真,则执行<body>，并把控制转向下一条语句；若为假
，则直接把控制转向下一条语句.3131条件表达式简单条件:关系表达式，比较两个表达式<expr1><rel-op><expr2>关系运算:<，<=，==，>=，>，!=数值比较字符串比较:按字典序.复杂条件
：布尔表达式.布尔运算符：and,or,not布尔表达式:<expr><relop><expr>结果为true/false3232and的定义and表示“并且”:PQPandQFFFFTFTFFTTT3333or的定义or表示“或者”:日常用语中的“
或”往往具有互斥的涵义,即二选一.与此处的or有不同!PQPorQFFFFTTTFTTTT3434not的定义not表示“否定”:PnotPTFFT布尔运算符的优先级not最高,and次之,or最低思考:aornotbandc何意
?最好使用括号!35例:判断两点是否位置相同ifp1.getX()==p2.getX()andp1.getY()==p2.getY():#pointsarethesameelse:#pointsaredifferent36解一元二次方程imp
ortmathdefmain():a,b,c=input("inputa,b,c:")d=b*b-4*a*cif(d>0):x1=(-b+math.sqrt(d))/2/ax2=(-b-math.sqrt(d))/2/aprint"x1=",x1,"x2=",
x2main()缺点在b*b–4*a*c<0时，程序没有任何反应改进：在b*b–4*a*c<0时，输出一个出错信息两分支决策语法if<条件>:<语句序列1>else:<语句序列2>语义若<条件>为真,执行<语句序列1
>，控制转向下一条语句；否则执行<语句序列2>，控制转向下一条语句.39解一元二次方程importmathdefmain():a,b,c=input("inputa,b,c:")d=b*b-4*a*cif(d<0):print"noroot"else:x1=(-b+math.sqrt(d)
)/2/ax2=(-b-math.sqrt(d))/2/aprint"x1=",x1,"x2=",x2main()缺陷当a等0时，程序会异常终止。因为遇到了除数为0的问题在解一元二次方程时增加一个检测条件，检验方程是不是一元二次方程#coding=gbkimpor
tmathdefmain():a,b,c=input("inputa,b,c:")if(abs(a)<0.000001):print"不是一元二次方程"else:d=b*b-4*a*cif(d<0):print"noroot
"else:x1=(-b+math.sqrt(d))/2/ax2=(-b-math.sqrt(d))/2/aprint"x1=",x1,"x2=",x2main()单分支程序设计分支语句的基本格式及应用
条件执行444444有条件执行程序回顾:Python模块分为程序/脚本:可直接执行模块最后一行是main(),即启动程序的语句执行方式–直接执行•Windows下双击模块图标•DOS命令行下:python<myfile>.py–在会话或其他程
序中import并执行库:不能直接执行模块中没有main()一行被其他程序import但不执行454545有条件执行程序(续)混合型模块:既能作为独立程序直接执行,又能作为库被其他程序import而不执行.#myfile.pydefmain():…defother
():…if__name__==„__main__‟:i()•import一个模块时,Python将该模块中的一个特殊变量__name__设置为该模块的名字;•直接执行模块时,__name__被设置为’__main__‟分支程序设计单分支多
分支异常处理多分支决策语法if<条件1>:<语句序列1>elif<条件2>:<语句序列2>...elif<条件n><语句序列n>else<缺省语句序列>语义：找到第一个为真的条件并执行对应语句序列，控制转向下一条语句；若无
，则执行else下的语句序列，控制转向下一条语句。47完善一元二次方程考虑等根的情况importmathdefmain():a,b,c=input("inputa,b,c:")if(abs(a)<0.000001):print"inputil
legal"else:d=b*b-4*a*cif(d<0):print"noroot"elif(abs(d)<0.0000001):x=-b/2/aprint"x=",xelse:x1=(-b+math.sqrt(d))/2/ax2=(-b-math.sqrt(d))/2/aprint"x1="
,x1,"x2=",x2main()49分支程序设计单分支多分支异常处理异常处理为保证程序的正确性，当程序中充斥着许多错误检测代码，使解决问题的算法反而不明显了.例如求一元二次方程的解，就是利用标准的公式。但为了用
此公式，必须判断a是否为0，Δ是否小于0。51解决办法异常处理机制：把错误集中在一起处理，以免影响算法的主线条。Python提供try...except...可使程序不因运行错误而崩溃，尽量让用户不受意外结果的困扰。例外处理语句
语法try:<body>except<ErrorType1>:<handler1>except<ErrorType2>:<handler2>...except:...语义：执行<body>。若无错，控制转下一语句；若有错，查找匹配该错误
的except子句，找到则执行相应的处理程序，找不到则程序崩溃，系统报错。53完善一元二次方程问题用异常处理语句来捕获math.sqrt的溢出错误try:...exceptValueError:...错误类型:从系统报错信息中可得.如ValueError，TypeE
rror，NameError等54importmathdefmain():a,b,c=input("inputa,b,c:")if(abs(a)<0.000001):print"inputillegal"else:d=b*b-4*a*ctr
y:x1=(-b+math.sqrt(d))/2/ax2=(-b-math.sqrt(d))/2/aprint"x1=",x1,"x2=",x2exceptValueError:print"noroot"main()改进版2将a等于0的判断也作为异常，
是程序更加简洁importmathdefmain():a,b,c=input("inputa,b,c:")d=b*b-4*a*ctry:x1=(-b+math.sqrt(d))/2/ax2=(-b-mat
h.sqrt(d))/2/aprint"x1=",x1,"x2=",x2exceptValueError:print"noroot"exceptZeroDivisionError:print"inputer
ror"main()END循环控制结构For循环回顾While循环嵌套循环后测试循环和Break语句循环的中途退出606060for循环:回顾语法for<var>in<sequence>:<body>语义：循环标志变量var取遍序列sequence中的每个值；对var所取
的每个值执行一遍循环体body。编程实例:求平均值需求:输入若干个数,求平均值.显然可用熟悉的累积器算法模式算法:输入数值个数n初始化累积变量sum=0循环n次输入数值x累加到sum输出平均值sum/n翻译到Python:avg.py61defmain():n=input(
"inputanum:")sum=0foriinrange(n):sum=sum+input("")print"average=",sum/nmain()凯撒密码（Caesarcipher）a-D、b-E、c-
F、d-G、e-H……s-V……、z-Ceg.明文：accesscontrol可变为：DFFHVVFRQWURO#codinggbkdefmain():str_before=raw_input("请输入明文：")str_after
=""forchinstr_before:iford(ch)<ord('x'):str_after=str_after+chr(ord(ch)+3)else:str_after=str_after+chr(ord(ch)-23)printstr_afte
rmain()循环控制结构For循环回顾While循环嵌套循环后测试循环和Break语句循环的中途退出6666while循环avg.py的缺点：需要用户输入n，不适合事先不知道n的场合解决方法：每次询问是否还有数据要输入
不确定的条件循环:while语法while<condition>:<body>语义:只要条件成立就反复执行循环体;当条件不成立则执行下一条语句.676767while循环的特点循环前测试条件若不满足,则循环体一次都不执行循环体影响下一次条件测试否则
导致无穷循环例如：for循环改写成while循环i=0whilei<10:printii=i+1问题：若忘了最后一条语句会怎样?条件循环体yesno常见循环模式:交互循环用户根据需要来循环执行程序某一部分例如:avg1.py不输入n，由程序自己数输入的值的个数设置一个
是否继续循环的标志初始化sum=0，count=0，moredata=yeswhilemoredata=yes:输入数据x累积sum=sum+x累积count=count+1询问用户moredata?输出平
均值sum/count68#avg.pydefmain():sum=0.0num=0moreData="yes"whilemoreData=="yes":sum=sum+input("inputdata:")num=num+1moreData=r
aw_input("moredata(yesorno)?")print"average=",sum/nummain()缺点avg1.py不断要用户输入moredata,很烦人.改进:设置一个特殊数据值(称为哨兵)作为终止循环的信号.对哨兵唯一的要求就是能与普通数据区
分模式:输入第一个数据while该数据不是哨兵:处理该数据输入下一个数据编程实例:avg2.py(负数哨兵)70Avg2.pydefmain():sum=0.0num=0data=input("inputdata:")whiled
ata>=0:sum=sum+datanum=num+1data=input("inputdata:")print"average=",sum/nummain()常见循环模式:文件循环avg~avg2都是交互式输入数据的不便处理大数据量.
一个输入错误即导致需要重新运行程序.改进:建立一个数据文件.数据处理应用中广泛使用模式:打开数据文件fforlineinf:处理每个数据编程实例:avg3.py72Avg3.py:统计整个文件d
efmain():sum=0.0num=0infile=open("data.txt",'r')forlineininfile.readlines():sum=sum+eval(line)num=num+1print"average=",s
um/nummain()缺点在处理前，将整个文件读入内存，导致运行速度减慢，甚至无法运行。解决方法：分批读入，每次读入一行。文件结束时，readline返回一个空串。Avg4.pydefmain():sum=0.0num=0infile=open("data.
txt",'r')line=infile.readline()whileline!="":sum=sum+eval(line)num=num+1line=infile.readline()print"average=",sum/numm
ain()循环控制结构For循环回顾While循环嵌套循环后测试循环和Break语句循环的中途退出常见循环模式:嵌套循环嵌套循环:一个循环语句的循环体内有另一个循环语句.用途:遍历一维空间的元素只需一个循环变量,遍
历二维空间的元素需要两个循环变量,……,遍历n维空间的元素需要n个循环变量.例如:假设数据文件包含多段数据，段与段之间用空行分开，需要分段统计。77Avg5.pydefmain():sum=0.0num=0infile=open("data1
.txt",'r')line=infile.readline()whileline!="":whileline!="\n"andline!="":sum=sum+eval(line)num=num+1line=infile.readline()print"average=",sum/num
sum=0.0num=0line=infile.readline()main()循环控制结构For循环回顾While循环嵌套循环后测试循环和Break语句循环的中途退出其他循环结构:后测试循环问题:输入验证检查用户输入是否符合要求,不符合就要求用户重新输入,直至符合为止
.这是一种后测试循环:执行循环体后才测试条件循环体至少执行一次直至条件成立才退出循环有些语言提供repeat…until语句80后测试循环Python没有提供特殊的语句可以用while循环实现，只要保证第一次进入循环时条件为真例如：要求用户输入一个大于0的数，如果不满足要求，则
重新输入。可用语句：Data=-1Whiledata<=0:data=input(“)break语句语法:break语义:退出break所处循环(通常是无穷循环).应用例:实现后测试循环while1:x=input("Enteranonnegativenumber:")if
x>=0:break比用一个非法值(如前面的1)来强制while循环一次的做法好.慎用break，尤其是一个循环体用多个break出口.循环控制结构For循环回顾While循环嵌套循环后测试循环和Break语句循环的中途退出半路循
环(LoopandaHalf)循环出口在循环体中间.例如while1:x=input("Enteranonnegativenumber:")ifx>=0:breakprint"negative!"用半路循环实现哨兵循环:while1:读取下一数据xifx是哨兵:br
eak处理xEND模拟与设计Racquetball问题的思考878787模拟计算机有远远高于人类的计算能力，能解决人类所不能解决的一些问题。如天气预报，设计飞机等模拟：用计算机为实际问题建模,从而提供非如此不能获得的信息.我们已经掌握的工具足以让我们编程解决有意思的问题.一个模拟问
题:Racquetball问题:为什么球技只比对手略差,却输掉绝大多数的比赛?一种可能是心理上的:你头脑中自以为比对手只是略差,实际情况是你差很多.另一种可能:这是壁球运动本身的特性,能力上的细微差距却导致压倒性的
胜负.解决方法：用计算机模拟壁球，通过模拟不同水平球员之间的数千场比赛来看看这是必然的还是偶然的，888989美式壁球基本知识球,球拍,场地一人发球开始比赛然后两人交替击球(称为一个rally)当一人未能击出合法球,则输掉本rally;发球方输则交换发球权;发球方赢则得1分
.先得15分者赢1局.程序规格球技水平:用球员作为发球方的获胜概率来模拟.程序规格输入:两个球员的水平,模拟比赛局数.输出:两球员各自的获胜局数及比例.90关键技术：随机数模拟的是不确定性事件：rally的输赢是随机的
.这类模拟也称为MonteCarlo算法如何用确定性的计算机模拟非确定性?用函数生成随机数(实际上是伪随机数).从种子值开始,计算出一个“随机”数;如果还需要,就用上一个随机数反馈给生成函数,生成下一个随机数.Pyth
on库random提供了一些伪随机数生成函数:从加载库的日期时间导出种子值.randrange():生成指定范围(类似range)内的一个整数random():生成[0,1)间的一个浮点数91用random模拟输赢设发球人获胜概率是prob程
序中显然需要这样的代码:if发球者胜了本回合:score=score+1并且要使该条件为真的情况占prob用random函数模拟:ifrandom()<prob:score=score+192自顶向下的分解对复杂问题常采用自顶向下分解:将对一般
问题的解决方案用若干个较小问题来表达.再对较小问题用同样的方法分解.直至小问题很容易求解.将所有小问题的解合并,就得到大问题的解.93自顶向下的分解将计算机程序分解成不同部分，各部分功能重叠越少越好.好处:允许多人独立开发系统的不同部分便于重用确保系统可维护性
易于增加新功能使系统易理解94结构图模拟壁球问题的程序被分成了四个部分:将每个部分定义为一个函数为每个函数定义接口，即函数名,参数,返回值的信息高层设计时只须关心函数的接口,而非函数的实现.用结构图(或称模块层次图)表示:95顶层设计基本算法:介绍程序功能取得输入:prob
A,probB,n利用probA和probB模拟n局比赛输出结果报告基本程序defmain():printIntro()probA,probB,n=getInputs()winsA,winsB=simNGames(n,probA,probB)pri
ntSummary(winsA,winsB)96抽象在设计的每一层，接口指明了需要下一层的哪些细节；其他可暂时忽略.抽象：确定某事物的重要特性并忽略其他细节的过程.抽象是基本的设计工具.自顶向下设计的整个过程可视为发现有用的抽象的系统化方法.第二层设计两个简
单函数defprintIntro():print"Thisprogramsimulatesagameofracquetball"print‟betweentwoplayerscalled"A"and"B".‟print"Theabilitieso
feachplayerisindicatedbya"print"probability(anumberbetween0and1)that"print"theplayerwinsthepointwhenserving.P
layerA"print"alwayshasthefirstserve.“defgetInputs():#RETURNSthreesimulationparametersprobA,probBandna=input("Whatisthepr
ob.playerAwinsaserve?")b=input("Whatistheprob.playerBwinsaserve?")n=input("Howmanygamestosimulate?")returna,b,n第二层设计(续)设计simNGame
s()winsA和winsB初始化为0循环n次模拟一局ifplayerA胜:winsA加1else:winsB加1defsimNGames(n,probA,probB):winsA=winsB=0foriinrange(n):scoreA,scoreB=simOneGame(probA,p
robB)ifscoreA>scoreB:winsA=winsA+1else:winsB=winsB+1returnwinsA,winsB第三层设计simOneGame:整个模拟程序的关键.是个不确定循环：不断进行回合较量，直至一局结束需要两个累积器：记分需要一个二值累积
器：记录发球方得分初始化为0发球方置为"A"当本局未结束就循环:模拟一次发球修改比赛状态返回比分第三层设计(续)defsimOneGame(probA,probB):scoreA=0scoreB=0serving="
A"whilenotgameOver(scoreA,scoreB):ifserving=="A":ifrandom()<probA:scoreA=scoreA+1else:serving="B"else:ifrandom()<probB:sco
reB=scoreB+1else:serving="A"returnscoreA,scoreB第三层设计(续)函数gameOverdefgameOver(a,b):#aandbrepresentscoresforara
cquetballgame#RETURNStrueifthegameisover,falseotherwise.returna==15orb==15函数printSummarydefprintSummary(winsA,winsB):#Pri
ntsasummaryofwinsforeachplayer.n=winsA+winsBprint"\nGamessimulated:",nprint"WinsforA:%d(%0.1f%%)"%(winsA,
float(winsA)/n*100)print"WinsforB:%d(%0.1f%%)"%(winsB,float(winsB)/n*100)完整程序:rball.py运行之,看看技术的小差距是否导
致大胜负差?试一试:修改成模拟多局制比赛.设计过程小结自顶向下,逐步求精将算法表达为一系列较小问题为每个小问题设计一个(函数)接口用各小问题的接口细化算法对各小问题重复此过程过程化的程序设计自顶向下的设计自底向上的实现从结构图的底层开始实现,逐级向上.
每完成一个模块，进行单元测试.其他设计技术原型技术(prototyping):从程序的一个简单版本开始,逐步增加功能,直至完全满足程序规格.初始的简单版本称为原型(prototype).原型技术导致螺旋式开发过程:原
型的设计,实现,测试新功能的设计,实现,测试……适合情况:对程序功能不熟悉,难以按自顶向下设计方法给出完整设计.例:壁球模拟程序的原型simOneGame()固定水平五五开固定比赛30个rallyfromra
ndomimportrandomdefsimOneGame():scoreA=0scoreB=0serving="A"foriinrange(30):ifserving=="A":ifrandom()<.5:scoreA=scoreA+1else:serving="B"else
:ifrandom()<.5:scoreB=scoreB+1else:serving="A"printscoreA,scoreB例:对原型的扩展增加两个参数:选手的技术水平改成完成一局比赛(一方先得15分)
完成多局比赛,统计各人获胜局数增加交互式输入,格式化输出设计的艺术螺旋式开发与自顶向下设计是互补的方法.如:原型可使用自顶向下设计好的软件设计者会使用多种设计技术.通过实践学习软件设计.END类的定义对象回顾类的定义封装编程实例111111111对象回顾对象的构成
:一组相关信息：属性处理该信息的一组方法：函数类决定了对象具有哪些信息和方法对象是类的实例通过类的构造函数创建新对象定义自己的类:即以OO方法来组织自己程序要处理的数据.112112编程实例:炮弹模拟程序规格输入:发射角,初速度,初始高度输出:射程注:不
用微积分,只用一些基本知识来算法化解决.算法输入模拟参数:角度,速度,高度,计算位置变化的时间间隔计算炮弹初始位置xpos，ypos计算炮弹初始水平和垂直速度xve，yvel当炮弹还在飞行,循环:更新一个时间间隔之后的xpos,ypos,yvel输出xpos编程实例:炮弹模
拟(续)defmain():angle=input("...(indegrees)")vel=input("...(inmeters/sec")h0=input("...(inmeters)")time=input("...(inseconds)")xpos
,ypos=0,h0theta=angel*math.pi/180.0xvel=vel*math.cos(theta)yvel=vel*math.sin(theta)whileypos>=0.0:更新print"Distance
:%0.1fmeters."%(xpos)114114114编程实例:炮弹模拟(续)算法核心部分:更新各值xpos=xpos+xvel*timeyvel_new=yvel9.8*timeypos=ypos+time*(yvel+yvel_new)/2y
vel=yvel_new抽象函数，得到的main函数为defmain():angle,vel,h0,time=getInput()xpos,ypos=0,h0xvel,yvel=getXYComponents(vel,angle)whileypos>=
0.0:xpos,ypos,yvel=updatePos(time,xposyposxvelyvel)函数updateData()的弊端过多参数:5个参数，3个返回值.函数参量过多通常意味着有更好的组织方式OO设计：设计
一个抛物体类Projectile，让它自己记住当前的位置、速度、以及y方向速度的变化，使main函数不用操心这些细节defmain():angle,vel,h0,time=getInput()cball=Porjectile(angle,vel,h0)whilecbal
l.getY()>=0.0:cball.update(time)类的定义对象回顾类的定义封装编程实例类的定义语法class<类名>:<方法定义>方法定义:同函数定义.方法是依附于类的函数.一般函数则是独立的.方法的第一个参量是专用的:指向方法的作用对象.传统上习惯用self这个名字.回忆
:对象是数据和操作的结合.上面的类定义中,方法对应于操作.但数据呢?117118118118例:类定义多面骰子#msdie.pyfromrandomimportrandrangeclassMSDie:def__init__(self,s
):self.sides=sself.value=1defroll(self):self.value=randrange(1,self.sides+1)defgetValue(self):returnself.value实例变量Python的类
并不明显定义实例变量,而是在方法中直接使用.主要是在__init__方法中(见后)用self.<实例变量>的方式给出如MSDie中的sides和value每个类的实例(对象)具有自己的实例变量副本,用来存储该对象自己的数据.对
实例变量的访问:<对象>.<实例变量>实例变量与函数局部变量不同!119方法调用方法调用:同函数调用,但需指明作用对象.因此不需要再为形参self提供实参了.例如:主程序main()中执行die1.setValue(8)构造函数对象构造函数(constructor)：构造一个新的对象并
赋初值__init__用法:(1)在类外部用类名生成新实例:die1=MSDie(6)(2)Python创建一个MSDie新实例,并对该实例调用__init__(),从而初始化其实例变量:die1.sides=6die1.value
=1121编程实例:Porjectile类构造器炮弹的实例变量:xpos,ypos,xvel,yvel构造器需要三个初值来为实例变量初始化:cball=Projectile(angle,vel,h0)因此得到:def_
_init__(self,a,v,h):self.xpos=0self.ypos=htheta=math.pi*a/180self.xvel=v*math.cos(theta)self.yvel=v*math.sin(thet
a)122编程实例:Porjectile类(续)读取实例变量的方法defgetX(self):returnself.xposdefgetY(self):returnself.ypos更新实例变量的方法:defupdate(self,time):self.xpos=self.xpos+sel
f.xvel*timeyvelnew=self.yvel–9.8*timeyvelavg=(self.yvel+yvelnew)/2self.ypos=self.ypos+yvelavg*timeself.yvel=yvelnewOO版
炮弹模拟程序:cball3.py类的定义对象回顾类的定义封装编程实例封装封装(encapsulation):如果确认某类对象对解决问题有用,即可当作此类对象已存在,从而直接使用对象功能;至于对象的实现细节则封装在相应
类定义中.这是抽象(忽略实现细节),也是SoC.Python的封装只是一种程序设计思想和方法,并非语言本身提供的能力.在程序的任何地方可以随意访问实例变量.严格意义的OO:内部细节在类外部是不可见的,只能通
过方法(接口)访问.125126126126类模块文件类定义一般作为单独的模块，以提供给其他所有程序使用.类模块文件类似于函数库很多OO语言都提供类库类模块的格式如前所述，模块的第一行一般是一行注释注释会被Py
thon编译器所忽略有一类特殊的注释，编译器会保存下来，它是用”””…………”””括起来特殊注释的使用模块、类和函数定义的第一行可以是一个特殊的注释字符串，说明所定义的模块、类和函数的性质、作用等，形如#projectile.py"""Thismodulepro
vides..."""classProjectile:"""Thisclass..."""defgetX(self)"Thisfunction..."docstring被系统保存在模块/类/函数的属性__doc__中，可访问类的定义对象回顾类的定义封装编程实例编程实例:掷骰子图形化模拟掷
两个骰子,程序显示投掷结果.提供两个按钮:一个用来投掷,一个用来退出程序.显然需要两个GUI部件:按钮和骰子.定制GUI部件:按钮按钮:图形窗口中的矩形区域，点击可以影响应用程序的行为.应该支持的方法:构造器activate：按钮处于激活状态deactivate：按钮处于失
效状态clicked：按钮被点击getLabel：获得按钮标签应该存储的实例变量可通过实现上述方法来明确需要哪些变量按钮方法实现：activate按钮激活时:边框由细变粗填充色由灰变黑defa
ctivate(self):self.label.setFill(black)self.rect.setWidth(2)self.active=1可见需要实例变量:Text对象label,Rectangle对象rect,布尔变量activedeactivat
e()的实现类似132按钮方法实现例:clicked按钮被点击:getMouse()返回的坐标位于按钮矩形范围内defclicked(self,p):returnself.activeand\self.xmin<=p.getX()<=self.xmaxand\self.ymin<=
p.getY()<=self.ymax可见需要实例变量:xmin,xmax,ymin,ymax133按钮类:button.py#button.pyfromgraphicsimport*classButton:def__ini
t__(self,win,center,width,height,label):self.xmin=center.getX()-width/2.0self.xmax=center.getX()+width/2.0self.ymin=cente
r.getY()-height/2.0self.ymax=center.getY()+height/2.0self.rect=Rectangle(Point(self.xmin,self.ymin),Point(self.xmax,self.ymax))self
.rect.setFill('lightgray')self.rect.draw(win)self.label=Text(center,label)self.label.draw(win)self.deactivate()def
clicked(self,p):returnself.activeandself.xmin<=p.getX()<=self.xmaxandself.ymin<=p.getY()<=self.ymaxdefgetLabel(se
lf):returnself.label.getText()defactivate(self):self.label.setFill('black')self.rect.setWidth(2)self.active=1defdeactivate(self):self.label.setFil
l('darkgrey')self.rect.setWidth(1)self.active=0定制GUI部件:骰子应该支持的方法:构造器setValue:设置骰子投出的值预置所有可能的圆点，根据值来点亮相应的圆点136骰子类:DieView.py#dieview.p
yfromgraphicsimport*fromgraphicsimport*classDieView:"""DieViewisawidgetthatdisplaysagraphicalrepresentationofastandardsix-
sideddie."""137构造函数构造一个骰子对象在窗口上画一个矩形，并确定骰子上6个点的位置置初值为1def__init__(self,win,center,size):#firstdefinesomestandardvaluesself.win=win#savethisfordra
wingpipslaterself.background="white"#colorofdiefaceself.foreground="black"#colorofthepipsself.psize=0.1*s
ize#radiusofeachpiphsize=size/2.0#halfthesizeofthedieoffset=0.6*hsize#distancefromcentertoouterpips#cre
ateasquareforthefacecx,cy=center.getX(),center.getY()p1=Point(cx-hsize,cy-hsize)p2=Point(cx+hsize,cy+hsize)rect=Rectangle
(p1,p2)rect.draw(win)rect.setFill(self.background)#Create7circlesforstandardpiplocationsself.pip1=self.__makePip(cx-offset,cy-offset)self.pip2=s
elf.__makePip(cx-offset,cy)self.pip3=self.__makePip(cx-offset,cy+offset)self.pip4=self.__makePip(cx,cy)self.pip5=self.__makePip(cx+o
ffset,cy-offset)self.pip6=self.__makePip(cx+offset,cy)self.pip7=self.__makePip(cx+offset,cy+offset)#Drawaninitialvaluese
lf.setValue(1)__makePip在给定位置生成骰子上的一点，置成背景颜色def__makePip(self,x,y):"Internalhelpermethodtodrawapipat(x,y)"p
ip=Circle(Point(x,y),self.psize)pip.setFill(self.background)pip.setOutline(self.background)pip.draw(s
elf.win)returnpipsetValue设置骰子的值defsetValue(self,value):"Setthisdietodisplayvalue."#将所有点都置成背景颜色self.pip1.setFill(self.ba
ckground)self.pip2.setFill(self.background)self.pip3.setFill(self.background)self.pip4.setFill(self.background)self.pip5.setFill(self.backg
round)self.pip6.setFill(self.background)self.pip7.setFill(self.background)#显示相应的点ifvalue==1:self.pip4.setFill(self.foreground)elif
value==2:self.pip1.setFill(self.foreground)self.pip7.setFill(self.foreground)elifvalue==3:self.pip1.setFill(self.foreground)self.pip7.setFill(self
.foreground)self.pip4.setFill(self.foreground)elifvalue==4:self.pip1.setFill(self.foreground)self.pip3.setFill(se
lf.foreground)self.pip5.setFill(self.foreground)self.pip7.setFill(self.foreground)elifvalue==5:self.pip1.setFill(self.foregroun
d)self.pip3.setFill(self.foreground)self.pip4.setFill(self.foreground)self.pip5.setFill(self.foreground)self.pip7.setFill(self.foreground)else
:self.pip1.setFill(self.foreground)self.pip2.setFill(self.foreground)self.pip3.setFill(self.foreground)self.pip5.setFill(self.foreground)
self.pip6.setFill(self.foreground)self.pip7.setFill(self.foreground)主程序#roller.py#Graphicsprogramtorollapairofdice.#Usescustomwidgets#Buttonan
dDieView.fromrandomimportrandrangefromgraphicsimport*frombuttonimportButtonfromdieviewimportDieView145defmain():#创建
一个图形窗口win=GraphWin("DiceRoller")win.setCoords(0,0,10,10)win.setBackground("green2")#画两个骰子和两个按钮die1=DieView(win,Point(3,7),2)die2=
DieView(win,Point(7,7),2)rollButton=Button(win,Point(5,4.5),6,1,"RollDice")rollButton.activate()quitButton=Button(win,Point(5,1),2,1,"Quit")#不断按RollD
ice按钮掷骰子，直到点击了quit按钮pt=win.getMouse()whilenotquitButton.clicked(pt):ifrollButton.clicked(pt):value1=randrange(1,7)die1.s
etValue(value1)value2=randrange(1,7)die2.setValue(value2)quitButton.activate()pt=win.getMouse()#closeupsh
opwin.close()END数据集合数据集合列表与类一起使用字典数据集合很多程序都需要处理大批量的数据.文档中的大量单词学校学生，企业客户实验得到的数据，......回顾：输入一批数据求平均值的程序.无需保存数据：用累积变量sum和count即可.但：求中位数和标准差需
要保存全部数据。如何保存？151151151列表有没有一个对象能包含很多数据?Yes!如range(10)=[0,1,2,3,4,5,6,7,8,9]又如string.split(“Thisisi
t.”)=[„This‟,‟is‟,‟it‟]用[]括起来的一组值称为列表（List）列表：是Python提供的一种数据集合.是数据的有序序列整体用一个名字表示:如seq各成员通过下标(索引)引用
:如seq[3]列表与字符串回顾：Python字符串是序列,可通过索引引用.列表与字符串的区别:列表的成员可以是任何数据类型,而字符串中只能是字符;列表的成员可修改,而字符串不能修改.举例表的操作>>>myList=[34,26,15,10]>>>myList[2]15
>>>myList[2]=0>>>myList[34,26,0,10]字符串的操作>>>myString="HelloWorld">>>myString[2]‟l‟>>>myString[2]=‟z‟Traceback(innermostlas
t):File"<stdin>",line1,in?TypeError:objectdoesn‟tsupportitemassignment列表与数组很多编程语言提供数组(array)类型.P
ython列表与数组的区别:列表是动态的,而数组是定长的列表元素可以是混合类型的，而数组元素是同类型的例如，silly=[1,“spam”,4,“U”]是合法的列表，但不是合法的数组。《程序设计思想与方法》hyw
eng@sjtu.edu.cn-155专用于列表的操作方法含义list.append(x)将x添加到表尾list.sort()将列表排序，比较函数可以作为参数list.reverse()倒置表元素list.index(x)返回x在表中的下标li
st.count(x)返回x在表中的出现次数list.remove(x)删除x在表中的第一次出现list.pop(i)删除表中的第i个元素，并返回该元素值xinlist检查x是否在表中，返回一个布尔值可应用于列表的字符串操作合并:<seq>+<seq>重复:<seq>*<int_expr>
索引:<seq>[<index_expr>]分段:<seq>[<start>:<end>]长度:len(<seq>)迭代:for<var>in<seq>:...del<seq>[<start>:<end>]编程实例计算输入的一组数据的均
值和方差均值的定义为方差的定义为niinxx1/nxxnii12)(解题思想循环读入每一个统计数据，存入一个列表计算平均值计算方差显示结果数据读入设计一个函数getNumber完成此功能。getNumber函数重复读入一个字
符串，将字符串转换为数字，添加到列表nums中，知道读入了一个空字符串，返回numsdefgetNumbers():nums=[]#startwithanemptylist#sentinellooptogetnumbersxStr=raw_input("Enteranum
ber(<Enter>toquit)>>")whilexStr!="":x=eval(xStr)nums.append(x)#addthisvaluetothelistxStr=raw_input("Enteranumber(<Enter>toquit)>>")returnnums计算平均值
设计函数mean完成此功能函数mean将nums中的每个数据加入到一个变量sum，返回sum/ndefmean(nums):sum=0.0fornuminnums:sum=sum+numreturnsum/len(nums)计算方差设计函数Dev完成此功能该函数将nums中
的每个数据与均值相减后的平方加起来存入变量sum返回sum/ndefDev(nums,xbar):sum=0.0fornuminnums:dev=xbar-numsum=sum+dev*devreturnsum/len(nums)Main函数defmain():print„程序计
算一组数据的均值和方差'data=getNumbers()xbar=mean(data)std=Dev(data,xbar)print'\n均值是：',xbarprint'\n方差是：',stdif__name__=='__main__':main()数
据集合数据集合列表与类一起使用字典列表与类结合使用类将一些数据与操作封装成一个对象列表将一些同类对象组合成整体这两者的结合可以表示任意复杂的数据集合体.167编程实例:对DieView的改进将骰子的7个点构成一个列
表好处:对整个列表进行操作时,代码变得简单,因为可以应用循环语句.如:forpipinself.pips:pip.setFill(self.background)foriin[0,3,6]:self.pips[i].setFill(self.foregroun
d)根据掷出的value决定点亮骰子哪些点:可以使用表驱动的写法点亮骰子上的点forpipinself.pips:self.pip.setFill(self.background)ifvalue==1:on=[
3]elifvalue==2:on=[0,6]elifvalue==3:on=[0,3,6]elifvalue==4:on=[0,2,4,6]elifvalue==5:on=[0,2,3,4,6]else:on=[0,1,2,4,5,6]forii
non:self.pips[i].setFill(self.foreground)进一步的优化这个onTable是不变的,可以作为类的实例变量,由__init__初始化.onTable=[[],[3]
,[2,4],[2,3,4],[0,2,4,6],[0,2,3,4,6],[0,1,2,4,5,6]]forpipinself.pips:self.pip.setFill(self.background)on
=onTable[value]foriinon:self.pips[i].setFill(self.foreground)修改后的dieview类的构造函数def__init__(self,win,center,size):#f
irstdefinesomestandardvaluesself.win=win#savethisfordrawingpipslaterself.background="white"#colorofdiefaceself.foreground="black"#col
orofthepipsself.psize=0.1*size#radiusofeachpiphsize=size/2.0#halfthesizeofthedieoffset=0.6*hsize#distancefromcentertooute
rpips#createasquareforthefacecx,cy=center.getX(),center.getY()p1=Point(cx-hsize,cy-hsize)p2=Point(cx+hsize,cy+hsize)rect=Rectangle(p1
,p2)rect.draw(win)rect.setFill(self.background)#Create7circlesforstandardpiplocationsself.pip1=self.__ma
kePip(cx-offset,cy-offset)self.pip2=self.__makePip(cx-offset,cy)self.pip3=self.__makePip(cx-offset,cy+offset)s
elf.pip4=self.__makePip(cx,cy)self.pip5=self.__makePip(cx+offset,cy-offset)self.pip6=self.__makePip(
cx+offset,cy)self.pip7=self.__makePip(cx+offset,cy+offset)self.pips=[self.pip1,self.pip2,self.pip3,self.pip4
,self.pip5,self.pip6,self.pip7]self.onTable=[[],[3],[2,4],[2,3,4],[0,2,4,6],[0,2,3,4,6],[0,1,2,4,5,6]]#
Drawaninitialvalueself.setValue(1)setValue函数defsetValue(self,value):"Setthisdietodisplayvalue."#turnallpipsoffforpipinself.pips:pip.setFil
l(self.background)#turncorrectpipsonon=self.onTable[value]foriinon:self.pips[i].setFill(self.foreground)编程实例:计算器程序=
数据结构的集合+处理数据结构的算法的集合因此:整个应用程序本身可看作对象!编程实例:计算器类每个计算器是计算器类的一个对象.计算器类calculator创建一个计算器的初始界面：由构造函数完成与用户的交互：用户按下某一按钮，显示部分会显示相应的按钮，由run函数实现构造函数创
建一个图形界面及合适的坐标值def__init__(self):#创建计算器的窗口win=GraphWin("calculator",250,300)win.setCoords(0,0,6,7)win.setBackg
round("slategray")self.win=win创建按钮self.__createButtons()创建显示部分self.__createDisplay()创建按钮利用Button类defcreateButtons(s
elf):#设定每个按钮的位置、宽度及值buttonSpecs=[(2,1,.75,'0'),(3,1,.75,'.'),(4.5,1,2,'='),(1,2,.75,'1'),(1,3,.75,'4'),(1,4,.75,'7'),(2,2,.75,'2'),(2,3,
.75,'5'),(2,4,.75,'8'),(3,2,.75,'3'),(3,3,.75,'6'),(3,4,.75,'9'),(4,2,.75,'+'),(4,3,.75,'*'),(4,4,.75,'<-'),
(5,2,.75,'-'),(5,3,.75,'/'),(5,4,.75,'C')]self.buttons=[]height=.75forcx,cy,bwidth,labelinbuttonSpecs:b=Button(self.win,Point(cx,cy),
bwidth,height,label)b.activate()self.buttons.append(b)元组创建按钮的关键是列表bSpecs，它给出了每个按钮的属性说明。它的每个成员称为一个元组元组:用圆
括号包围的一组值.类似列表但内容不可修改.178创建显示区域显示部分创建一个矩形和一个文本框def__createDisplay(self):bg=Rectangle(Point(.5,5.5),Point(5.5,6.5))bg.setFill('whit
e')bg.draw(self.win)text=Text(Point(3,6),"")text.draw(self.win)text.setFace("courier")text.setStyle("bold")text.setSize(16)self
.display=text交互部分设计一个run函数完成所有的交互Run函数反复执行下列动作：等待用户按下按钮根据选择的按钮执行不同的操作defrun(self):while1:key=self.getKeyPress()self.processKey(key)getKey
Press等待mouseclick事件判断点击了哪一个按钮defgetKeyPress(self):while1:p=self.win.getMouse()forbinself.buttons:ifb.cli
cked(p):returnb.getLabel()processKey(key)根据key做不同的处理defprocessKey(self,key):text=self.display.getText()ifkey=='C':self.display.setTex
t("")elifkey=='<-':self.display.setText(text[:-1])elifkey=='=':try:result=eval(text)except:result='ERROR'self.display.setText(str(result))else:self.d
isplay.setText(text+key)数据集合数据集合列表与类一起使用字典无序集合Python提供了另外一种集合类型，称为字典字典类型用来存储“键-值对”可以通过键找到相应的值#cod
ing=gbkdefmain():dict={"apple":"苹果","mellon":"西瓜"}printdict["apple"]printdict["mellon"]main()输出：苹果西瓜字典操作创建：dict={k1:v1,k2
:v2,...,kn:vn}检索：dict[ki]返回相关联的<vi>值可修改：dict[ki]=new_value键类型常用字符串、整数，值类型则任意存储：按内部最有效的方式，不保持创建顺序字典操作键存在性：<dict>ha
s_key(<key>)键列表：<dict>.keys()值列表：<dict>.values()键值对列表：<dict>.items()删除键值对：del<dict>[<key>]添加键值对：
<dict>[<key>]=<value>清空字典：<dict>.clear()字典例缩略语字典abbr={„etc‟:‟cetera‟,„cf‟:‟confer‟,‟ibid‟:‟ibidem‟}查找:abbr[„etc‟]返回cetera修改:abbr[„etc‟]=
„etcetera‟.月份映射表month={1:‟Jan‟,2:‟Feb‟,3:‟March‟,4:‟April‟}显示:printmonth[1]增加键值对:month[5]=„May‟编程实例:词频统计词频统计是有用的一个操作，很多场合都要用到。如搜索引擎等统计文档
中单词的出现频率，并按字母序输出每个单词和词频用字典结构:用很多累积变量显然不好!counts:{<单词>:<频度计数>}过程打开文件并读入将所有单词都转换为小写将标点符号替换成空格将文件内容分解成一个列表对列表的每个成员如果出现过
，词频加1；如果没有出现过，词频为1，添加到count将单词按字母序排序输出单词和对应的频率单词首次出现的处理异常处理try:counts[w]=counts[w]+1exceptKeyError:counts[w]=1分支语句if
counts.has_key(w):counts[w]=counts[w]+1else:counts[w]=1#coding=gbk#统计词频wordCount.pyimportstringdefmain():text=open('wordCount.py','r').read()#打开文件并读入
text=string.lower(text)#将读入的内容全部转为小写#除去标点符号forchin'!"#$%&()*+,-./:;<=>?[\\]ˆ_\'{|}˜':text=string.replace(text,ch,'')words=string
.split(text)#分解成一个列表#开始统计counts={}forwinwords:try:counts[w]=counts[w]+1exceptKeyError:counts[w]=1#按字母序按排序单词uniqueWords=counts.keys()uniqueWords.sor
t()#输出forwinuniqueWords:printw,counts[w]词频统计修改版对大文档，为每个单词输出频度没有意义。希望输出前n个最频繁的单词如何输出前n个最频繁的单词？将count按频度排序。创建一个按频度排序的列表如何将counts按频度排序创建一个<
键，值>对组成的列表：item=counts.items()Sort函数比较元组时，按从左到右的次序。因此对item调用sort函数的结果是按字母序排序解决方法：利用sort函数的参数。Sort函数可
以带一个函数参数，缺省情况下是用内置的cmp函数。该函数有两个参数，当参数1小于、等于、大于参数2时，函数分别返回-1、0、1。自己定义一个比较函数来替代cmp函数对列表item调用sort函数排序
#coding=gbk#统计词频wordCountTopN.pyimportstringdefcompareItems((w1,c1),(w2,c2)):ifc1>c2:return-1elifc1==c2:returncmp(w1,w2)else:return1defmai
n():text=open('wordCount.py','r').read()#打开文件并读入text=string.lower(text)#将读入的内容全部转为小写#除去标点符号forchin'!"
#$%&()*+,-./:;<=>?[\\]ˆ_\'{|}˜':text=string.replace(text,ch,'')words=string.split(text)#分解成一个列表#开始统计counts={}forwinwords:try:
counts[w]=counts[w]+1exceptKeyError:counts[w]=1#输出高频词n=input('howmanywords?')items=counts.items()items.sort(compareItems)foriinrang
e(n):print"%-10s%5d"%items[i]END面向对象设计OO设计过程实例1：壁球比赛CaseOO的特征200200200设计的本质设计的本质是用黑箱及其接口描述系统.每个部件通过其接口提供
一些服务，其他部件是这些服务的用户(客户)客户只需了解服务的接口，而实现细节对客户无关紧要.服务组件只管提供服务的实现，不管客户如何应用.201201201结构化设计与OOD结构化设计设计:黑箱是函数。设计的任务是自顶向下将所需完成的任务设计成一个个函数客
户只要知道函数接口即能使用之.函数这个黑箱中包含的是解决一个问题的过程。函数实现细节被封装在函数定义中.OOD:对象是黑箱，设计的任务是抽象完成任务需要的对象对象这个黑箱中包含了完成任务的过程及完成任务所需的数
据类对外提供的接口即方法.方法的实现对外部客户是不重要的.202202202OOD设计指南OOD：对给定问题找出并定义一组有用的类的过程.确定有用的对象考虑问题描述中的事物这些事物有什么什么属性和行为通过属性确定实例变量通过行为确定接口复杂行为的自顶向下逐步求精反
复设计尝试其他途径力求简单编程实例:壁球比赛对象:球员：有技术水平数据一局比赛：输入两个球员,提供play()记录员：统计比赛结果，提供update(),printReport()主程序核心代码:stats=SimStats()foriinrange(n):theGa
me=RBallGame(probA,probB)theGame.play()stats.update(theGame)stats=printReport()203进一步细化设计一个类时会获得其他类的设计思路例如：实现SimStats的update(aGame)时，需要aG
ame的分数，由此想到RBallGame类应提供getScores方法。又如：实现RBallGame时发现技术是属于球员而非比赛的，因此应设计Player类。各类间的关系可用图来表示Player的设计属性：赢的概率和本次比赛得分行为：是否得分增加得分获取得
分classPlayer:def__init__(self,prob):self.prob=probself.score=0defwinsServe(self):returnrandom()<=self.probd
efincScore(self):self.score=self.score+1defgetScore(self):returnself.scoreRBallGame的设计属性：两个球员和谁发球行为：玩游戏和获取游戏结果玩游戏继续分解出
两个函数：判断游戏是否结束换发球classRBallGame:def__init__(self,probA,probB):self.playerA=Player(probA)self.playerB=Player(probB)self.server=self.pl
ayerAdefplay(self):whilenotself.isOver():ifself.server.winsServe():self.server.incScore()else:self.changeServer()def
isOver(self):a,b=self.getScores()returna==15orb==15or(a==7andb==0)or(b==7anda==0)defchangeServer(self):ifself.server==
self.playerA:self.server=self.playerBelse:self.server=self.playerAdefgetScores(self):returnself.playerA.getScore(),s
elf.playerB.getScore()SimStats的设计属性：A、B赢的次数，A、B不让对方赢的概率行为：更新记录输出记录输出记录进一步分解出打印一行的函数classSimStats:d
ef__init__(self):self.winsA=0self.winsB=0self.shutsA=0self.shutsB=0defupdate(self,aGame):a,b=aGame.getScores()if
a>b:#Awonthegameself.winsA=self.winsA+1ifb==0:self.shutsA=self.shutsA+1else:#Bwonthegameself.winsB=self.winsB+1ifa==0:self.shutsB=self.
shutsB+1defprintReport(self):n=self.winsA+self.winsBprint"Summaryof",n,"games:"printprint"wins(%total)shutouts(%w
ins)"print"--------------------------------------------"self.printLine("A",self.winsA,self.shutsA,n)self.printLine("B",self.winsB,self.shutsB,n)defp
rintLine(self,label,wins,shuts,n):template="Player%s:%4d%5.1f%%%11d%s"ifwins==0:#Avoiddivisionbyzero!shutStr="-----"else:shutStr="%4.1f%%"%(flo
at(shuts)/wins*100)printtemplate%(label,wins,float(wins)/n*100,shuts,shutStr)全局函数defprintIntro():print"Thisprogramsimulatesgamesofracquetballbe
tweentwo"print'playerscalled"A"and"B".Theabilityofeachplayeris'print"indicatedbyaprobability"print"theplayerwinsthepo
intwhenserving.PlayerAalways"print"hasthefirstserve.\n"defgetInputs():a=input("Whatistheprob.playerAwinsaserve?")b=inp
ut("Whatistheprob.playerBwinsaserve?")n=input("Howmanygamestosimulate?")returna,b,nMain函数defmain():printIntro()probA,probB,n=getInputs()#Playthegam
esstats=SimStats()foriinrange(n):theGame=RBallGame(probA,probB)theGame.play()stats.update(theGame)stats.printReport()main()raw_input("\nPress<Ent
er>toquit")编程实例:DicePoker游戏规则:玩家开始时有$100.每轮花$10进行游戏.先投掷一手5个骰子.然后有两次机会重掷部分或全部骰子.最后根据上表结帐.两对$5三同$8一对加三同$1
2四同$15顺子(1-5或2-6)$20五同$30图形界面要求显示余额玩家破产时自动终止，玩家也可选择退出提示程序状态及用户如何响应的信息模型-视图设计方法将复杂程序分解为模型和视图。模型是程序的核心，体现了任务是如何由计
算机来完成的视图是与用户的交互界面。分开的好处：对同一模型，可以设计不同的用户界面。例如，命令行界面或图像界面。模型的设计面向对象程序设计中首先考虑的是对象的抽取程序涉及到骰子和钱，是否这两者都要抽取为对
象？骰子和钱都只需要用一个数字表示，不像是一个对象的好的候选者但游戏感兴趣的是5个骰子，掷5个骰子并分析它们的组合情况可将5个骰子组成的集合封装成一个类DiceDice类保存5个骰子的状态行为：构造器
：初始化Dice对象集合体rollAll：对5个骰子赋随机值roll：对部分骰子赋随机值，其他不变values：返回骰子当前值score：返回骰子的得分(金额)游戏过程的设计游戏过程也作为一个对象对应的类为PokerAppP
okerApp类的对象记录游戏过程中钱、骰子和掷骰子的次数的轨迹，并通过函数run开始玩游戏视图的设计实现界面文本界面GUI界面用户的交互也通过一个类来实现为本界面：TextInterface图形界面：PockInterfaceDice类的实现OO概念:封装将数据以及相关
操作打包在一起的过程.封装的结果就是对象概念.世界是相互作用的对象构成的.封装使”定义”与”使用”的SoC成为可能.封装使得代码重用成为可能.224OO概念:多态性给对象发了消息,具体做什么取决于该对象的类型.例如:
obj.draw(win)对不同图形对象obj将画出不同的图形.LuChaojun,SJTU225OO概念:继承可以从现有的类出发,定义新类.超类与子类子类继承超类的变量和方法,并且另有自己的变量和方法.好处:代码重用.LuChaojun
,SJTU226LuChaojun,SJTU227LuChaojun,SJTU227End算法设计与分析LuChaojun,SJTU229LuChaojun,SJTU229229查找问题问题:在一个列表中查找某个值.def
search(x,nums):#nums为一数值列表,x是一个数#如果找到,返回x在列表中的位置#否则返回-1Python本身就提供有关的功能:判断:xinnums求位置:nums.index(x)LuChaojun,SJTU230LuChaojun,SJTU230230策
略一:线性查找逐个检查列表中的数据.defsearch(x,nums):foriinrange(len(nums)):ifnums[i]==x:returnireturn–1特点:适合无序数据列表不适合大数据量使列表有序后,线性查找算法可略加改
进.(How?)LuChaojun,SJTU231LuChaojun,SJTU231231策略二:两分查找猜数游戏:可取的策略?两分查找:每次查看有序列表的中点数据,根据情况接着查找较大一半或较小一半.defsearch(x,nums):low,high=0,len(nums)-1whi
lelow<=high:mid=(low+high)/2ifx==nums[mid]:returnmidelifx<nums[mid]:high=mid-1else:low=mid+1return-1算法的优劣比较经验分析根据电脑上的运行时间比较抽象分析分析
算法解题所耗"步数"(时间).步数又与问题难度相关查找问题中,问题难度用数据量n衡量LuChaojun,SJTU232LuChaojun,SJTU233LuChaojun,SJTU233233查找算法的比较策略一步数与n成正
比称为线性时间算法策略二步数与log2n成正比称为对数时间算法猜数游戏中:若数的范围是1~1000000,则策略一:平均要猜50万次才能猜对最坏1百万次,最好1次策略二:最坏也只需猜20次递归定义两分查找算法的另一表述:算法binar
ySearch:在nums[low]~nums[high]中查找xmid=(low+high)/2iflow>highx不在nums中elifx<nums[mid]在nums[low]~nums[mid-1]中查找xelse在nums[mid+
1]~nums[high]中查找x大问题的子问题仍是同样形式的问题,故仍用解决大问题的算法来解决子问题.LuChaojun,SJTU234递归定义的特征递归定义完全是合法的,数学里有很多递归定义的对象.如阶乘:n!=1,当n=0;n*(n–1)!,否则这不
是循环定义.递归定义的特征:有奠基情形,这种情形无需递归;每次递归都是针对较小情形;递归链最后终止于奠基情形.LuChaojun,SJTU235Python递归函数例如:计算阶乘的递归函数deffact(n):ifn==0:return1else:ret
urnn*fact(n-1)LuChaojun,SJTU236递归查找算法两分查找的递归版本:defrecBinSearch(x,nums,low,high):iflow>high:return-1mid=(low+high)/2ifx==nums[mid]returnmidelifx
<nums[mid]:returnrecBinSearch(x,nums,low,mid-1)else:returnrecBinSearch(x,nums,mid+1,high)defsearch(x,nums):returnrecBinSearch(x,nums,0,len(nums)-1)Lu
Chaojun,SJTU237递归vs迭代递归算法设计容易易读效率略低迭代算法:用循环设计困难有的问题没有直观的迭代算法效率高排序问题给定数据列表,将其数据重新排列,形成一个有序的(递增)列表.回顾:Python列表类型提供了方法<list>.sort()我们
要学的是如何实现这个方法,而不是学会用现成的朴素策略:选择排序每次从剩下的数据中选择最小值输出.求列表中最小值的算法:参考前面的max算法.defselSort(nums):n=len(nums)forbottominrange(n-1):#求nums[bottom]..num
s[n-1]间的最小值mp=bottom#初始bottom为迄今最小foriinrange(bottom+1,n):#考虑其他值ifnums[i]<nums[mp]:mp=i#新的迄今最小值nums[bottom],nums[mp]=nu
ms[mp],nums[bottom]大数据量时效率低.分而治之:归并排序数据分成两组或更多组,分别对各组排序,再把已有序的各组归并(merge)成完整有序列表.归并:比较两组各自的第一个数据,小者输出,由该组的下一个数据
顶上来继续比较.当某组没有数据,则将另一组整个输出.defmerge(lst1,lst2,lst3):while当lst1和lst2两组都有数据:输出两组第一个数据的较小者至lst3更新该组的第一个数据while某组没
有数据了:将另一组剩余数据输出至lst3分而治之:归并排序(续)问题:如何对各组排序?似乎可以利用递归:对每一组再次应用分而治之的归并排序.因为满足递归的前提条件:奠基情形:组中只有一个数据时无需递归
;每次分组都使列表变小,最终会到达奠基情形.defmergeSort(nums):n=len(nums)ifn>1:m=n/2nums1,nums2=nums[:m],nums[m:]mergeSort(nums1)mergeSort(nums2)merge(nums1,nums2
,nums)排序算法的比较难度和列表大小n有关.选择排序每次循环:从剩余数据中选择最小值,所需步数为剩余数据的个数总的步数:n+(n-1)+...+1=n(n+1)/2称为n2算法归并排序作分组归并图示,可知每层归并都涉及n步,共有log2n层
,故需nlog2n步.称为nlogn算法可计算性与计算复杂性问题可划分为:可计算的:存在确定的机械过程,一步一步地解决问题.可计算,而且能有效解决可计算,但难度太大,不能有效解决不可计算的:不
存在明确的机械过程来求解该问题.不可解,不可判定Hanoi塔问题体现递归威力的经典问题!defmoveTower(n,source,dest,temp):ifn==1:print"Movediskfrom",source,"to",dest+"."else:moveTower(n-1,s
ource,temp,dest)moveTower(1,source,dest,temp)moveTower(n-1,temp,dest,source)难度:需要2n−1步!称为指数时间算法属于难解(intractable)问题.根据Hanoi塔的传说:有64个金盘.就算僧侣
1秒移动一次,至少也要花264−1秒,大约等于5850亿年.停机问题能否编一个终止性判定程序HALT?defHALT(prog,data)若prog(data)终止,则输出True;否则输出False.是不可解(unsolvable)问题!若
有HALT,则歌德巴赫猜想可以迎刃而解:defgc():n=2whileTrue:if2*n不是两个素数的和,则返回Falsen=n+1然后运行HALT(gc)即可.停机问题(续)说HALT不存在只能通过严格证明:假设存在HALT(prog,data).
则编程序defstrange(p):result=HALT(p,p)ifresult==False:#即p(p)不终止returnelse:whileTrue:n=1运行strange(strange),结果如何?LuChaojun,SJTU2
48LuChaojun,SJTU248End
辽公网安备 21102102000191号
营业执照
