第六讲、算法和流程图

第2章、程序的灵魂——算法/本章学习目标理解算法的概念了解算法的表示方法掌握流程图的绘制方法掌握三种基本结构的流程图了解结构化程序设计方法/内容进度算法算法的表示方法自然语言传统流程图N-S流程图伪代码计算机语言各种表示方法的比较结构化程序设计方法文档和注释/算法的引入问题：计算矩形的周长第一步：定义三个变量存储长、宽和周长第二步：提示用户输入矩型的长和宽第三步：计算周长，两个长加上两个宽第四步：打印计算结果算法的定义：解决问题所使用的一系列合乎逻辑的、简洁的步骤。lengthwidth/算法与程序关系著名科学家沃思（NikiklausWirth）的公式：数据结构＋算法＝程序扩充后的公式：数据结构＋算法＋程序设计方法＋语言和环境＝程序算法是灵魂，数据结构是加工对象，语言是工具，程序设计方法是使用手段。/算法的特性有穷性确定性有效性有零个或多个输入有一个或多个输出/算法的分析与优化分析程序的算法设计，应先看主流程图，再逐步细化地分析了解算法是否实现了任务需求，方法是否合理性能上是否存在瓶颈，能否被优化如果有多个输入条件，处理时是否覆盖了全部输入条件如果有多个输出结果，其输出是否被系统所定义和处理/内容进度算法算法的表示方法自然语言传统流程图N-S流程图伪代码计算机语言各种表示方法的比较结构化程序设计方法文档和注释/算法的表示方法案例：判断2000～2500年中的每一年是否为闰年。闰年的条件：能被4整除，但不能被100整除的年份；能被100整除，又能被400整除的年份；/自然语言自然语言描述：设y为被检测的年份，则算法可表示如下：S1：2000→y；S2：若y不能被4整除，则输出y“不是闰年”，然后转到S6；S3：若y能被4整除，不能被100整除，则输出y“是闰年”，然后转到S6；S4：若y能被100整除，又能被400整除，输出y“是闰年”，然后转到S6；S5：输出y“不是闰年”，然后转到S6；S6：y+1→y；S7：当y≤2500时,返回S2继续执行，否则结束。/自然语言使用自然语言描述算法的优缺点：优点：通俗易懂缺点：文字冗长含义不太严格，容易出现歧义/内容进度算法算法的表示方法自然语言传统流程图N-S流程图伪代码计算机语言各种表示方法的比较结构化程序设计方法文档和注释/传统流程图用一些图框表示指令或活动的各种操作流程ANSI规定的常用流程图符号：起始框输入/输出框判断框处理框流程线连接点注释框/三种基本结构顺序结构选择结构ABPYNAB/三种基本结构循环结构PAY当型（while）循环结构NPAYN直到型（until）循环结构/应用举例优点：比较清晰，可以解决任何复杂的问题缺点：流程图比较长，基本结构之间的流程线多余/内容进度算法算法的表示方法自然语言传统流程图N-S流程图伪代码计算机语言各种表示方法的比较结构化程序设计方法文档和注释/N-S流程图美国学者I.Nassi和B.shneiderman提出流程图符号：AB顺序结构PYNAB选择结构当P成立A当型循环结构A直到P成立直到型循环结构/应用举例y+1=y打印“非闰年”优点：直观易懂缺点：画起来比较麻烦，不易修改/内容进度算法算法的表示方法自然语言传统流程图N-S流程图伪代码计算机语言各种表示方法的比较结构化程序设计方法文档和注释/伪代码BEGIN（算法开始）2000＝ywhiley=2500{ify能被4整除ify不被100整除printy：”是闰年”elseify能被400整除printy：”是闰年”elseprinty：”非闰年”endifendifelseprinty：”非闰年”endify＋1＝y}END(算法结束)/内容进度算法算法的表示方法自然语言传统流程图N-S流程图伪代码计算机语言各种表示方法的比较结构化程序设计方法文档和注释/#includestdio.hvoidmain(){inty=2000;while(y=2500){if((y%4)==0){if(y%100!=0)printf(%d年是闰年\n,y);elseif(y%400==0)printf(%d年是闰年\n,y);elseprintf(%d年是非闰年\n,y);}elseprintf(%d年是非闰年\n,y);y=y+1;}}计算机语言/内容进度算法算法的表示方法自然语言传统流程图N-S流程图伪代码计算机语言各种表示方法的比较结构化程序设计方法文档和注释/表示方法优点缺点自然语言通俗易懂文字冗长，含义不太严格，容易出现歧义流程图比较清晰，可以解决任何复杂的问题流程图比较长，基本结构之间的流程线多余N-S流程图直观易懂画起来比较麻烦，不易修改伪代码书写比较自由，容易表达思想，容易修改不太直观，容易出现逻辑上的错误计算机语言表示直接在计算机上可以运行，得到结果必须严格遵守所用语言的语法规则各种表示方法比较/绘制流程图应该注意的事项一个流程图只有一个入口点和一个出口点；主要画出问题的逻辑处理过程，无需将每一步都画的很详细；如果算法很复杂，则可以先画出大的逻辑关系，再把一些关键处理步骤细化成的流程图;流程图在跨页时，需要在流程线上标注出号码，以便在下一页找出对应关系;让编程人员或读者能够容易读懂流程图。/内容进度算法算法的表示方法自然语言传统流程图N-S流程图伪代码计算机语言各种表示方法的比较结构化程序设计方法文档和注释/结构化程序设计方法C语言是结构化程序设计方法优点：程序便于编写、阅读、修改、维护程序可靠性较好，质量较高主要有两种：自顶向下、逐步细化、模块化设计、结构化编码把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。例如，建筑楼房。优点：程序结构周全、层次分明、容易设计，读者易理解，且修改方便。自下而上、逐步积累先处理细节和小的地方，然后再组织起来形成系统。缺点：很难考虑周全，往往只注意细节，而容易忽略全局，不符合一般人的思路。/应用举例机票预定系统预订机票系统客户信息管理机票查询机票打印/应用举例逐步细化客户信息管理客户信息录入客户查询机票打印得到用户信息打印机票按订单查询按姓名查询姓名ID性别日期始发站终点站/机票查询有航班无航班打印无航班信息有座位无座位退出不交订金交订金等待退票调用机票打印有无退回订金调用机票打印应用举例/算法算法的表示方法自然语言传统流程图N-S流程图伪代码计算机语言各种表示方法的比较结构化程序设计方法本章内容总结