C语言教学课件之第2章算法.ppt

知识改变命运 学习成就未来,2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法,第2章 程序的灵魂算法,本章大纲,程序的灵魂算法（1学时） 教学内容： 算法的概念 算法的特性； 算法的常用表示方法：流程图 基本要求： 理解算法的概念及特性； 了解怎样设计算法； 掌握算法的表示方法； 熟悉结构化程序设计方法。 重点：算法的常用表示方法 难点：算法的常用表示方法,2.1 算法的概念,广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。,算法成熟，已汇编成册,种类繁多，要求各异，难规范化,非数值运算算法,数值运算算法,2.2 简单算法举例,步骤1： 先求12，得到结果2。 步骤2： 将步骤1得到的乘积2再乘以3，得到结果6。 步骤3： 将6再乘以4，得24。 步骤4： 将24再乘以5，得120。,如果想求121000， 难道要写999个步骤吗？,例2.1 求12345。,理解,设两个变量，一个变量p代表被乘数，一个变量i代表乘数，乘积放在被乘数变量p中。将算法改写如下： S1： 使p=1 S2： 使i=2 S3： 使pi，乘积仍放在变量p中，可表示为pi=p S4： 使i的值加1，即i+1 = i S5： 如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。,循环算法解决 这类问题最拿手了！,如果求1357911 怎么办呢？自己想想啦！,2.3 算法的特性,1.有穷性,1.包含有限的操作步骤 2.指“在合理的范围之内” 3. “合理限度” ，由人们的常识和需要而定,算法中的每一个步骤都应当是确定的,2.确定性,理解,3.有零个或多个输入,所谓输入是指在执行算法时需要从外界取得必要的信息。,每个步骤都应当能有效地执行，并得到确定的结果。,4. 有一个或多个输出,5. 有效性,没有输出的算法是没有意义的。,图2.2,3个输入,1个输出,算法,求3个数中的最大的数,a,b,c,3个数中的最大的数,补充内容：算法的评价,1.时间复杂度,2.空间复杂度,度量算法执行的时间长短,度量算法所需存储空间的大小,了解,2.4 怎样表示一个算法,自然语言 传统流程图 结构化流程图 N-S流程图 伪代码 PAD图 计算机语言,2.4.1 用自然语言表示算法,通俗易懂,1.文字冗长，尤其是描述分支和循环的算法，不方便 2.容易出现“歧义性”。,张先生对李先生说他的孩子考上了大学。,到底谁考上了？,张先生的孩子考上了？,李先生的孩子考上了？,了解,2.4.2 用流程图表示算法,用一些图框表示各种操作，直观形象，易于理解。规定了一些常用的流程图符号(见图2.3)。,起止框,输入/输出框,判断框,掌握,图 2.3,处理框,流程线,连接点,注释框,例2.6 将例2.1求5!的算法用流程图表示。,2.4.3 三种基本结构和改进的流程图,1. 传统流程图的弊端,1.对流程线的使用没有严格限制 2.使流程图变得毫无规律。 3.算法难以阅读，也难以修改 4.算法的可靠性和可维护性难以保证,(1) 顺序结构，如图2.14所示，虚线框内是一个顺序结构。,2. 三种基本结构,1966年，Bohra和Jacopini提出的,图2.14,(2) 选择结构（选取结构，分支结构）如图2.15所示。,无论 p 条件是否成立，只能执行A框或B框之一,在执行完A或B之后，都经过b点，然后脱离本选择结构,A或B两个框中可以有一个是空的,图2.15,图2.16,(3) 循环结构：,我也叫重复结构,1.是当给定的条件p1成立时，执行A框操作 2.执行完A后，再判断条件p1是否成立，如果仍然成立，再执行A框 3.如此反复执行A框，直到某一次p1条件不成立为止，此时不执行A框， 4.从b点脱离循环结构, 当型(While型)循环结构,对应while语句,1.它的功能是先执行A框，然后判断给定的p2条件是否成立2.如果p2条件不成立，则再执行A，然后再对p2条件作判断，如果p2条件仍然不成立，又执行A 3.如此反复执行A，直到给定的p2条件成立为止，此时不再执行A 4.从b点脱离本循环结构。,直到型(Until型)循环,C语言中没有until语句,图2.18当型循环,风把门吹开了。,门被风吹开了。,图2.19直到型循环,意思相同，可以互相转换,(1) 只有一个入口。 (2) 只有一个出口。 (3) 结构内的每一部分都有机会被执行到。 (4) 结构内不存在“死循环”,菱形判断框有两个出口。不要混淆哦！,看清楚哦，是有机会，不是一定！,三种基本结构的特点：,图2.20 没有通路,图2.21 死循环,2.4.4 用N-S流程图表示算法,1.1973年美国学者I.Nassi和B.Shneiderman提出 2.去掉了带箭头的流程线 3.全部算法写在一个矩形框内 4.自上而下执行 5.适于结构化程序设计 6.尤其适合表达复杂的循环结构,(2) 选择结构,(1) 顺序结构,图2.24,图2.25,N-S流程图用以下的流程图符号：,像不像一个 方方正正的盒子? 所以也叫盒图!,图2.26当型循环,(3) 循环结构,图2.27直到型循环,图2.28,(3) 示例：,2.4.5 用伪代码表示算法,1.直观易懂 2.画起来比较费事 3.流程图适宜表示一 个算法,1.伪代码 (pseudo code)是用介于自然语言和计算机语言之间的文字和符号来描述算法。 2.不用图形符号，书写方便 、格式紧凑 3.适于设计算法 4.比较好懂，便于向计算机语言算法(即程序)过渡,IF x is positive THEN print x ELSE print x,伪意思是假的，不真实的,如：伪军，伪君子,伪代码不能运行,IF x 为正 print x ELSE print x,例如， “打印x的绝对值”的算法可以用伪代码表示如下：,若 x为正 打印 x否则 打印 x,IF x is positive THEN print x ELSE print x,2.4.6 用计算机语言表示算法,不再是表示算法,而是用计算机语言来实现算法,计算机是无法识别流程图和伪代码的。,例2.20 将例2.16表示的算法（求5!）用C语言表示。,main( ) int i，t; t=1; i=2; while(i=5) t=t*i; i=i+1; printf(“%d“，t); ,补充内容：PAD图,1.PAD （Problem Analysis Diagram）即问题分析图 2.1973年由日本日立公司发明，得到一定程度的推广 3.它用二维数形结构的图表示程序的控制流，将这种图转换为程序代码比较容易。,优点 ： 1.程序结构十分清晰 2.易读、易懂、易记。程序自上而下，从左到右顺序执行 3.很容易将PAD图转换成高级程序语言源程序，由软件工具自动完成提高可靠性和生产率。 4.既可用于表示程序逻辑，也可用于描述数据结构,了解,PAD图的基本符号,2.5 结构化程序设计方法,自顶向下； 逐步细化； 模块化设计； 结构化编码,1.模块化思想：“分而治之” 2.模块划分的原则：聚合度高，耦合