C语言程序设计第二章算法.ppt

C程序设计,主讲人：袁丽,燕大里仁基础教学部,第二章：算法程序的灵魂,一个程序主要包括两方面的信息：,对数据的描述：在程序中要指定用到哪些数据以及这些数据 的类型和数据的组织形式。即数据结构（data structure),对操作的描述：即要求计算机进行操作的步骤，也就是算法 (algorithm),著名计算机科学家沃思提出的一个公式：算法+数据结构=程序,算法就是解决问题的思路。有好的算法，才会有好的程序。算法是程序的精髓。 类比于我们平常用的汉语，我们都能看懂普通的文字，但不是每个会说普通话的人 都能写出漂亮的文章。,数据是操作的对象;操作的目的是对数据进行加工处理，以得到期望的结果,一个程序除了算法和数据结构这主要要素外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示 算法、数据结构、程序设计方法和语言工具是一个程序设计人员应具备的知识,算法是解决“做什么”和“怎么做”的问题 程序中的操作语句，是算法的体现 不了解算法就谈不上程序设计,一、什么是算法,广义地讲：为解决一个问题而采取的方法和步骤，就称为算法。 例如：描述太极拳动作的图解，就是太极拳的算法。一首歌曲的 乐谱，也可以称为该歌曲的算法。,计算机能执行的算法，为计算机算法。其可分为两大类别： 数值运算算法和非数值运算算法。,对同一个问题，可以有不同的解题方法和步骤 为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法,数值运算的目的是求数值解 非数值运算包括的面十分广泛，最常见的是用于事务管理领域,例1、求1*2*3*4*5。,例2、有50个学生，要求输出成绩在80分以上的学生的学号和成绩。,例3、给出一个大于或等于3的正整数，判断它是不是一个素数。,二、算法的特性,有穷性：一个算法应包含有限的操作步骤，而不能是无限的。 有穷性往往指“在合理的范围之内”。“合理限度”由人们的常识 和需要判定。,确定性：算法的每一个步骤都应当是确定的，不应当含糊和模棱 两可。也就是说算法的含义应当是唯一的，而不可以产生“歧义性”,有零个或多个输入：所谓输入是指在执行算法时需要从外界取得 必要的信息。一个算法可以有两个或多个输入，也可以没有输入。,有一个或多个输出：算法的目的是为了求解，“解”就是输出。 但算法的输出并不一定就是计算机的打印输出或屏幕输出，一个算法 得到的结果就是算法的输出，没有输出的算法是没有意义的。,有效性：算法中的每一个步骤都应当能有效地执行，并得到确定 的结果。,三、算法的表示,用自然语言表示算法,用流程图表示算法,三种基本结构和改进的流程图,用N-S流程图表示算法,用伪代码表示算法,用计算机语言表示算法,（1）用自然语言表示算法,用自然语言表示通俗易懂，但文字冗长，容易出现歧义性 用自然语言描述包含分支和循环的算法，不很方便 除了很简单的问题外，一般不用自然语言,（2）用流程图表示算法,流程图是用一些图框表示各种操作。,x0,Y,N,一个入口,两个出口,菱形框的作用是对一个给定的条件进行判断，根据给定的条件 是否成立决定如何执行其后的操作。,连接点（小圆圈）是用于将画在不同地方的流程线连接起来。,位置不够,防止交叉,例、求1*2*3*4*5。将该算法用流程图表示。,开始,1t,2i,t*it,i+1i,i5,Y,结束,N,如果需要将最后结果输出:,开始,1t,2i,t*it,i+1i,i5,Y,N,输出t,结束,如果需要将最后结果输出:,例、求1*2*3*4*5。将该算法用流程图表示。,例、 判定20002500年中的每一年是否闰年，将结果输出。 将该算法用流程图表示。,N,Y,Y,N,Y,N,N,Y,1.通过以上几个例子可以看出流程图是表示算法的较好的工具。,2.一个流程图包括以下几部分： (1) 表示相应操作的框 (2) 带箭头的流程线 (3) 框内外必要的文字说明,3.流程线不要忘记画箭头，否则难以判定各框的执行次序。,（3）三种基本结构和改进的流程图,1.传统流程图的弊端 传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制 使用者可以毫不受限制地使流程随意地转来转去，使人难以理解算法的逻辑 2.三种基本结构,(1)顺序结构,A,B,（2）选择结构,Y,A,N,B,Y,A,N,（3）循环结构, 当型循环结构,Y,A,N,0x,Y,x+1x,N,输出1,2,3,4,5, 直到型循环结构,A,N,Y,0x,x+1x,N,Y,输出1,2,3,4,5,以上三种基本结构，有以下共同特点： (1) 只有一个入口 (2) 只有一个出口 一个判断框有两个出口 一个选择结构只有一个出口 (3) 结构内的每一部分都有机会被执行到。也就是说，对每一个框来说，都应当有一条从入口到出口的路径通过它 (4) 结构内不存在“死循环” 由以上3种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。,由三种基本结构派生出来的结构：,A,Y,B,N,根据表达式p的值进行选择,p=p1,A,p=p2,B,p=pm,M,p=pn,N,（4）用N-S流程图表示算法,顺序结构,选择结构,循环结构 （当型）,循环结构（直到型）,例：求5!算法用N-S图表示。,1t,2i,t*it,i+1i,直到i5,输出t,例:将50名学生中成绩高于80分者的学号和成绩输出。将该算法用N-S图表示。,1i,输入ni、gi,i+1i,直到i50,1i,gi80,是,输出ni,gi,否,i+1i,直到i50,例:将判定闰年的算法用N-S图表示,一个结构化的算法是由一些基本结构顺序组成的 在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内 一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变 如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法,（5）用伪代码表示算法,伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法 用伪代码写算法并无固定的、严格的语法规则，可以用英文，也可以中英文混用,例:求5!。 begin (算法开始) 1 t 2 i while i5 t*i t i+1 i print t end (算法结束),例: 求,begin 1 sum 2 deno 1 sign while deno 100 (-1)*sign sign sign*1/deno term sum+term sum deno+1 deno print sum end,（6）用计算机语言表示算法,要完成一项工作，包括设计算法和实现算法两个部分。 设计算法的目的是为了实现算法。 不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。,例:将算法（求5!）用C语言表示。,#include int main( ) int i,t; t=1; i=2; while(i=5) t=t*i; i=i+1; printf(“%dn“,t); return 0; ,例:将算法（求多项式的值）用C语言表示。,#include int main( ) int sign=1; double deno = 2.0,sum = 1.0, term; while (deno = 100) sign = -sign; term = sign/deno; sum = sum+term; deno = deno+1; printf (“%fn“,sum); return 0; ,四、结构化程序设计方法,结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。 结构化程序设计方法的基本思路是：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。,采取以下方法保证得到结构化的程序： （1） 自顶向下； （2） 逐步细化； （3） 模块化设计； （4） 结构化编码。,用三种基本结构组成的程序是结构化程序,自顶向上，逐步细化：将问题求解由抽象逐步具体化的设计过程。,比如设计房屋，先进行整体规划，然后确定建筑物方案，再进行各个部分的设计，最后进行细节的设计（门窗，楼道等），而绝不会在没有整体方 案之前先设计楼道和厕所。而在完成设计，有了图纸之后，在施工阶段则 是自下而上实施的，用一砖一瓦实现一个局部，最后由各个部分组成一个 建筑物。,模块化设计：“分而治之”的思想，把大任务分为若干子任务。,程序中的子模块在C语言中通常是用函数来实现。,结构化编码：将已设计好的算法用计算机语言来表示，即根据已经细化的 算法正确写出计算机程序。,结构化程序设计步骤,一、确定算法：分析问题（建立数学模型，利用公式),写出算法 描述（比如流程图）,二、编写程序：用计算机语言写出实现算法的程序,三、上机调试：输入（编辑）程序-编译、连接、执行程序-输出结果,举例：,算经中提出“百鸡问题”：鸡翁一值钱五，鸡母一值钱三， 鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？ （体会编程步骤）,(1)分析：cocks+hens+chicks=100 5*cocks+3*hens+chicks/3=100,其中，0 cocks 19 , 0 hens 33 ,0 chicks 100,累试法（枚举法）求解,算法描述： cocks=0 当cocks 19时 找满足题意的hens,chicks数 cocks加1 ,细化,cocks=0 当cocks 19时 hens=0 当hens 33时 找满足题意的chicks数 hens加1 hens加1 ,细化,cocks=0,当cocks 19时,hens=0 当hens 33时,chicks=100-cocks-hens 如果（5*cocks+3*hens+chicks/3=100） 则输出,hens加1,cocks加1,(2)