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

《C语言程序设计第二章算法.ppt》由会员分享，可在线阅读，更多相关《C语言程序设计第二章算法.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 C程序设计程序设计主讲人：袁丽主讲人：袁丽燕大里仁基础教学部第二章：算法第二章：算法程序的灵魂程序的灵魂1 什么是算法什么是算法2 算法的特性算法的特性3 算法的表示算法的表示4 结构化程序设计方法结构化程序设计方法一个程序主要包括两方面的信息：一个程序主要包括两方面的信息：u 对数据的描述：在程序中要指定用到哪些数据以及这些数据对数据的描述：在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式。即数据结构（的类型和数据的组织形式。即数据结构（data structure)data structure)u 对操作的描述：即要求计算机进行操作的步骤，也就是算法对操作的描述：即要求计算机

2、进行操作的步骤，也就是算法(algorithm)(algorithm)著名计算机科学家沃思提出的一个公式：算法+数据结构=程序 算法就是解决问题的思路。有好的算法，才会有好的程序。算法是程序的精髓。算法就是解决问题的思路。有好的算法，才会有好的程序。算法是程序的精髓。类比于我们平常用的汉语，我们都能看懂普通的文字，但不是每个会说普通话的人类比于我们平常用的汉语，我们都能看懂普通的文字，但不是每个会说普通话的人都能写出漂亮的文章。都能写出漂亮的文章。数据是操作的对象数据是操作的对象;操作的目的是对数据进行加工处理，以操作的目的是对数据进行加工处理，以得到期望的结果得到期望的结果 一个程序除了一个

3、程序除了算法和数据结构这算法和数据结构这主要要素外，还应当采用结主要要素外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表构化程序设计方法进行程序设计，并且用某一种计算机语言表示示 算法算法、数据结构数据结构、程序设计方法程序设计方法和和语言工具语言工具是一个程序设计是一个程序设计人员应具备的知识人员应具备的知识u算法是解决算法是解决“做什么做什么”和和“怎么做怎么做”的问题的问题u程序中的操作语句，是算法的体现程序中的操作语句，是算法的体现u不了解算法就谈不上程序设计不了解算法就谈不上程序设计一、什么是算法一、什么是算法 广义地讲：为解决一个问题而采取的方法和步骤，就称为

4、算法。广义地讲：为解决一个问题而采取的方法和步骤，就称为算法。例如：描述太极拳动作的图解，就是太极拳的算法。一首歌曲的例如：描述太极拳动作的图解，就是太极拳的算法。一首歌曲的乐谱，也可以称为该歌曲的算法。乐谱，也可以称为该歌曲的算法。计算机能执行的算法，为计算机算法。其可分为两大类别：计算机能执行的算法，为计算机算法。其可分为两大类别：数值运算数值运算算法和算法和非数值运算非数值运算算法。算法。对同一个问题，可以有不同的解题方法和步骤对同一个问题，可以有不同的解题方法和步骤为了有效地进行解题，不仅需要保证算法正确，还要考虑算法为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合

5、适的算法的质量，选择合适的算法数值运算数值运算的目的是求数值解的目的是求数值解非数值运算非数值运算包括的面十分广泛，最常见的是用于事务管理领域包括的面十分广泛，最常见的是用于事务管理领域例例1 1、求、求1 1*2 2*3 3*4 4*5 5。例例2 2、有、有5050个学生，要求输出成绩在个学生，要求输出成绩在8080分以上的学生的学号和成绩。分以上的学生的学号和成绩。例例3 3、给出一个大于或等于、给出一个大于或等于3 3的正整数，判断它是不是一个素数。的正整数，判断它是不是一个素数。二、算法的特性二、算法的特性u有穷性有穷性：一个算法应包含有限的操作步骤，而不能是无限的。一个算法应包含有

