C语言课件第02章.ppt

《C语言课件第02章.ppt》由会员分享，可在线阅读，更多相关《C语言课件第02章.ppt（34页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第2章 程序的灵魂-算法2.0 引言2.1 算法的概念2.2 简单算法举例2.3 算法的特性2.4 怎样表示一个算法2.5 结构化程序设计方法Return1程序应包含2方面的内容:v对数据的描述:程序中指定数据的类型和数据的组织形式-数据结构v对操作的描述:操作的步骤,即算法 数据是操作的对象,操作的目的是对数据加工处理以得到期望的结果.以厨师需菜谱打比方.沃思提出了一个公式:数据结构+算法=程序除了上面2个主要方面还有其他因素,程序可表示为:程序=算法+数据结构+程序设计方法+语言工具和环境 4方面中:算法是灵魂,数据结构是加工对象,语言是工具,编程要采用合适的方法.本书不单单讲算法或是语言

2、规则,而是结合这4方面,如何编写C程序Return2.0 引言22.1 算法的概念算法:解决一个问题而采取的方法和步骤v做任何事情都有一定的步骤.如开会,购物,考大学,按一定顺序进行，缺一不可，日常生活中人们意识不到每件事都需事先设计出“行动步骤”。v并不是只有“计算”的问题才有算法.例如:太极拳的拳谱,乐谱v不仅要保证算法正确,还要考虑的是算法的质量.例如求解本书只考虑计算机算法.v数值算法:目的是求数值解.如求方程的根,求积分等v非数值算法:包括的面非常广泛.最常见的用在事物管理领域Return32.2 简单算法举例案例2.1求 5!。v方法1：步骤1：先求12，得结果2步骤2：将步骤1的

3、结果乘以3，得结果6步骤3：6再乘以4，得24步骤4：24再乘以5，得最后的结果120。分析：算法正确，但太烦琐。若要求1000!，要写多少步骤呢？且不方便的是每次都直接使用上一步骤的结果v方法2：设变量p为被乘数(乘积)，i为乘数，改写如下S1：使p=1S2：使i=2S3：p ipS4：i+1 iS5：若i不大于5，则回到S3；否则算法结束。最后的p就是5！v分析：若求1 3 5 7 9 11，只做很少的改动即可。S2：i=3 S4：i+2 i S5：i11，回到S3，否则结束。说明方法2简练且通用。若条件改成i0;i+)。实际上，“有穷性”是指在一个“合理的范围内”。若让计算机执行一个历时

4、几千年才结束的算法，虽然是有穷的，但超过了合理的限度。“合理限度”无严格标准，根据常识和需要而定确定性v算法中的每一步骤的含义都应当是确定唯一的，不应当产生“歧义性”。如“手举过头顶”“n被一个整数除，得余数r。”有零个或多个输入v输入是指在执行算法时需要从外界取得必要的信息。例如，算法：判断一个数是否是素数，求2个整数的最大公约数，求n个数的方差等。当然也可以没有输入。有一个或多个输出v算法的目的就是求解，解就是输出。不一定是计算机打印输出。没有输出的算法没有意义有效性v算法的每一步骤应当有效的执行，得到确定的结果。如一个除数为0表达式是不能有效执行的。算法如同“黑箱子”，从外部特性了解算法

5、的作用，就可使用算法。但自己要学会设计算法 Return102.4 怎样表示算法2.4.1 用自然语言表示算法2.4.2 用传统流程图表示算法2.4.3 三种基本结构和改进的流程图2.4.4 用N-S流程图表示算法2.4.5 用伪代码表示算法2.4.6 用计算机语言表示算法Return112.4.1 用自然语言表示算法2.2节 算法举例中讲的算法就是用自然语言表示的。自然语言就是日常使用的语言，如汉语，英语等。v通俗易懂，但文字冗长，易出现“歧义”“张先生对李先生说他的孩子考上了大学”，他指的谁？v描述包含分支和循环的算法，不是很方便适用描述简单的问题Return122.4.2 用流程图表示算

