模拟与设计
模拟与设计
模拟 ·我们已经掌握的工具足以让我们编程解决有意 思的问题 一有意思是指：如果不设计实现计算机算法，该问题是很难或不可 能解决的 0 模拟：用计算机为实际问题建模，从而提供非如 此不能获得的信息 一这是解决实际问题的强大技术，每天都在应用： 人天气预报 人设计飞机 人制作电影特效 Lu Chaojun,SJTU 2
Lu Chaojun, SJTU 2 模拟 • 我们已经掌握的工具足以让我们编程解决有意 思的问题. – 有意思是指:如果不设计实现计算机算法,该问题是很难或不可 能解决的 • 模拟:用计算机为实际问题建模,从而提供非如 此不能获得的信息. – 这是解决实际问题的强大技术,每天都在应用: ©天气预报 ©设计飞机 ©制作电影特效 ©
一个模拟问题：Racquetball ·问题：为什么球技只比对手略差，却输掉绝 大多数的比赛？ 一一种可能是心理上的：你头脑中自以为比对 手只是略差，实际情况是你差很多 一另一种可能：这是壁球运动本身的特性，能力 上的细微差距却导致压倒性的胜负 。 解决方法：编程模拟壁球，通过模拟不同水平球 员之间的数千场比赛来发现原因. Lu Chaojun,SJTU 3
一个模拟问题:Racquetball • 问题:为什么球技只比对手略差,却输掉绝 大多数的比赛? – 一种可能是心理上的:你头脑中自以为比对 手只是略差,实际情况是你差很多. – 另一种可能:这是壁球运动本身的特性,能力 上的细微差距却导致压倒性的胜负. • 解决方法:编程模拟壁球,通过模拟不同水平球 员之间的数千场比赛来发现原因. Lu Chaojun, SJTU 3
美式壁球基本知识 ·球，球拍，场地 ·一人发球开始比赛 。 然后两人交替击球（称为一个rally) 0 当一人未能击出合法球，则输掉本rally; -发球方输则交换发球权： -发球方赢则得1分 ·先得15分者赢1局 Lu Chaojun,SJTU 4
Lu Chaojun, SJTU 4 美式壁球基本知识 • 球,球拍,场地 • 一人发球开始比赛 • 然后两人交替击球(称为一个rally) • 当一人未能击出合法球,则输掉本rally; – 发球方输则交换发球权; – 发球方赢则得1分. • 先得15分者赢1局. Lu Chaojun, SJTU
程序规格 ·球技水平：用球员作为发球方的获胜概率 来模拟. ·程序规格 输入：两个球员的水平，模拟比赛局数， 输出：两球员各自的获胜局数及比例 Lu Chaojun,SJTU 5
程序规格 • 球技水平:用球员作为发球方的获胜概率 来模拟. • 程序规格 输入:两个球员的水平,模拟比赛局数. 输出:两球员各自的获胜局数及比例. Lu Chaojun, SJTU 5
随机数 模拟的是不确定性事件：rally的输赢是随机的 -这类模拟也称为Monte Carlo算法 如何用确定性的计算机模拟非确定性？ 一用函数生成随机数（实际上是伪随机数） 人从种子值开始，计算出一个“随机”数； 人如果还需要，就用上一个随机数反馈给生成函数，生成下一 个随机数 -Python)库random提供了一些伪随机数生成函数： 人从加载库的日期时间导出种子值 人randrange():生成指定范围（类似range)内的一个整数 人random():生成[0，l)间的一个浮点数 Lu Chaojun,SJTU 6
随机数 • 模拟的是不确定性事件:rally的输赢是随机的. – 这类模拟也称为Monte Carlo算法 • 如何用确定性的计算机模拟非确定性? – 用函数生成随机数(实际上是伪随机数). ©从种子值开始,计算出一个“随机”数; ©如果还需要,就用上一个随机数反馈给生成函数,生成下一 个随机数. – Python库random提供了一些伪随机数生成函数: ©从加载库的日期时间导出种子值. ©randrange():生成指定范围(类似range)内的一个整数 ©random():生成[0,1)间的一个浮点数 Lu Chaojun, SJTU 6
用random模拟输赢 o 设发球人获胜概率是prob ·程序中显然需要这样的代码： f发球者胜了本回合： score score 1 -并且要使该条件为真的情况占prob ·用random函数模拟： if random()<prob: score score 1 Lu Chaojun,SJTU 7
用random模拟输赢 • 设发球人获胜概率是prob • 程序中显然需要这样的代码: if 发球者胜了本回合: score = score + 1 – 并且要使该条件为真的情况占prob • 用random函数模拟: if random() < prob: score = score + 1 Lu Chaojun, SJTU 7
自顶向下设计 ·对复杂问题常采用自顶向下设计： -将对一般问题的解决方案用若干个较小问题 来表达. 一再对较小问题用同样的方法分解. 一直至小问题很容易求解 一将所有小问题的解合并，就得到大问题的解 Lu Chaojun,SJTU 8
自顶向下设计 • 对复杂问题常采用自顶向下设计: – 将对一般问题的解决方案用若干个较小问题 来表达. – 再对较小问题用同样的方法分解. – 直至小问题很容易求解. – 将所有小问题的解合并,就得到大问题的解. Lu Chaojun, SJTU 8
项层设计 。基本算法： 介绍程序功能 取得输入：probA,probB,n 利用probA和orobB模拟n局比赛 输出结果报告 ·基本程序 def main () printIntro() probA,probB,n getInputs() winsA,winsB simNGames (n,probA,probB) printSummary (winsA,winsB) Lu Chaojun,SJTU 9
顶层设计 • 基本算法: 介绍程序功能 取得输入: probA, probB, n 利用probA和probB模拟n局比赛 输出结果报告 • 基本程序 def main(): printIntro() probA, probB, n = getInputs() winsA, winsB = simNGames(n, probA, probB) printSummary(winsA, winsB) Lu Chaojun, SJTU 9
分离关注 Separation of Concerns(SoC):将计算机程序分 解成不同部分，各部分功能重叠越少越好 一一个关注是指程序中的一个兴趣点或焦点 o 好处： 一允许多人独立开发系统的不同部分 一便于重用 一确保系统可维护性 -易于增加新功能 一使系统易理解 Lu Chaojun,SJTU 10
分离关注 • Separation of Concerns (SoC): 将计算机程序分 解成不同部分,各部分功能重叠越少越好. – 一个关注是指程序中的一个兴趣点或焦点. • 好处: – 允许多人独立开发系统的不同部分 – 便于重用 – 确保系统可维护性 – 易于增加新功能 – 使系统易理解 – ...... Lu Chaojun, SJTU 10