6、限的操作步骤，而不能是无限的。有穷性往往指有穷性往往指“在合理的范围之内在合理的范围之内”。“合理限度合理限度”由人们的常识由人们的常识和需要判定。和需要判定。u确定性确定性：算法的每一个步骤都应当是确定的，不应当含糊和模棱算法的每一个步骤都应当是确定的，不应当含糊和模棱两可。也就是说算法的含义应当是唯一的，而不可以产生两可。也就是说算法的含义应当是唯一的，而不可以产生“歧义性歧义性”u有零个或多个输入有零个或多个输入：所谓输入是指在执行算法时需要从外界取得所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法可以有两个或多个输入，也可以没有输入。必要的信息。一个算法可以有两个或多个输入，

7、也可以没有输入。u有一个或多个输出有一个或多个输出：算法的目的是为了求解，算法的目的是为了求解，“解解”就是输出。就是输出。但算法的输出并不一定就是计算机的打印输出或屏幕输出，一个算法但算法的输出并不一定就是计算机的打印输出或屏幕输出，一个算法得到的结果就是算法的输出，没有输出的算法是没有意义的。得到的结果就是算法的输出，没有输出的算法是没有意义的。u有效性有效性：算法中的每一个步骤都应当能有效地执行，并得到确定算法中的每一个步骤都应当能有效地执行，并得到确定的结果。的结果。三、算法的表示三、算法的表示 用自然语言表示算法用自然语言表示算法 用流程图表示算法用流程图表示算法 三种基本结构和改进

8、的流程图三种基本结构和改进的流程图 用用N-SN-S流程图表示算法流程图表示算法 用伪代码表示算法用伪代码表示算法 用计算机语言表示算法用计算机语言表示算法（1）用自然语言表示算法）用自然语言表示算法n用自然语言表示通俗易懂，但文字冗长，容易出现歧义性用自然语言表示通俗易懂，但文字冗长，容易出现歧义性n用自然语言描述包含分支和循环的算法，不很方便用自然语言描述包含分支和循环的算法，不很方便n除了很简单的问题外，一般不用自然语言除了很简单的问题外，一般不用自然语言（2）用流程图表示算法）用流程图表示算法流程图是用一些图框表示各种操作。流程图是用一些图框表示各种操作。x 0YN一个入口一个入口两个

9、出口两个出口 菱形框的作用是对一个给定的条件进行判断，根据给定的条件菱形框的作用是对一个给定的条件进行判断，根据给定的条件是否成立决定如何执行其后的操作。是否成立决定如何执行其后的操作。连接点（小圆圈）是用于将画在不同地方的流程线连接起来。连接点（小圆圈）是用于将画在不同地方的流程线连接起来。位置不够位置不够防止交叉防止交叉例、求例、求1 1*2 2*3 3*4 4*5 5。将该。将该算法用流程图表示。算法用流程图表示。开始开始1t2it*iti+1ii5Y结束结束N如果需要将最后结果输出如果需要将最后结果输出:开始开始1t2it*iti+1ii5YN输出输出t结束结束如果需要将最后结果输出如

10、果需要将最后结果输出:例、求例、求1 1*2 2*3 3*4 4*5 5。将该。将该算法用流程图表示。算法用流程图表示。例、例、判定判定2000200025002500年中的每一年是否闰年，将结果输出。年中的每一年是否闰年，将结果输出。将该将该算法用流程图表示。算法用流程图表示。开始开始year不能不能被被4整除整除2000yearNyear不能不能被被100整除整除Yyear是闰年是闰年Yyear不是闰年不是闰年Nyear不能不能被被400整除整除Yyear不是闰年不是闰年Nyear是闰年是闰年year+1yearyear2500NY结束结束1.1.通过以上几个例子可以看出流程图是表示算法的

11、较好的工具通过以上几个例子可以看出流程图是表示算法的较好的工具。2.2.一个流程图包括以下几部分一个流程图包括以下几部分：(1)(1)表示相应操作的框表示相应操作的框(2)(2)带箭头的流程线带箭头的流程线(3)(3)框内外必要的文字说明框内外必要的文字说明3.3.流程线不要忘记画箭头，流程线不要忘记画箭头，否则否则难以判定各框的执行次序难以判定各框的执行次序。（3）三种基本结构和改进的流程图）三种基本结构和改进的流程图1.1.传统流程图的弊端传统流程图的弊端n传统的流程图用流程线指出各框的执行顺序，对流程线传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制的使用没有严格限制n

