1、第四章 计算机解决问题的方法第四章 计算机解决问题的方法第四章 计算机解决问题的方法 教学目的：了解计算机解决问题的一般步骤 理解算法和程序设计的概念 理解结构化程序设计的含义 掌握三种基本结构流程图的画法 初步学会用N-S流程图表示结构化算法 掌握“自顶向下，逐步细化”的解决问题方法 教学重点（难点）：掌握三种基本结构流程图的画法 教学课时：13课时第四章 计算机解决问题的方法第四章 计算机解决问题的方法选择问题循环问题顺序问题 生活问题的解决自顶向下，逐步细化解决问题的方法本章内容第四章 计算机解决问题的方法4.1 生活问题的解决生活问题的解决4.1.1日常生活问题的处理过程 程序设计：寻
2、找方法和步骤的过程 算法：解决问题的方法和步骤第四章 计算机解决问题的方法4.1.1日常生活问题的处理过程例题：萧峰同学准备用几年积攒下来的零钱，买一台计算机、一辆自 行车和一双拳击手套。他家附近的计算机公司、银行、体育用品商店和自行车行所处位置如图4-1所示。他应该怎样设计完成任务的线路和步骤呢？4.1 生活问题的解决生活问题的解决第四章 计算机解决问题的方法方法A：（1）去银行取钱；（2）去体育用品商店买拳击手套；（3）到计算机公司买计算机；（4）扛着计算机到自行车商店买自行车；（5）骑车运计算机回家。方法B：（1）去银行取钱；（2）去自行车商店买自行车；（3）骑自行车到体育用品商店买拳击
3、手套；（4）到计算机公司买计算机；（5）骑车运计算机回家。4.1 生活问题的解决生活问题的解决第四章 计算机解决问题的方法4.1.2 算法的表示方法 常见的算法表示方法有：文字描述、图解表示、音像演示、流程图表示等。制作过程：制胎 掐丝点蓝 烧蓝 打磨 镀金图4-2 文字描述算法的实例景泰蓝的制作1.用文字描述算法实例：景泰蓝的制作（叶圣陶）优点是：符合人们日常的习惯，容易表达，常用在要求不必太严格的场合。缺点是：文字冗长，不够严谨，容易产生歧义。4.1 生活问题的解决生活问题的解决第四章 计算机解决问题的方法4.1.2 算法的表示方法2.用图解描述算法 常见的游戏下载步骤说明（图4-3）就是
4、一种典型的算法图解。例子：广播操动作图解、建筑和机械行业的施工图纸等。特点：直观形象，但成本较高，还需要一定的制作技术作保障。4.1 生活问题的解决生活问题的解决第四章 计算机解决问题的方法图图4-3 游戏软件下载游戏软件下载算法的图解表示实例算法的图解表示实例4.1 生活问题的解决生活问题的解决第四章 计算机解决问题的方法4.1.2 算法的表示方法3.音像媒体演示算法 例如：有些微波炉生产厂家，特意附送几张用微波炉烹制佳肴的光盘。特点：容易吸引人们的注意力，但制作成本比较昂贵。4.1 生活问题的解决生活问题的解决第四章 计算机解决问题的方法4.1.2 算法的表示方法4.用流程图描述 流程图是
5、以若干有关系的框图来描述算法流程的工具，它的画法有统一的规定。特点：简洁概括、关系分明。4.1 生活问题的解决生活问题的解决第四章 计算机解决问题的方法4.1 生活问题的解决生活问题的解决4.1.3 传统流程图流程图一般有传统流程图和N-S流程图。下表是传统流程图规定的常用符号形状及相应含义。图形符号图形符号名称名称说明说明起止框表示一个算法的开始或结束输入、输出框框内标明输入、输出的内容处理框框内标明所进行的处理判别框框内标明判断条件，并要在框外标明条件成立（Y）及条件不成立（N）时的两种不同流向。连接圈表示算法流向的出口连接点或入口连接点。同一对出口点、入口点的连接圈内，必须标以相同的符号
6、。第四章 计算机解决问题的方法4.1 生活问题的解决生活问题的解决4.1.3 传统流程图下图是出租车收费标准。(a)出租车收费规定 第四章 计算机解决问题的方法4.1 生活问题的解决生活问题的解决4.1.3 传统流程图用传统流程图描述了出租车收费问题的计算过程。流程开始输入路程sS3？f=8f=8+1.5*(s-3)输出运费f流程结束第四章 计算机解决问题的方法4.1 生活问题的解决生活问题的解决4.1.3 传统流程图 优点：直观形象、流程清晰，成本较低。缺点：流程图面积较大，而且由于流程线的使用，使流程任意转移，容易使人弄不清流程的思路。第四章 计算机解决问题的方法4.1.4 结构化流程图的
7、三种基本结构与N-S流程图 1966年，Bohm和Jacopini证明，任何复杂的流程都可以用顺序、选择（或称为分支）和循环（或称为重复）三种基本结构组合而成。结构化流程的核心内容就是：所有的流程只能由顺序结构、选择结构（或称为分支结构）、循环结构（或称为重复结构）三种基本结构组成，其中循环结构又可分为“当型循环结构”和“直到型循环结构”，而其它所有的流程都是由这三种结构派生而出的。4.1 生活问题的解决生活问题的解决第四章 计算机解决问题的方法4.1.4 结构化流程图的三种基本结构与N-S流程图1973年 美国学者B.Schneiderman和I.Nassi N-S流程图。N-S图的全部算法
8、都写在一个框内，每一种基本结构也是一个框，因此也常称此为盒图。4.1 生活问题的解决生活问题的解决图4-5 N-S图表示出租车收费问题输入路程sS3？YNf=8f=8+1.5*(s-3)输出运费f第四章 计算机解决问题的方法4.2 计算机解决问题的方法之一计算机解决问题的方法之一顺序顺序 4.2.1 顺序结构及其流程图图4-6 一个典型的游戏登录界面 第四章 计算机解决问题的方法4.2 计算机解决问题的方法之一计算机解决问题的方法之一顺序顺序 4.2.1 顺序结构及其流程图顺序结构：按顺序进行解决问题的结构。图4-7就是顺序结构的流程图，表示其中的a块操作与b块操作之间须按顺序执行。（a）传统
9、流程图表示（b）N-S图表示图4-7 顺序结构的流程图a块b块ABa块b块第四章 计算机解决问题的方法4.2 计算机解决问题的方法之一计算机解决问题的方法之一顺序顺序 4.2.1 顺序结构及其流程图图4-8是登录游戏的过程的N-S图 输入帐号和密码点击“确定”按钮进入游戏流程开始输入帐号和密码点击“确定”按钮进入游戏流程结束（a）传统流程图表示（b）N-S图表示图4-8 登录游戏的流程图第四章 计算机解决问题的方法4.2 计算机解决问题的方法之一计算机解决问题的方法之一顺序顺序 4.2.2 顺序结构的计算机算法举例例4-1用流程图表示求底边为a、高为h的三角形面积s的算法。计算机处理这个问题的
10、步骤为：S1：将a和h的值输入到计算机；S2：根据公式计算s的值；S3：输出s的值。图4-9 求三角形面积的流程图输入底边a和高ha*h/2s输出s的值流程开始输入底边a和高ha*h/2s输出s的值流程结束第四章 计算机解决问题的方法4.2 计算机解决问题的方法之一计算机解决问题的方法之一顺序顺序 4.2.2 顺序结构的计算机算法举例例4-2有两个变量a和b，将它们的值互换。主要步骤为：S1：将变量a的值送给变量c（）；S2：将变量b的值送给变量a（）；S3：将变量c的值送给变量b（）。完整的步骤为：S0：输入变量a和b的值；S1：将变量a的值送给变量c（）；S2：将变量b的值送给变量a（）；
11、S3：将变量c的值送给变量b（）。S4：输出交换后的a、b的值。图4-10 互换两个变量的值 流程开始输入变量a和b的值cb输出a、b的值流程结束acba第四章 计算机解决问题的方法4.2 计算机解决问题的方法之一计算机解决问题的方法之一顺序顺序 4.2.2 顺序结构的计算机算法举例图4-10 互换两个变量的值 b ac b输出a、b的值a c输入变量a和b的值第四章 计算机解决问题的方法4.3 计算机解决问题的方法之一计算机解决问题的方法之一选择选择 4.3.1 分支结构及其流程图选择结构：也称为分支结构，需要判断给定的条件是否满足，然后根据判断的结果在两条分支路径中选择执行一条的结构。(a
12、)传统流程图表示(b)N-S图表示图4-11选择结构a块b块AB条件P条件P满足不满足a块b块第四章 计算机解决问题的方法4.3 计算机解决问题的方法之一计算机解决问题的方法之一选择选择 4.3.1 分支结构及其流程图图4-12 选择结构的流程图实例有没有游戏帐号是否申请帐号点击“确定”按钮输入帐号和密码进入游戏流程开始输入帐号和密码有没有游戏帐号申请帐号进入游戏流程结束点击“确定”按钮是否第四章 计算机解决问题的方法4.3 计算机解决问题的方法之一计算机解决问题的方法之一选择选择 4.3.2 分支结构的计算机算法举例例4-3某城市的出租车收费标准为：路程在3公里以下，收起步价8元；路程超过3
13、公里者，超过部分按每公里1.5元加收。如果路程为s公里，运费为f元，则计算公式为：算法流程图如图4-4所示。f=8 (s3)8+(s-3)1.5 (s3)第四章 计算机解决问题的方法4.3 计算机解决问题的方法之一计算机解决问题的方法之一选择选择4.3.3 多分支问题市发展计划委员会关于调整居民自来水价格关于调整居民自来水价格的通知的通知 为节约用水，从2005年5月1日起实行居民用水分段收费办法。当居民用水不超过5吨时，按每吨0.8元收费；当月用水超过5吨不超过10吨时，超过部分按每吨1元收费；当月用水超过10吨时，超过部分按每吨1.5元收费。例4-4 近年夏天，全国很多地区发生严重干旱，自
14、来水公司为鼓励市民节约用水，采取分段收费标准（如右）。试用N-S图表示水费的收取问题。分析：设居民当月用水x吨，水费y元，计算公式为：y=0.8x (0 x5)4+1(x-5)(5x10)4+5+1.5(x-10)(x10)第四章 计算机解决问题的方法4.3 计算机解决问题的方法之一计算机解决问题的方法之一选择选择4.3.3 多分支问题图4-14 用两分支结构描述三分支问题输入当前月水量xx5成立不成立y=0.8*xy=4+1*(x-5)输出当月水费yx10成立不成立y=9+1.5*(x-10)第四章 计算机解决问题的方法4.3 计算机解决问题的方法之一计算机解决问题的方法之一选择选择 4.3
15、.3 多分支问题例4-5商场搞促销活动，向一次性购物金额高的顾客让利，张贴广告如右。请用N-S图描述计算机根据购货总额（折前货款）x来计算实付货款（折后货款）y的过程。好 消 息 为答谢广大顾客，本商场隆重推出金秋让利活动。凡在本商一次性购物 2000元(含2000元,以下同)到3000元者，给予九五折优惠；3000元到4000元者，给予九折优惠；4000元到5000元者，给予八五折优惠；5000元以上者，给予八折优惠。欢迎参与！第四章 计算机解决问题的方法4.3 计算机解决问题的方法之一计算机解决问题的方法之一选择选择4.3.3 多分支问题图4-14 用两分支结构描述三分支问题分析：根据题意
16、可知：20000.95200030000.9300040000.85400050000.85000 xxxxyxxxxxx第四章 计算机解决问题的方法4.3 计算机解决问题的方法之一计算机解决问题的方法之一选择选择4.3.3 多分支问题图4-15 用两分支结构描述多分支问题输入打折前的货款xX2000成立不成立y=0.95*xy=0.9x输出打折后的应付款y成立不成立y=0.85xy=xX3000X4000不成立不成立成立成立X5000y=0.8x第四章 计算机解决问题的方法4.4 计算机解决问题的方法之一计算机解决问题的方法之一循环循环 4.4.1 循环结构及其流程图图4-17 账号或密码出
17、错时的系统提示 第四章 计算机解决问题的方法4.4 计算机解决问题的方法之一计算机解决问题的方法之一循环循环 4.4.1 循环结构及其流程图 重复结构:也称为循环结构，就是反复多次执行某些步骤的结构。循环结构可分为当型循环结构和直到型循环结构。第四章 计算机解决问题的方法4.4 计算机解决问题的方法之一计算机解决问题的方法之一循环循环 4.4.1 循环结构及其流程图 当型循环：当指定的条件P成立时执行A操作，然后再返回判断P条件是否还成立，如成立再执行A如此重复下去，直到P条件不成立为止。图4-18（a）当型循环的传统流程图 图4-18（b）当型循环的N-S流程图 条件P不满足满足A块当给定条
18、件P满足A块第四章 计算机解决问题的方法4.4 计算机解决问题的方法之一计算机解决问题的方法之一循环循环 4.4.1 循环结构及其流程图图4-19 游戏登录过程的表示输入帐号和密码按”确定”按钮当帐号或密码有错时系统提示出错信息用户重新输入帐号密码用户按”确定”按钮进入游戏第四章 计算机解决问题的方法4.4 计算机解决问题的方法之一计算机解决问题的方法之一循环循环 4.4.1 循环结构及其流程图 直到型循环结构：先执行A操作，再判断P条件是否成立，如不成立则返回再执行A操作如此重复下去，直到P条件成立为止。图4-20是直到型循环的两种流程图。图4-20(a)直到型循环的传统流程图图4-20(b
19、)直到型循环的N-S图直到给定条件P满足A块条件P满足不满足A块第四章 计算机解决问题的方法4.4 计算机解决问题的方法之一计算机解决问题的方法之一循环循环 4.4.2 循环结构的计算机算法举例图4-21 例4-6对应的N-S图例4-6在等式两边的中填入同一个数字，使38256=36528 成立。x=0 x+1x直到(30+x)*8256=(x*10+3)*6528输出x第四章 计算机解决问题的方法4.4 计算机解决问题的方法之一计算机解决问题的方法之一循环循环 4.4.2 循环结构的计算机算法举例 例例4-74-7按照国家统计局调查统计，2003年我国人口出生率为1.241%，死亡率为0.6
20、4%，人口自然增长率为0.601%。如果继续保持这个增长率不变，那么再过多少年，我国大陆的人口数会增加到14亿(以2004年底的人口数13亿为基础)？算法分析：S1：输入最初的人口数量p和增长率c。S2：计算到下一年年底的人口数量新值p，并累计年数n。S3：判断：人口数量是否已经达到14亿？若没有，则重复执行S2，若达到，则终止循环。S4：输出经过的年数n。第四章 计算机解决问题的方法4.4 计算机解决问题的方法之一计算机解决问题的方法之一循环循环 4.4.2 循环结构的计算机算法举例(a)例4-7的当型N-S图(b)例4-7的直到型N-S图图4-23 人口问题的N-S图p=13c=0.006
21、01n=0当p14p*(1+c)pn+1n输出np=13c=0.00601n=0直到p14p*(1+c)pn+1n输出n第四章 计算机解决问题的方法4.5 复杂问题的计算机处理复杂问题的计算机处理4.5.1 自顶向下，逐步细化的解决问题方法 处理复杂问题的有效方法：从全局到局部，从抽象到具体，一步一步细化的方法。“逐步细化”或“逐步求精”：由抽象到具体的算法设计方法。第四章 计算机解决问题的方法4.5.2“自顶向下，逐步细化”的方法应用举例例4-8找出甲、乙、丙三位同学身高各不相同，求出个子最高的同学的身高值。（1）“做什么”？子问题S1：输入三人的身高（图4-24（a）（b）子问题S2：通过
22、比较输出最大的身高值（图4-21（a）。4.5 复杂问题的计算机处理复杂问题的计算机处理(图4-21(a)(图4-21(b)S1:输入三人的身高值S2:通过比较出最大的身高值S1:输入a,b,c第四章 计算机解决问题的方法4.5.2“自顶向下，逐步细化”的方法应用举例（2）“如何做”？分析ab两种情况（图4-24（c）进一步细化子问题S2，当ab时 比较a和c的大小，谁大就是最大身高值（图4-24（d）当ab时 比较b和c的大小，谁大就是最大身高值（图4-24（e）4.5 复杂问题的计算机处理复杂问题的计算机处理ab是否S2.1:身高的最大值在a、c中产生S2.2:身高的最大值在b、c中产生ac是否S2.1.1:输出“甲为最高”S2.1.2:输出“丙为最高”bc是否S2.2.1:输出“乙为最高”S2.2.2:输出“丙为最高”ac是否S2.1.1:输出“甲为最高”S2.1.2:输出“丙为最高”bc是否S2.2.1:输出“乙为最高”S2.2.2:输出“丙为最高”第四章 计算机解决问题的方法4.5.2“自顶向下，逐步细化”的方法应用举例4.5 复杂问题的计算机处理复杂问题的计算机处理图4-25 求三个数中的最大数 ac是否S2.1.1:输出“甲为最高”S2.1.2:输出“丙为最高”bc是否S2.2.1:输出“乙为最高”S2.2.2:输出“丙为最高”ab是否
