第2章程序的灵魂—算法讲述.ppt

南理工紫金学院 第二章 程序的灵魂 ——算法 主要内容 2.1 算法的概念 2.3 算法的特性 2.4 怎样表示一个算法 §2.1 算法的概念 算法：为解决一个问题而采取的方法和步骤 对同一个问题，可有不同的解题方法和步骤 算法的分类： ①数值运算算法 求数值解。如求方程的根、求函数的定积分等。 ②非数值运算算法 包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理等。 §2.3 算法的特性 有穷性： 确定性： 有零个或多个输入： 有一个或多个输出： 有效性： §2.4 算法的表示 常用的算法表示方法有： 自然语言 传统流程图 N-S结构化流程图 伪代码 一、用自然语言表示算法 易懂，但文字冗长，易有歧义，不严格 除很简单的问题外，一般不用自然语言描述算法 二、用流程图表示算法 ANSI(美国国家标准化协会)规定的流程图符号： 三种基本结构 三种基本结构：顺序结构、选择结构、循环结构 三种基本结构的流程图图示： 扩展： 只要具有上述四个特点的都可以作为基本结构。 三、用N-S流程图表示算法 特点：完全去掉了流程线。全部算法写在一个矩形框内，在该框内还可包含其它从属于它的框。 N-S流程图用以下的流程图符号： 五、用计算机语言表示算法 四、用伪代码表示算法 伪代码：介于自然语言和计算机语言之间的文字和符号。 特点：它不用图形符号，因此书写方便、格式紧凑、易懂、便于向计算机语言算法(即程序)过渡。 * 美国国家标准学会(American National Standards Institute) 要求掌握：算法的概念、算法的表示 著名计算机科学家沃思 (Wirth)提出一个公式:  数据结构 + 算法 = 程序 描述数据的类型、组织形式 描述对数据的操作步骤 数据结构＋算法＋程序设计方法＋语言工具 完整的程序设计应该是: 方法1：1+2，+3，+4，一直加到100 方法2：100+(1+99)+(2+98)+…+(49 +51)+50 = 50×100 +50 例： 求 包含有限的操作步骤。 算法中的每一个步骤都应当是确定的。 输入是指在执行算法时需要 从外界取得必要的信息。 “解” 就是输出。 算法中的每一个步骤都应当能有效地执 行，并得到确定的结果。 起止框 判断框 处理框 输入/输出框 注释框 流程线 连接点 说明：框内可以用自然语言或伪代码描述。 (1)顺序结构 (2)选择结构 (3)循环结构 (a)当型(While型)循环 (b)直到型(Until型)循环 循环体 先判断后执行 先执行后判断 三种基本结构的共同特点： (1)只有一个入口。 (2)只有一个出口。 (3)结构内的每一部分都有机会被执行到。 (4)结构内不存在“死循环”(无终止的循环)。 图中没有一条从入口 到出口的路径通过A框 例如： 死循环 X X √ √ 传统流程图的流程可以是： 缺点：难以阅读、修改，降低了可靠性和可维护性 解决办法：限制流程线的滥用 优点：灵活、自由、直观，可表示任何算法。 选择结构 循环结构 优点：直观、形象、 易于理解、紧凑易画。 顺序结构 目的：实现算法。只有用计算机语言编写的程序才能被计算机执行。 特点：必须严格遵循所用的语言的语法规则，这是和伪代码不同的。 例2.2 有50个学生，要求将他们之中成绩在80分以上者打印出来。设n表示学号， ni代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩。 自然语言描述： S1：1 → i S2：输入ni和gi S3：i+1 → i S4：如果i≤50，返回S2继续执行。 S5：1 → i S6：如果gi≥80，则打印ni和gi ，否则不打印。 S7：i+1 → i S8：如果i≤50，返回S6继续执行；否则算法结束。 流程图描述： N-S图描述： 输 入 信 息 * 美国国家标准学会(American National Standards Institute) 清华大学《计算机文化基础》电子教案 2003年3月 * 页