《【2018年整理】C语言程序设计算法》由会员分享，可在线阅读，更多相关《【2018年整理】C语言程序设计算法（45页珍藏版）》请在金锄头文库上搜索。
1、第二章l 本章要点n n算法的概念算法的概念 n n算法的表示算法的表示n n结构化程序设计方法结构化程序设计方法 3一个程序应包括两个方面的内容: 对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm)著名计算机科学家沃思提出一个公式: 数据结构 + 算法 = 程序 数据结构算法程序设计方法语言工具完整的程序设计应该是:42.1 算法的概念1、算法：计算机求解某一问题而采用的具体方法和步骤，就称为“算法”。对同一个问题，可有不同的解题方法和步骤为了有效地进行解题，不仅需要保证 算法正确，还要考虑算法的质量，选择合 适的算法。希望方法简单，运算步骤少。
2、52.1 算法的概念(1)数值运算算法：求数值解，例如求 方程的根、求函数的定积分等。(2)非数值运算算法：包括的面十分广 泛，最常见的是用于事务管理领域， 例如图书检索、人事管理、车辆调度 管理等。2、计算机算法可分为两大类别：6 有穷性：包含有限的操作步骤 确定性：算法中的每一个步骤都应当是确 定的 有零个或多个输入：输入是指在执行算法 时需要从外界取得必要的信息 有一个或多个输出：算法的目的是为了求 解，“解” 就是输出 有效性：算法中的每一个步骤都应当能有 效地执行，并得到确定的结果 。3、算法的特性：72.2 算法的描述方法可以用不同的方法表示算法，常用的有： 自然语言 传统流程图
3、N-S流程图 伪代码 计算机语言81、 用自然语言表示算法自然语言就是人们日常使用的语言，可以 是汉语或英语或其它语言。用自然语言表示 的算法通俗易懂，但文字冗长，容易出现“ 歧义性”。自然语言表示的含义往往不太严 格，要根据上下文才能判断其正确含义，描 述包含分支和循环的算法时也不很方便。因 此，除了那些很简单的问题外，一般不用自然语言描述算法。 92、 用传统的流程图表示算法美国国家标准化协会ANSI(American National Standard Institute)规定了一些 常用的流程图符号：起止框判断框处理框输入/输出框注释框流程线连接点10三种基本结构Bohra和Jacop
4、ini提出了以下三种基本 结构：顺序结构、选择结构、循环结构用这三种基本结构作为表示一个良好算 法的基本单元。11三种基本结构的图示：顺序结构选择结构12循环结构的图示： 当型(While型)循环结构 直到型(Until型)循环 不133、用N-S流程图表示算法1973年美国学者I.Nassi和B.Shneiderman 提出了一种新的流程图形式。在这种流程图 中，完全去掉了带箭头的流程线。全部算法 写在一个矩形框内，在该框内还可以包含其 它的从属于它的框，或者说，由一些基本的 框组成一个大的框。这种流程图又称N-S结 构化流程图 。14N-S流程图用以下的流程图符号：(1)顺序结构 (2)选
5、择结构(3)循环结构15用三种N-S流程图中的基本框，可以组成复杂 的N-S流程图。图中的A框或B框，可以是一个 简单的操作，也可以是三个基本结构之一。 A框可以是一个 选择结构 B框可以是一个 循环结构 164、用伪代码表示算法 概念：伪代码是用介于自然语言和计算机 语言之间的文字和符号来描述算法。 特点：它如同一篇文章一样 ，自上而下地 写下来。每一行(或几行)表示一个基本操 作。它不用图形符号，因此书写方便 、格 式紧凑，也比较好懂，也便于向计算机语 言算法(即程序)过渡。 用处：适用于设计过程中需要反复修改时 的流程描述。17IF x is positive THENprint xEL
6、SEprint -x 也可以用汉字伪代码表示：若 x为正打印 x否则打印 -x 也可以中英文混用，如：IF x 为正print xELSEprint -x例： “打印x的绝对值 ”的算法可以用伪代 码表示为：185、用计算机语言表示算法 概念：用计算机实现算法。计算机是无法 识别流程图和伪代码的。只有用计算机语 言编写的程序才能被计算机执行。因此在 用流程图或伪代码描述出一个算法后，还 要将它转换成计算机语言程序。 特点：用计算机语言表示算法必须严格遵 循所用的语言的语法规则，这是和伪代码 不同的。 用处：要完成一件工作，包括设计算法和 实现算法两个部分。设计算法的目的是为 了实现算法。19
7、强调说明：写出了C程序，仍然只是描述了 算法，并未实现算法。只有运行程 序才是实现算法。应该说，用计算 机语言表示的算法是计算机能够执 行的算法。20例1、从a,b中找出一个较大数赋给max。 (1)自然语言的算法描述如下： 第一步：从键盘输入两个数a和b； 第二步：如果a大于b，则把a的值赋给max，否则，把b的值赋给max； 第三步：输出max的值。21例1、从a,b中找出一个较大数赋给max。 (2) 传统流程图的算法描述如下： 22YN ab?输出 maxmax=bmax=a结束开始输入a,b23例1、从a,b中找出一个较大数赋给max。 (3) N-S流程图的算法描述如下： 24例1
8、、从a,b中找出一个较大数赋给max。 (4) 伪代码的算法描述如下： begininput a and bif aba maxelseb maxprint maxend 25例1、从a,b中找出一个较大数赋给max。 (5) 计算机语言的算法描述如下： #include void main() int a,b,max; scanf(“%d%d“, if(ab)max=a; elsemax=b; printf(“%d“,max);26例2、计算S=,写出其算法 。(1)自然语言的算法描述如下：S1：0 SS2：1 nS3：S+n SS4：n+1 nS5：判断n100? 是，转S3；否则，转S6
9、S6：输出S的值。(2) 传统流程 图的算法描 述如下：28(3) N-S流程图的算法描述如下： 0 S1 nn100?S+n Sn+1 n输出S的值29(4) 伪代码的算法描述如下：begin0 S1 ndo S+n Sn+1 n while n100print Send30(5) 计算机语言的算法描述如下：#include void main() int n,S;S=0; n=1; do S=S+n; n=n+1; while(n=100); printf(“S=%dn“,S); 31N-S图表示算法的优点 比文字描述直观、形象、 易于理解； 比传统流程图紧凑易画。尤其是它废除 了流程线，
10、整个算法结构是由各个基本 结构按顺序组成的，N-S流程图中的上 下顺序就是执行时的顺序。用N-S图表 示的算法都是结构化的算法，因为它不 可能出现流程无规律的跳转，而只能自 上而下地顺序执行。321、三种基本结构Bohra和Jacopini提出了以下三种基本 结构：顺序结构、选择结构、循环结构用这三种基本结构作为表示一个良好算 法的基本单元。2.3 结构化程序设计方法33三种基本结构的图示：顺序结构选择结构34循环结构的图示： 当型(While型)循环结构 直到型(Until型)循环 不352、三种基本结构的共同特点：(1)只有一个入口； (2)只有一个出口；（请注意：一个菱形判断 框有两个出
11、口，而一个选择结构只有一个出 口。不要将菱形框的出口和选择结构的出口 混淆。） (3)结构内的每一部分都有机会被执行到； (4)结构内不存在“死循环”(无终止的循环) 。 36图中没有一条 从入口到出口的 路径通过A框。不正确的流程表示：流程内的死循环37扩展： 只要具有上述四 个特点的都可以 作为基本结构。 可以自己定义基 本结构，并由这 些基本结构组成 结构化程序。此图符合基本结构的特点38这是一个多分 支选择结构，根据 表达式的值决定执 行路线。虚线框内 的结构是一个入口 一个出口，并且有 上述全部的四个特 点。由此构成的算 法结构也是结构化 的算法。可以认为 这是由三种基本结 构所派生
12、出来的。39小结： 由三种基本结构顺序组成的算法结 构，可以解决任何复杂的问题。由 基本结构所构成的算法属于“结构 化”的算法，它不存在无规律的转 向，只在本基本结构内才允许存在 分支和向前或向后的跳转。40小结： 一个结构化的算法是由一些基本结构顺序 组成的。在基本结构之间不存在向前或向 后的跳转，流程的转移只存在于一个基本 结构范围之内(如循环中流程的跳转)；一 个非结构化的算法可以用一个等价的结构 化算法代替，其功能不变 。如果一个算 法不能分解为若干个基本结构，则它必然 不是一个结构化的算法。413、结构化程序设计的优点 一个结构化程序 就是用高级语言表示 的结构化算法。用三种基本结构
13、组成的 程序必然是结构化的程序，这种程序便 于编写、便于阅读、便于修改和维护。 结构化程序设计强调程序设计风格和程 序结构的规范化，提倡清晰的结构。424、结构化程序设计方法的基本思路l把一个复杂问题的求解过程 分阶段 进行，每个阶段处理的问题都控制在 人们容易理解和处理的范围内。 采取以下方法来保证得到结构化的程序： 自顶向下； 逐步细化； 模块化设计； 结构化编码。两种不同的方法： 自顶向下，逐步细化； 自下而上，逐步积累。43用这种方法逐步分解，直到作者认为可以直接将 各小段表达为文字语句为止。这种方法就叫做“自顶 向下，逐步细化”。 44自顶向下，逐步细化方法的优点：考虑周全，结构清晰，层次分明，作 者容易写，读者容易看。如果发现某一部 分中有一段内容不妥，需要修改，只需找 出该部分修改有关段落即可，与其它部分 无关。我们提倡用这种方法设计程序。这 就是用工程的方法设计程序。455、结构化程序设计过程(1) 确定算法(2) 编写程序(3) 上机调试
