CT09模拟设计.ppt

1、模拟与设计,Lu Chaojun, SJTU,2,Lu Chaojun, SJTU,2,2,模拟,我们目前掌握的工具已经足以解决一些有意思的问题. 有意思是指:如果不设计实现计算机算法,该问题是很难或不可能解决的. 模拟:用计算机为实际问题建模,从而提供非如此不能获得的信息. 这是解决实际问题的强大技术,每天都在应用: 天气预报 设计飞机 制作电影特效 .,一个模拟问题:Racquetball,球员的困惑:为什么球技只比对手略差,却输掉绝大多数的比赛? 一种可能是心理上的:你头脑中自以为比对手只是略差,实际情况是你差很多. 另一种可能:这是壁球运动本身的特性,能力上的细微差距却导致压倒性的胜负

2、. 解决困惑:编程模拟壁球,通过模拟不同水平球员之间的数千场比赛来发现原因.,Lu Chaojun, SJTU,3,Lu Chaojun, SJTU,4,Lu Chaojun, SJTU,4,美式壁球基本知识,球,球拍,场地 一人发球开始比赛 然后两人交替击球(称为一个rally) 当一人未能击出合法球,则输掉本rally; 发球方输则交换发球权; 发球方赢则得1分. 先得15分者赢1局.,Lu Chaojun, SJTU,程序规格说明,球技水平:用球员作为发球方时的获胜概率来模拟. 程序规格说明 输入:两个球员的水平,模拟比赛局数. 输出:两球员各自的获胜局数及比例.,Lu Chaojun,

3、 SJTU,5,随机数,模拟的是不确定性事件:每回合输赢是随机的. 这类模拟也称为Monte Carlo算法 如何用确定性的计算机模拟非确定性? 用函数生成随机数(实际上是伪随机数). 从种子值开始,计算出一个“随机”数; 如果还需要,就用上一个随机数反馈给生成函数,生成下一个随机数. Python库random提供了一些伪随机数生成函数: randrange():生成指定范围内的一个整数 random():生成0,1)间的一个浮点数,Lu Chaojun, SJTU,6,用random模拟输赢,设发球人获胜概率是prob 程序中显然需要这样的代码: if 发球者胜了本回合: score =

4、score + 1 并且要使该条件为真的情况占prob 用random函数模拟: if random() prob: score = score + 1,Lu Chaojun, SJTU,7,prob,1 prob,prob,1,0,自顶向下设计,对复杂问题常采用自顶向下设计: 将对一般问题的解决方案用若干个较小问题来表达. 再对较小问题用同样的方法分解. 直至小问题很容易求解. 将所有小问题的解合并,就得到大问题的解.,Lu Chaojun, SJTU,8,顶层设计,基本算法: 介绍程序功能 取得输入: probA, probB, n 利用probA和probB模拟n局比赛 输出结果报告 基

5、本程序 def main(): printIntro() probA, probB, n = getInputs() winsA, winsB = simNGames(n, probA, probB) printSummary(winsA, winsB),Lu Chaojun, SJTU,9,分离关注,Separation of Concerns (SoC): 将计算机程序分解成不同部分,各部分功能重叠越少越好. 一个关注是指程序中的一个兴趣点或焦点. 好处: 允许多人独立开发系统的不同部分 便于重用 确保系统可维护性 易于增加新功能 使系统易理解 .,Lu Chaojun, SJTU,10,

6、结构图,模拟壁球问题的程序被分成了四个关注: 为每个关注定义了函数的接口(interface)或称特征(signature). 即函数名,参数,返回值的信息 高层设计时只须关心函数的接口,而非函数的实现. 用结构图(或称模块层次图)表示:,Lu Chaojun, SJTU,11,抽象,在设计的每一层,接口指明了需要下一层的哪些细节;其他可暂时忽略. 抽象:确定某事物的重要特性并忽略其他细节的过程. 抽象是基本的设计工具. 自顶向下设计的整个过程可视为发现有用的抽象的系统化方法.,Lu Chaojun, SJTU,12,第二层设计,两个简单函数 def printIntro(): print T

7、his program simulates a game of racquetball print between two players called A and B. print The abilities of each player is indicated by a print probability (a number between 0 and 1) that print the player wins the point when serving. Player A print always has the first serve.“ def getInputs(): # RE

8、TURNS three simulation parameters probA, probB and n a = input(What is the prob. player A wins a serve? ) b = input(What is the prob. player B wins a serve? ) n = input(How many games to simulate? ) return a, b, n,Lu Chaojun, SJTU,13,第二层设计(续),设计simNGames() winsA和winsB初始化为0 循环n次 模拟一局 if playerA胜: win

9、sA加1 else: winsB加1 def simNGames(n, probA, probB): winsA = winsB = 0 for i in range(n): scoreA, scoreB = simOneGame(probA, probB) if scoreA scoreB: winsA = winsA + 1 else: winsB = winsB + 1 return winsA, winsB,Lu Chaojun, SJTU,14,第三层设计,simOneGame:整个模拟程序的关键. 是个不确定循环:不断进行回合较量,直至一局结束 需要两个累积器:记分 需要一个二值累

10、积器:记录发球方 得分初始化为0 发球方置为A 当本局未结束就循环: 模拟一次发球 修改比赛状态 返回比分,Lu Chaojun, SJTU,15,第三层设计(续),结束条件用函数gameOver def simOneGame(probA, probB): scoreA = 0 scoreB = 0 serving = A while not gameOver(scoreA, scoreB): if serving = A: if random() probA: scoreA = scoreA + 1 else: serving = B else: if random() probB: sco

11、reB = scoreB + 1 else: serving = A return scoreA, scoreB,Lu Chaojun, SJTU,16,第三层设计(续),函数gameOver def gameOver(a,b): # a and b represent scores for a racquetball game # RETURNS true if the game is over, false otherwise. return a=15 or b=15 函数printSummary def printSummary(winsA, winsB): # Prints a sum

12、mary of wins for each player. n = winsA + winsB print nGames simulated:, n print Wins for A: %d (%0.1f%) % (winsA, float(winsA)/n*100) print Wins for B: %d (%0.1f%) % (winsB, float(winsB)/n*100) 完整程序:rball.py 运行之,看看技术的小差距是否导致大胜负差? 试一试:修改成模拟多局制比赛.,设计过程小结,自顶向下,逐步求精 将算法表达为一系列较小问题 为每个小问题设计一个(函数)接口 用各小问题

13、的接口细化算法 对各小问题重复此过程,自底向上实现,从结构图的底层开始实现,逐级向上. 每完成一个模块,进行单元测试. 这也是分离关注,使debug更容易,其他设计技术,原型技术(prototyping):从程序的一个简单版本开始,逐步增加功能,直至完全满足程序规格. 初始的简单版本称为原型(prototype). 原型技术导致螺旋式开发过程: 原型的设计,实现,测试 新功能的设计,实现,测试 适合情况:对程序功能不熟悉,难以按自顶向下设计方法给出完整设计.,例:壁球模拟程序的原型,simOneGame() 固定水平五五开 固定比赛30个rally from random import random def simOneGame(): scoreA = 0 scoreB = 0 serving = A for i in range(30): if serving = A: if random() .5: scoreA = scoreA + 1 else: serving = B else: if random() .5: scoreB = scoreB + 1 else: serv