12、使用者可以毫不受限制地使流程随意地转来转去，使人使用者可以毫不受限制地使流程随意地转来转去，使人难以理解算法的逻辑难以理解算法的逻辑2.2.三种基本结构三种基本结构(1)(1)顺序结构顺序结构AB（2 2）选择结构）选择结构pYANBpYAN（3 3）循环结构）循环结构 当型循环结构当型循环结构p1YAN0 xx5输出输出t例例:将将5050名学生中成绩高于名学生中成绩高于8080分者的学号和成绩输出。将分者的学号和成绩输出。将该该算法用算法用N-SN-S图表示。图表示。1i输入输入ni、gii+1i直到直到i501igi 80是是输出输出ni,gi否否i+1i直到直到i50例例:将判定闰年的

13、算法用将判定闰年的算法用N-SN-S图表示图表示n一个结构化的算法是由一些基本结构顺序组成的一个结构化的算法是由一些基本结构顺序组成的n在基本结构之间不存在向前或向后的跳转，流程的转移只在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内存在于一个基本结构范围之内n一个非结构化的算法可以用一个等价的结构化算法代替，一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变其功能不变n如果一个算法不能分解为若干个基本结构，则它必然不是如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法一个结构化的算法（5）用伪代码表示用伪代码表示算法算法n伪代码是用介于自

14、然语言和计算机语言之间的文字和符号来描伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法述算法n用伪代码写算法并无固定的、严格的语法规则，可以用英文，用伪代码写算法并无固定的、严格的语法规则，可以用英文，也可以中英文混用也可以中英文混用例例:求求5!5!。beginbegin (算法开始算法开始)1 1 t t 2 2 i i while i while i5 5 t*i t*i t t i+1 i+1 i i print t print tend end (算法结束算法结束)例例:求求begin begin 1 1 sumsum 2 2 denodeno 1 1 signsign

15、while deno while deno 100 100 (-1)*sign (-1)*sign sign sign sign*1/deno sign*1/deno term term sum+term sum+term sum sum deno+1 deno+1 deno deno print sum print sumendend（6 6）用计算机语言表示用计算机语言表示算法算法n要完成一项工作，包括要完成一项工作，包括设计算法设计算法和和实现算法实现算法两个部分。两个部分。n设计算法的目的是为了实现算法。设计算法的目的是为了实现算法。n不仅要考虑如何设计一个算法，也要考虑如何实现一个算

16、法。不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。例例:将算法（求将算法（求5!5!）用）用C C语言表示。语言表示。#include#include int main()int main()int i,t;int i,t;t=1;i=2;t=1;i=2;while(i=5)while(i=5)t=t*i;t=t*i;i=i+1;i=i+1;printf(%dn,t);printf(%dn,t);return 0;return 0;例例:将算法（求多项式的值）用将算法（求多项式的值）用C C语言表示。语言表示。#include#include int main()int main()i

17、nt sign=1;int sign=1;double deno=2.0,sum=1.0,term;double deno=2.0,sum=1.0,term;while(deno=100)while(deno=100)sign=-sign;sign=-sign;term=sign/deno;term=sign/deno;sum=sum+term;sum=sum+term;deno=deno+1;deno=deno+1;printf(%fn,sum);printf(%fn,sum);return 0;return 0;四、四、结构化程序设计方法结构化程序设计方法n结构化程序结构化程序设计强调程序

18、设计风格和程序结构的规范化，设计强调程序设计风格和程序结构的规范化，提倡清晰的结构提倡清晰的结构。n结构化程序设计方法的结构化程序设计方法的基本思路基本思路是：把一个复杂问题的求是：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。易理解和处理的范围内。n采取以下方法保证得到结构化的程序：采取以下方法保证得到结构化的程序：（1 1）自顶向下自顶向下；（2 2）逐步细化逐步细化；（3 3）模块化设计模块化设计；（4 4）结构化编码结构化编码。用三种基本结构组成的程序是结构化程序用三种基本结构组成的程序是结构

