C语言教学之算法省公共课一等奖全国赛课获奖课件.pptx

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