《C语言第2章(谭浩强).ppt》由会员分享，可在线阅读，更多相关《C语言第2章(谭浩强).ppt（42页珍藏版）》请在三一办公上搜索。
1、1,第2章 程序的灵魂算法,打个比方，厨师做菜肴，需要有菜谱。菜谱上一般应包括：（）配料（数据）（）操作步骤（算法）面对同一些原料可以加工出不同风味的菜肴。数据是操作对象，对操作的描述既是操作步骤，操作的目的是对数据进行加工处理得到期望的结果。本课程虽然不是专门讲算法的，但不会算法就达不到我们的目的用语言进行程序设计。,2,著名计算机科学家沃思提出一个公式：数据结构算法程序实际上，一个程序还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示。程序算法数据结构程序设计方法语言以上四个方面是一名程序设计员所应具备的知识。在这四个方面中，算法是灵魂，是解决“做什么
2、”和“怎么做”的问题。数据结构是加工对象，语言是工具，编程需要采用合适的方法。,3,2.1 算法的概念做任何事情都有一定的步骤，这些步骤都是有一定的顺序。如：起床上学，用电脑画画，弹奏乐曲。不要以为只有“计算”的问题才有算法的。什么叫做算法？广义：为解决一个问题而采用的方法和步骤就称为“算法”。例如：求 1+2+3+4+100 可先算1+2、再加3、再加4直到加上100；也可采用 100+（1+99）+（2+98）+（49+51）+50本书所关心的算法只限于计算机算法。,4,计算机算法可分两大类:（1）数值运算算法（2）非数值运算算法数值运算：求数值解、如求方程根、函数 定积分等。非数值运算：
3、事物管理、图书检索、人事管理、行车调度管理等。由于数值运算有现成的模型，可以应用数值分析方法，算法比较成熟。例如有些计算机系统提供“数学程序库”，可以直接调用。而非数值运算的种类繁多，不可能罗列所有的算法，需要设计解决特定的问题。目前计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。,5,2.2 简单算法举例例2.1 求1*2*3*4*5设两个量：一个被乘数p一个乘数nS1：p=1/*S1 是步骤一*/S2：n=2S3：p*n=pS4：n+1=nS5：若n不大于5，重复执行S3、S4、S5（若求1*3*5*7*9*11 呢？）,6,例2.2 有50个学生，将成绩在80分以上的学号和成
4、绩打印出来。说明：n:学号，ni:第i个学生学号，g:成绩，gi:第i个学生成绩步骤如下：S1：1=iS2：若gi80,则输出ni和 gi，否则不输出。S3：i+1=iS4：若i小于等于50,则返回 S2继续执行；否则算法结束。,7,例2.3判定2000-2005年中的每一年是否闰年，将结果输出。说明：闰年的条件（1）能被4整除，但不能被100整除的都是闰年（2）能被100整除，又能被400整除的是闰年。y:年份步骤如下：S1：y=2000S2：若y不能被4整除，则输出y“不是闰年”。转到s6S3：若y能被4整除，不能被100整除，则输出y“是闰年”。转到s6S4：若y能被100整除，又能被4
5、00整除，输出y“是闰年”。转到s6S5：输出y“不是闰年”。S6：y=y+1S7:当y=2500,转s2继续执行，否则算法结束。,8,例2.4求1-1/2+1/3-1/4+1/99-1/100说明：sum:累加项；deno:分母；sign:符号；term:某一项步骤如下：S1:sign=1S2:sum=1S3:deno=2S4:sign=(-1)*signS5:term=sign*(1/deno)S6:sum=sum+termS7:deno=deno+1S8:若deno=100返回s4；否则算法结束。,9,2.3 算法的特性一个算法具有以下特性：有穷性包含有限的操作步骤，不能是无限的；在合理
6、 的范围之内。如：例2.4 条件改为deno0确定性每一步骤是确定的，而不应是含糊的，模棱两可的。有零个或多个输入输入是从外界取得必要的信息。有一个或多个输出“解”就是输出，没有输出的算法是无意义的。有效性每一步骤都应是有效的执行，并有确定的结果。,10,2.4 怎样表示一个算法表示方法：1、自然语言2、传统流程图 3、NS流程图4、结构化流程图5、伪代码、PAD图,11,2.4.1 用自然语言表示算法 用自然语言表示通俗易懂，但容易出现“歧异性”。2.4.2 用传统流程图表示算法 直观形象，易于理解。成为世界各国程序工作者普遍采用。下面给出传统流程图的说明：,12,起止框,输入/输出框,处理
7、框,有一个入口 一个出口,判断框,有一个入口，两个出口,13,流程线,注释框,连接点,14,例2.6 求5！的算法用流程图表示,15,例2.7 将50名学生中成绩在80分以上的学号和成绩输出,16,例2.8 判断20002500年中的每一年是否为闰年。是闰年的条件：1.能被整除，但不能被整100除。2.能被100整除又能被400整除。,17,例.9求 1-1/2+1/3-1/4+1/99-1/100sign符号sum 累加和deno分母term项 deno100算法结束,18,例.10 对一个大于或等于的正整数，判断它是否为素数。所谓素数，是指除了被和该数本身之外，不能再被其他整数整除的数。,
8、19,2.4.三种基本结构和改进的流程图 1.传统流程图的弊端 传统的流程图用流程线指出各框的执行顺序，对流程线可以随意地转来转去，无规律。如下图，称为BS型。,20,2.三种基本结构：1966年提出,（1）顺序结构:平铺直叙的向下顺序执行,即执行A操作后,执行B操作。,（2）选择结构:或称选取、分支结构，根据给定条件决定执行A操作和执行B操作。,21,（3）循环结构:又称重复结构，即反复执行某一部分的操作。有两类循环结构：A:当型循环(while)B：直到型循环（until）,22,举例：输出5个数：1，2，3，4，5,23,结论：,3种基本结构的共同特点：（1）只有一个入口；如上图的a点（
9、2）只有一个出口；如上图的b点。区分：判断框和选择结构的出口（3）结构内的每一部分都有机会执行到；对每一个框都有一个入口和出口 如P26图2-20（4）结构内不存在死循环。如P26图2-21 已经证明，以上三种基本结构顺序组成的算法，可以解决任何复杂的问题。基本结构并不仅限于这三种，只要符合这4个条件都可以作为基本结构。如P26图2-22图2-23,24,2.4.用NS流程图表示算法既然用基本结构的顺序组合可以表示任何复杂的算法，那么基本结构的流程线就属多余了。所以 1973年由美国学者提出了一种新的流程图形式，在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，这种流程图称为
10、 NS 流程图。（Nassi 和 Shneiderman 两位美国学者英文姓名的第一个字母）,25,请观看以下流程符号,顺序结构 循环结构（当型）A 当 Pi 成立 B A 选择结构 循环结构（直到型）P A成立 不成立 A B 直到 Pi 成立,26,解方程：ax2+bx+c=0,27,求请转换成直到型？,28,例2.12 将50名学生中成绩高于80分的学号和成绩输出,29,例2.12 将50名学生中成绩高于80分的学号和成绩输出（增加了输入）,30,例2.13 判断闰年,31,例2.14 求1-1/2+1/3-1/4+1/99-1/100,32,例：输入三个数比较大小，输出最大值,33,练
11、习：用N-S图表示算法,要求：输入一个数,求的值 有方程组y=1(x0)y=-1(x0)y=0(x=0),34,35,例：2.15 用N-S图表示判别素数的算法，结果P29图2-35,36,结论：,一个结构化的算法是由一些基本结构顺序组成的；在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构内；一个非结构化的算法可以用一个等价的结构化算法代替；如果一个算法不能分解成若干个基本结构，则它必然不是一个结构化的算法。,37,2.4.用伪代码表示算法,伪代码是介于自然语言和计算机语言之间的文字和符号来描述算法。它不用图形符号，书写方便、格式紧凑、也比较好懂，便于向计算机语言算法（即程
12、序）过度。例如：若为正为正打印否则打印,38,伪代码书写格式比较自由，可以随手写下容易表达出设计者的思想。同时，用伪代码写的算法很容易修改，如加一行、删除一行等，而这却是用流程图表示算法时所不便处理的。但是，用伪代码不容易写出结构化的算法。例如上面几个例子都是结构化的算法。要用伪代码写算法就不如流程图直观，可能会出现逻辑上的错误（例如循环或选择结构的范围搞错等）。以上介绍的表示算法的几种方法，在程序设计中可根据需要和习惯选用。考虑到国内初学者的情况，本课程采用流程图表示算法。,39,2.4.用计算机语言表示算法,要完成一项工程，包括设计算法和实现算法两个部分。一个菜谱是一个算法，厨师炒菜就是在
13、实现这个算法。设计算法的目的是为了实现算法。因此，不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。以上我们只是描述算法，即用不同的形式表示操作的步骤。而要得到运算结果，就必须实现算法。我们实现算法的任务是用计算机解题，也就是用计算机实现算法。计算机是无法识别流程图和伪代码的，只有用计算机语言编写的程序才能被计算机执行（通过编译）。,40,2.5 结构化程序设计方法,前面介绍了顺序结构、选择结构、循环结构这三种基本结构。一个结构化程序就是用高级语言表示结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、阅读、修改和维护。结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。怎样才能得到一个结构化的程序呢？结构化程序设计方法的基本思路是：把一个复杂问题的求解过程分阶段进行，把每个阶段处理的问题都控制在人们容易理解和处理的范围内。,41,采用以下方法可得到结构化程序,（1）自顶向下（2）逐步细化（3）模块化设计（4）结构化编码,42,作业,P36习题2.4（1）（3）习题2.5（1）（3）,
