C语言 第二讲-程序的灵魂—算法.pptVIP

American National Standards Institute（ANSI——美国国家标准学会） 是由公司、政府和其他成员组成的自愿组织。它们协商与标准有关的活动，审议美国国家标准，并努力提高美国在国际标准化组织中的地位。此外，ANSI使有关通信和网络方面的国际标准和美国标准得到发展。ANSI是IEC和ISO的成员之一。 * C 程序设计 第2章 程序的灵魂-算法 主要内容 算法的概念 简单算法举例 算法的特性 怎样表示一个算法 结构化程序设计方法 1 算法的概念 算法是指解决一个具体问题的意义明确的步骤的集合，是有限的。 概括的说，算法是指解决问题方案的准确而完整的描述。 对同一个问题可以有不同的解题方法和步骤，也就是有不同的算法。 算法有优劣，一般而言，应当选择简单的、运算步骤少的，既运算快 内存开销小的算法。 什么是算法？ 计算机科学家沃思（N.Wirth）认为， 数据结构 + 算法=程序 由此可以看出，程序和算法密切相关。 简单算法举例 简单算法举例 简单算法举例 简单算法举例 简单算法举例 2 算法的特性 确定性：算法中的每一步骤都应当是确定的 有效性：算法的每个步骤都应当有效执行，并能得到 确定结果。 有零个或者多个输入：可以没有输入，也可以有输入 有一个或者多个输出：算法必须得到结果 有穷性：一个算法应当包含有限的步骤，不能是无限 的，事实上“有穷性”往往是指“在合理的范围之内”的 有限步骤。 3 怎样表示一个算法？ 表示一个算法的方式有多种，常用的算法表示方法： 自然语言 流程图表示法 N-S流程图表示法 伪码 主要介绍流程图表示法和N-S流程图表示法 一、自然语言表示法 自然语言就是人们常用的语言，可以是汉语、英语或其他语言。 优点：用自然语言表示通俗易懂； 缺点：但文字冗长，容易出现“歧义”性。 用自然语言描述包含分和循环的算法，很不方便。 一般不使用自然语言描述算法。 3 怎样表示一个算法？ 一、自然语言表示法 3 怎样表示一个算法？ 二、流程图表示算法 3 怎样表示一个算法？ 在程序设计过程中，一般不可能在一开始就用某种程 序设计语言编制计算机程序，而是先用某种简单、直观、 灵活的描述工具来描述处理问题的流程。 当方案确定以后，再将这样的流程转换成计算机程序， 这种转换往往是机械的，已经不涉及功能的重新设计或控 制流程的变化，而只需考虑程序设计语言规定的语法要求 以及一些细节问题。 3 怎样表示一个算法？ 流程图：用一些约定的几何图形来描述算法。用某种图框表示某种操作，用箭头表示算法流程。 流程图（的符号及意义）美国标准化协会ANSI规定了一些常用的流程图符号，为世界各地普遍采用。 起止框 输入输出框 判断框 处理框 流程线 x≥0 打印x 打印x+3 Y N 二、流程图表示算法 优点：直观形象 缺点：由于对流程线的使用没有严格限制，使用者可以随意地转来转去，使得算法难于阅读、理解及修改。 这种局面是不可避免的吗？ 人们经过研究发现，任何复杂问题的算法都可由3种基本结构顺序组合而成，而且非顺序转向仅出现在每个基本结构内部，不会出现在基本结构之间。 这种算法称为结构化算法。 顺序结构 分支结构 循环结构 顺 序 结 构 开始 结束 分支结构 循环结构 循 环 结 构 分支结构 顺序结构 二、流程图表示法 基本思路：把一个复杂问题的求解过程分阶段来进行，每个阶段处理的问题都控制在人们容易理解与处理的范围内。 具体方法：自顶向下，逐步细化。 优点：便于修改、易于验证正确性 结构化程序设计 结构化程序设计 1966年，Bohra和Jacopini提出三种基本结构，用这三种基本结构作为表示一个良好算法的基本单元。 三种基本结构是： （1）顺序结构 按指令的顺序依次执行 （2）选择结构 根据判别条件有选择地改变 （3）循环结构 有条件的重复地执行某个程序 A B a b 虚线框内是一个顺序结构。从a点进入结构，在执行完A框指定的操作后，接着就执行B框指定的操作，经b点离开结构。因此，仅有一个入口，也仅有一个出口。 1、顺序结构 p A B a b 成立 不成立 虚线框内是一个选择结构。从a点进入结构，根据给定的条件p是否成立而执行A框或B框指定的操作，经b点离开结构。因此，仅有一个入口,也仅有一个出口。而且，结构内的每一部分都有机会被执行到。 分支结构 2、分支结构 思考：求a、b两个数中的最大值。 3、循环结构