6、法用图形表示算法，直观形象，易理解。美国国家标准化协会ANSI（american national standard institute）规定了一些常用的流程图符号：起止框输入输出框判断框处理框连接点流程线注释框x0打印x打印-x图 2.4 判断框有一入两出，根据给定的条件判断执行的操作图2.5 连接点：把不同地方的流程线连接起来。画不下才分开来，可避免流程线交叉或过长，使流程图清晰。注释框：不是必要的部分，作些必要的说明以帮助阅读和理解13案例2.6开始1t2ititi+1ii5打印t结束YN图 2.7案例2.1 求5！的算法的流程图流程图一般包括以下几个部分:表示相应操作的框;带箭头的流程

7、线(反映各框的执行次序);框内外的文字说明.14案例2.71igi80打印ni，gii+1ii50结束YNNY图2.9 案例2.2的流程图表示:输入50个学生的学号和成绩且将80分以上的打印出来开始1ii+1ii50输入ni，giYNni,gi为第i个学生的学号和成绩15案例2.8 判断闰年算法的流程图表示y+1yy2500结束YN开始2000yy不能被4整除y不能被100整除y不能被400整除打印y“是闰年”打印y“不是闰年”打印y“是闰年”打印y“不是闰年”YNYNYN16案例2.9 求 (案例2.4)的算法的流程图表示 开始1sum2deno1sign(-1)signsigndeno+1

8、denodeno100结束YNsign(1/deno)termsum+termsum图 2.1117案例2.10 判断素数的算法(案例2.5)的流程图表示i+1ir=0?结束Y开始输入n打印n“不是素数”N2in/i的余数r打印n“是素数”i?YN图 2.12传统流程图的优点:直观形象,逻辑关系清楚缺点是:篇幅较多,费时又不方便.N-S结构化流程图已代替传统的流程图Return返回图2.34182.4.3 三种基本结构和改进的流程图传统流程图的弊端v对流程线没有严格的限制,复杂的算法就会使流程图变得毫无规律,难以阅读和修改,算法的可靠性和可维护性不能得到保证(见书中P24 图 2.13)v为提

9、高算法的质量,必须限制流程的随意转向.可算法不可能由一个个框按顺序执行.所以人们设想规定了几种基本结构,由各个基本结构顺序排列组成算法.三种基本结构v顺序结构(最简单)v选择结构(又称选取或分支结构)v循环结构(重复结构)当型(While)直到型(Until)19ABab图2.14 顺序ABabpYN图2.15 选择(A或B可一空)Aabp1YNAabp2YN图2.17 循环(While和Until型)共同特点:只有一入口(a点)只有一出口(b点)每一部分都有机会被执行 结构内不存在死循环具有以上特点的都可作为基本结构,但最基本就是以上3种,其他的可以看作为由3种最基本结构派生出来的.Retu

10、rn程序演示1程序演示2202.4.4 用N-S流程图表示算法1973年美国人Nassi和Shneiderman提出了新的流程图形式，即N-S结构化流程图。适合结构化程序设计，省略掉了带箭头的流程线，算法写在一个矩形框内，还可以包含框。用到以下流程图符号：其他的可用这几种结构组合。如图2.24中的A可以是选择结构，B可以是循环结构AB图2.24 顺序结构ABP不成立成立图2.25 选择结构A当p1成立图2.26 当型循环结构A直到p2成立图2.27 直到型循环结构A当p1成立211t2ititi+1i直到i5打印t图2.29 案例2.11 求5！1ii+1i直到i50图2.31 例2.12 5

11、0名学生成绩输入ni,gi1igi80是否输出ni,gii+1i直到i5022例2.13 判定闰年的算法的N-S表示y/400的余数否是为0打印y“是闰年”打印y“非闰年”y/100的余数不为0否是y/4的余数为0打印y“是闰年”打印y“非闰年”否是y+1y直到y25002000y图 2.321sum2deno1sign(-1)signsign1/denosigntermsum+termsumdeno+1deno直到deno100打印sum例2.14 求 算法的N-S表示图 2.3323图 2.34变换使符合基本结构的特点，以解决2个出口点的问题。加了个标志变量wi+1ir=0?Y开始输入nN

