程序设计与算法(问题求解).ppt

第2章 程序设计与算法（问题求解 ） 1 本章主要内容 2.1 程序的基本组成：输入、处理与输出 2.2 算法与编程工具 2 2.1 程序的基本组成：输入、处理与输出 1. 计算机解题示例 Input(输入)Processing(处理)Output(输出)Processing(处理) 图2-1 3 2. 程序设计的一般步骤 分析：问题定义 设计：计划解题 选择与创建界面：选择与确定界面对象 编码：用程序设计语言描述对象 测试与调试：查找并排除程序中的任何错误 完成文档：整理和组织描述程序的所有资料 4 2.2 算法与编程工具 设计程序前，根据实际问题的特点和需求，同 时考虑到计算机的工作特性，确定解决该问题所 需要的方法和步骤称为“算法设计”。 1. 算法的概念 2. 算法示例 3. 算法的特征 4. 算法的描述 5. 基本算法结构 5 1. 算法的概念 广义而言，算法就是解决某个问题或处理某件事 的方法和步骤。 狭义而言，算法是专指用计算机解决某一问题的 方法和步骤。 计算机算法可以分为两大类：一类是数值计算算 法；另一类是非数值计算算法。 研究解决各种特定类型问题的算法已成为一个称 为“计算方法”的专门学科。 对于同一问题的求解，往往可以设计出多种不同 的算法。一般而言，评价一个算法的好坏优劣， 主要看算法是否正确、运行的效率及占用系统资 源的多少等。 6 2. 算法示例 算法1 算法2 7 算法1：求两个自然数的最大公约数的算法 S1.输入两个自然数M、N； S2.求M除以N的余数R； S3.使M=N，即用N代换M； S4.使N=R，即用R代换N； S5.若R0，则重复执行S2、S3、S4（循环），否则转S6 ； S6.输出M，M即为M和N的最大公约数。 本算法是由古希腊数学家欧几里德提出的，所以 又称为“欧几里德算法”。算法中的S1、S2、 S3叫作算法步骤，每个算法步骤明确规定所要 进行的操作及处理对象的特性（M、N为自然数 ）。 欧几里德算法是求两个自然数最大公约数的经典 算法。 8 算法2 在N个字符数据集合中， 查找有无特定的字符串存在 S1.输入字符数据的个数N和要查找的数据S； S2.使I=1，I用于计数； S3.从字符数据集合中读取一个数据X； S4.若X=S，输出“找到S”的信息，算法结束，否则 转S5； S5.使I=I+1，计数器计数； S6.若IN；则重复执行S3、S4、S5（循环）；否 则转S7； S7.输出“找不到S”信息，算法结束。 本算法也称为“顺序查找算法”，也是在处理非数 值信息时最常用的一种算法。 9 3. 算法的特征 从上述算法的示例可以看出，作为算法，应具备 以下特征： 1）确定性-算法的每个步骤都应确切无误，没有歧 义性。 2）可行性-算法的每个步骤都必须是计算机能够有 效执行、可以实现的，并可得到确定的结果。 3）有穷性-一个算法包含的步骤必须是有限的，并 在一个合理的时间限度内可以执行完毕。 4）输入性-执行算法时可以有多个输入，但也可以 没有输入（0个输入）。 5）输出性-一个算法必须有1个或多个输出。 10 4. 算法的描述 算法可以采用多种方式来表示。比如使用人们的 自然语言像英语、汉语等来描述；使用某种代码 符号来描述或者使用特定的图形来描述等等。由 于图形的描述方法既形象，又直观，所以得到广 泛的应用。 用于描述算法的图形使用较多的是所谓的流程框 图，简称流程图。它是使用规定的图形符号来描 述算法的。流程图使用的图形符号见表2-1。 图2-2和图2-3分别是上一节两个算法示例的流程 图。图框内的文字用于说明具体的操作内容。显 而易见，使用流程图比使用自然语言描述算法优 越地多。 11 图形符号名称代表的操作 输入/输出数据的输入与输出 处理各种形式的数据处理 判断 判断选择，根据条件满足与否 选择不同路径 起止流程的起点与终点 特定过程一个定义过的过程 流程线连接各个图框，表示执行顺序 连接点表示与流程图其他部分相连接 表2-1 12 图2-2图2-3 13 5. 基本算法结构 “结构化程序设计方法”的核心是规定了算法的三 种基本结构：顺序结构、分支结构和循环结构。 三种基本结