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