12、0w 2in/i的余数ri 和w=0NY1w结束打印n“不是素数”打印n“是素数”w=0YN24i+1in/i的余数r输入n0w 2ir=0是否1w直到i 和w=0w=0是否输出n“是素数”输出n“不是素数”图 2.35N-S的优点：比文字描述直观、形象、易理解比传统流程图紧凑易画，废除了流程线，由各个基本结构按顺序组成总之，结构化的算法由一些基本结构按顺序组成的；基本结构又可以包含其他的基本结构；流程的跳转只存在基本结构范围内，之间不存在；非结构化的算法可以用等价的结构化算法代替；若算法不能分解成若干个基本结构，必然不是结构化的算法Return252.4.5 用伪代码表示算法设计算法时要反复

13、修改，画、修改流程图麻烦。为方便常用称为伪代码的工具。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的。每一行（或几行）表示一个操作。不用图形符号，书写方便，格式紧凑，易懂，向计算机语言算法过渡方便计算机语言中的语句关键字用英文表示，其他可用汉字表示，以便于书写和阅读为原则。无固定的语法规则，只要把意思表达清楚，写成清晰易读的形式。优点：书写格式自由，易表达设计者的思想，容易修改。缺点：不如流程图直观，可能会出现逻辑上的错误。适合软件专业人员，初学者一般采用N-S。下面看几个例子：26例2.16 求5！BEGIN 1t 2i while i=5 ti t i+1 i printE

14、ND例2.17 打印出50个学生中成绩高于80分的学号和成绩BEGIN 1i while i=50 input ni and gi i+1 i 1i while i=50 if gi80 print ni and gi i+1 i END27例2.18 判闰年BEGIN2000ywhile y=2500 if y被4整除 if y 不被100整除 print y；“是闰年”else if y被400整除 print y；“是闰年”else print y；“非闰年”end if end if else print y；“非闰年”end if y+1y END例2.19 求BEGIN1sum 2

15、deno 1signwhile deno=2500 (-1)sign sign sign 1/deno term sum+term sum deno+1deno print sum ENDReturn282.4.6 用计算机语言表示算法设计算法的目的是实现算法。作曲家创作曲谱和演奏家演奏乐谱、菜谱和厨师炒菜实现算法的方式有多种：人工心算、笔算和用计算器等。我们的任务就是用计算机实现算法，那就要用计算机语言编写程序例2.20 5！算法用C语言表示：#Includevoid main()int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(“%d”,t);程序演

16、示29例2.21 求 算法用C语言表示#Includevoid main()int sign=1;float deno=2.0,sum=1.0,term;while(deno=100)sign=-sign;term=sign/deno;sum=sum+term;deno=deno+1;printf(“%f”,sum);程序演示Return302.5 结构化程序设计方法结构化程序便于编写、阅读、修改和维护，减少程序出错的机会，提高可靠性，保证质量。结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构，怎样得到一个结构化的程序呢？基本思路为：把复杂问题分解成多个阶段，而每一阶段都容易理

17、解和处理。具体地说，有以下4种方法可得到结构化程序：自顶向下逐步细化模块化设计结构化编码接受一任务后怎样着手进行呢？有2种方法，以写文章来说，自顶向下，逐步细化自下而上，逐步积累。提倡第一种方法，即是用工程的方法设计程序，例如设计房屋。此方法的过程是将问题求解由抽象逐步具体化的过程，也便于验证，在向下一层展开前要本层设计的正确。下面看一个实例31例2.22 将1到1000之间的素数打印出来。用“筛法”求解，即用“埃拉托色尼筛法”：在纸上写上1到1000全部整数，判断一个素数就把它挖掉。输入1n去掉非素数打印ABC顶层设计输入n1i当inixii+1iA：1i当in把剩下的xi打出来i+1iC：

18、Gxi=0是否打印xiG:32将x1去掉(让x1=0)2i当i 的整数部分i+1iB：如xi未去掉,则将xi+1到xn间全部是xi倍数的数去掉Dxi=0是否将xi+1到xn间全部是xi倍数的数去掉D:Ei+1j当jn将能被xi整除的xj去掉j+1jE：Fxi=0是否xj能被xi整除F:是否使xj=033也可用伪代码来描述逐步细化过程，如：输入1n各数把所有非素数去掉打印全部素数 i=1while in 把未挖的xi打印出来(if xi 不等于0 then print xi)i=i+1 根据程序模块的功能可划分若干个子模块,若有必要还可划分更小的模块.子模块在C语言中是用函数实现的,一般不超过50行,这样便于组织和阅读.划分时应注意模块的独立性,即完成一项功能且模块间耦合少.Return34