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