19、化程序 自顶向上，逐步细化：自顶向上，逐步细化：将问题求解由抽象逐步具体化的设计过程。将问题求解由抽象逐步具体化的设计过程。比如设计房屋，先进行整体规划，然后确定建筑物方案，再进行各个部比如设计房屋，先进行整体规划，然后确定建筑物方案，再进行各个部分的设计，最后进行细节的设计（门窗，楼道等），而绝不会在没有整体方分的设计，最后进行细节的设计（门窗，楼道等），而绝不会在没有整体方案之前先设计楼道和厕所。而在完成设计，有了图纸之后，在施工阶段则案之前先设计楼道和厕所。而在完成设计，有了图纸之后，在施工阶段则是自下而上实施的，用一砖一瓦实现一个局部，最后由各个部分组成一个是自下而上实施的，用一砖一瓦

20、实现一个局部，最后由各个部分组成一个建筑物。建筑物。模块化设计：模块化设计：“分而治之分而治之”的思想，把大任务分为若干子任务。的思想，把大任务分为若干子任务。程序中的子模块在程序中的子模块在C C语言中通常是用函数来实现。语言中通常是用函数来实现。结构化编码：结构化编码：将已设计好的算法用计算机语言来表示，即根据已经细化的将已设计好的算法用计算机语言来表示，即根据已经细化的算法正确写出计算机程序。算法正确写出计算机程序。结构化程序设计结构化程序设计步骤步骤一、确定算法：一、确定算法：分析问题（建立数学模型，利用公式分析问题（建立数学模型，利用公式),),写出算法写出算法 描述（比如流程图描述

21、（比如流程图）二、编写程序：二、编写程序：用计算机语言写出实现算法的程序用计算机语言写出实现算法的程序三、上机调试：三、上机调试：输入（编辑）程序输入（编辑）程序-编译、连接、执行程序编译、连接、执行程序-输出结果输出结果举例：举例：算经算经中提出中提出“百鸡问题百鸡问题”：鸡翁一值钱五，鸡母一值钱三，：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？（体会编程步骤）（体会编程步骤）(1)(1)分析：分析：cocks+hens+chicks=100 5*cocks+3*hens+chicks/3=100cocks+he

22、ns+chicks=100 5*cocks+3*hens+chicks/3=100其中，其中，0 cocks 19 ,0 hens 33 ,0 chicks 1000 cocks 19 ,0 hens 33 ,0 chicks 100累试法（枚举法）求解累试法（枚举法）求解算法描述：算法描述：cocks=0 cocks=0 当当cocks 19cocks 19时时找满足题意的找满足题意的hens,chickshens,chicks数数 cocks cocks加加1 1 细化细化cocks=0cocks=0 当当cocks 19cocks 19时时hens=0hens=0当当hens 33hen

23、s 33时时 找满足题意的找满足题意的chickschicks数数 hens hens加加11henshens加加1 1 细化细化cocks=0cocks=0当当cocks 19cocks 19时时hens=0hens=0当当hens 33hens 33时时chicks=100-cocks-henschicks=100-cocks-hens 如果（如果（5*cocks+3*hens+chicks/3=1005*cocks+3*hens+chicks/3=100）则输出则输出henshens加加11cockscocks加加11(2)(2)计算机语言写出程序计算机语言写出程序int main()i

24、nt main()int cocks=0.hens,chicks;int cocks=0.hens,chicks;while(cocks=19)while(cocks=19)hens=0;hens=0;while(hens=33)while(hens=33)chicks=100-cocks-hens;chicks=100-cocks-hens;if(5*cocks+3*hens+chicks/3=100)if(5*cocks+3*hens+chicks/3=100)printf(“%d%d%dn”,cocks,hens,chicks);printf(“%d%d%dn”,cocks,hens,chicks);hens+;hens+;cocks+;cocks+;return 0;return 0;#include#include