搜索
C++高级语言程序设计袁开国北京邮电大学计算机学院第5章算法简介5.1算法的概念5.2算法举例5.3算法的特性5.4算法的表达5.5三种基本算法结构作业编写两个控制台程序，分别实现例5.1和5.2的功能程序＝数据结构＋算法•一个程序包括两方面内容：⑴数据描述：指定程序中数据的类型和数据的组织形式，即数据结构。⑵操作描述：数据的操作方法和步骤，即算法。•操作的目的是用算法对数据进行加工处理，以得到正确的结果，因此，在编程解决实际问题时，必须认真设计数据结构和算法。•著名计算机科学家NikiklausWirth曾提出：程序＝数据结构＋算法•数据是程序的核心，算法是程序的灵魂。5.1算法的概念•算法是解决某个问题或处理某件事的方法和步骤。例如人们计时的方法就五花八门。•对于同一问题的求解，往往有多种不同的算法。•本书仅限于讨论用计算机解决问题的基本算法。•按所处理的数据类型来分，计算机算法分为两类：数值算法：如求超越方程的根、定积分、解微分方程等；非数值算法：如排序、查找等。•算法评价：正确性、运行效率及占用资源等。5.2算法举例例5.1求两个自然数的最大公约数的算法。s1．输入两个自然数M、N；s2．求M除以N的余数→R；s3．使M←N，即用N代换M；s4．使N←R，即用R代换N；s5．若R≠0，则重复执行s2、s3、s4，否则转s6；s6．输出M，M即为M和N的最大公约数。例5.2在N个字符串中，查找有无指定的字符串。s1．输入字符串的个数N和要查找的字符串S；s2．使I←1，I用于计数；s3．从字符串集合中读取一个字符串x；s4．若x=S，输出“找到S”，算法结束，否则转s5；s5．使I←I+1，计数器计数；s6．若I≤N，则重复执行s3、s4、s5，否则转s7；s7．输出“找不到S”，算法结束。5.3算法的特性•确定性：指算法的每个步骤都应确切无误，无歧义。•可行性：指算法的每个步骤都是计算机可实现、能有效执行并可得到确定的结果。•有穷性：一个算法包含的步骤应是有限的，并在一个合理的时间限度内执行完毕。•输入性：执行算法时，计算机可从外部取得数据。一个算法可有多个输入，但也可没有输入，因计算机可自动产生一些必须的数据。•输出性：一个算法应有1个或多个输出。计算机是人们“解题”的工具，算法应能输出计算结果，否则该算法将毫无意义。5.4算法的表达•算法表示方式主要有：自然语言(如例5.1和例5.2所示)某种代码符号来描述(如伪代码)特定的图形来描述(流程图和N-S图)编程语言(如汇编语言、高级语言)•图形描述方法形象直观，易于理解，应用广泛。•较常用的描述算法的图形是流程框图，简称流程图。流程图•流程图使用的图形符号如图2-1所示，是ANSI标准，为各国程序员普遍采用。•菱形框用于条件判断，若条件成立则转向一个出口，否则转向另一个出口。•连接框用于将画在不同地方的流程线连接起来，避免流程线的交叉或过长。•注释框不是流程图的必要部分，不反映流程和操作，仅对流程图中某些框的操作做补充说明。流程图举例5.5三种基本算法结构•顺序结构、选择结构、循环结构三种基本结构的特点•单入口和单出口•结构中的每个部分都有可能被执行•结构内不应出现永不终止的循环结构化程序设计•理论基础：解决任何问题的算法都可表示为顺序结构、选择结构和循环结构的组合。•结构化程序设计：用三种基本算法结构设计程序。•结构化程序设计的优点：结构清晰，易于理解，易于验证其正确性，也易于查错和排错。