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