c语言第二章算法ppt课件.ppt

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

1、第二章程序的灵魂-算法教材第2章为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益一个程序包括对数据的描述和对数据处理的描述。一个程序包括对数据的描述和对数据处理的描述。1对数据的描述，即数据结构。对数据的描述，即数据结构。在在C语言中，系统提供的数据结构，是以数据类型的形式语言中，系统提供的数据结构，是以数据类型的形式出现的。出现的。2对数据处理的描述，即计算机算法。算法是为解决一个对数据处理的描述，即计算机算法。算法是为解决一个问题而采取的方法和步骤，是程序的灵魂。为此，著名计算问题而采取的方法和步骤，是程序的灵魂。为此，著

2、名计算机科学家沃思（机科学家沃思（NikiklausWirth）提出一个公式：）提出一个公式：数据结构数据结构+算法算法+文档文档=程序程序实际上，一个程序除了数据结构和算法外，还必须使用一实际上，一个程序除了数据结构和算法外，还必须使用一种计算机语言，并采用结构化方法来表示。种计算机语言，并采用结构化方法来表示。程序设计概述程序设计概述为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益算法算法:解决一个具体问题的意义明确的步骤的集合。解决一个具体问题的意义明确的步骤的集合。从程序来说，也可以说算法是一个有限条指令的集合，这从程

3、序来说，也可以说算法是一个有限条指令的集合，这些指令确定了解决某一特定类型问题的运算序列。些指令确定了解决某一特定类型问题的运算序列。对于同一个问题可以有不同的解题方法和步骤，也就是有对于同一个问题可以有不同的解题方法和步骤，也就是有不同的算法。算法有优劣，一般而言，应当选择简单的、运算不同的算法。算法有优劣，一般而言，应当选择简单的、运算步骤少的，即步骤少的，即运算快、内存开销小运算快、内存开销小的算法（算法的时空效率）。的算法（算法的时空效率）。21 算法的概念为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益买电视机的步骤

4、：买电视机的步骤：选好货物开票付款拿发票取货回家考大学上大学的步骤考大学上大学的步骤填报名单交报名费拿准考证参加考试得到录取通知书报到注册为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益n计算机算法计算机能执行的算法n数值运算算法n非数值运算算法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例1求求12345。可先写出这样的算法：可先写出这样的算法：（1）先求）先求12，得到结果，得到结果2；（2）将步骤）将步骤1得到的结果再乘以得到的结果再乘以3，得到结

5、果，得到结果6；（3）将）将6再乘以再乘以4，得到，得到24；（4）将）将24再乘以再乘以5，得到，得到120。2.2、简单算法举例求求123499呢呢为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益n上述算法太繁琐，我们找一种通用的表示方法。s1:设变量p，被乘数，p=1;s2:设变量i,代表乘数，i=2;s3:使pi,乘积放在被乘数变量p中，可表示为：p i p;s4:使i的值加1，即i+1 i;s5:如果i不大于5，返回重新执行步骤s3以及其后的s4、s5;否则，算法结束。最后得到的p就是5!的值。例例1：求：求1234

6、5为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益上述算法稍作改动：上述算法稍作改动：s1:1 p;s2:3 i;s3:p i p;s4:i+2 is5:若i11,返回s3;否则，结束。例例2.2.求求13579111357911为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 请同学们仔细分析循环结束的条件，即请同学们仔细分析循环结束的条件，即s5步骤，如果在求求步骤，如果在求求1357911时，时，将将s5步骤写成：步骤写成：s5：若：若i2500,算法停

7、止。算法停止。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益（1）使）使S=0（S作为累加变量）；作为累加变量）；（2）使）使N=1（N代表分母）；代表分母）；（3）S+1.0/NS（执行迭代，（执行迭代，S为迭代变量）；为迭代变量）；（4）N+1N；（5）若）若N100，转去执行（转去执行（3）以及其后的各步骤；否则）以及其后的各步骤；否则执行（执行（6）；）；（6）打印）打印S的值（即所求之总和）。的值（即所求之总和）。可以写出下面的算法可以写出下面的算法例例5.求下级数的值求下级数的值为了规范事业单位聘用关系，建立和完

8、善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益n1、有穷性：、有穷性：n2、确定性：、确定性：n3、有有0个个或或多多个个输输入入（即即：可可以以没没有有输输入入，也可以有输入）也可以有输入）n4、有、有1个或多个输出个或多个输出（即算法必须得到结果）（即算法必须得到结果）n5、有效性、有效性2.3.算法的特性算法的特性为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 为了表示一个算法，可以用不同的方法。为了表示一个算法，可以用不同的方法。常用的算法表示方法：常用的算法表示方法：自然语言，传

9、统流程图，结构化流程图（自然语言，传统流程图，结构化流程图（N-S流流程图），伪代码、计算机语言等。程图），伪代码、计算机语言等。（重点：传统流程图，（重点：传统流程图，N-S流程图）流程图）2.4.怎样表示一个算法？怎样表示一个算法？为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益2.4.1 用自然语言表示算法用自然语言表示算法自然语言就是人们常用的语言，可以是汉语、自然语言就是人们常用的语言，可以是汉语、英语或其他语言。英语或其他语言。用自然语言表示通俗易懂；用自然语言表示通俗易懂；但文字冗长，容易出现但文字冗长，容易出现

10、“歧义歧义”性；性；而且，用自然语言描述包含分支和循环的而且，用自然语言描述包含分支和循环的算法，不很方便。算法，不很方便。一般不使用自然语言描述算法一般不使用自然语言描述算法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例如：描述计算并输出例如：描述计算并输出z=y/x的流程，可以用自的流程，可以用自然语言描述如下：然语言描述如下：（1）输入）输入x，y。（2）判断）判断x是否为是否为0：若若x=0,则输出错误信息；则输出错误信息；否则计算否则计算y/xz，且输出，且输出z。自然语言描述举例自然语言描述举例为了规范事业单位

11、聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益算法描述语言：算法描述语言：是为了说明程序的流程而专门规定的某种是为了说明程序的流程而专门规定的某种语言。它一般介于自然语言与程序设计语言之间，它具有自然语言。它一般介于自然语言与程序设计语言之间，它具有自然语言灵活的特点，同时又接近于程序设计语言的描述。语言灵活的特点，同时又接近于程序设计语言的描述。注意：注意：算法描述语言所描述的流程，一般不能直接作为程序算法描述语言所描述的流程，一般不能直接作为程序来使用，最后还需转换成用某种程序设计语言所描述的程序。来使用，最后还需转换成用某种程序设计语

12、言所描述的程序。与程序设计语言的区别：与程序设计语言的区别：前者比较自由，不象后者那样受语法的约束，只要描述得人前者比较自由，不象后者那样受语法的约束，只要描述得人们能理解就行，而不必考虑计算机处理时所要遵循的规定或其们能理解就行，而不必考虑计算机处理时所要遵循的规定或其它一些细节。它一些细节。算法描述语言算法描述语言为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益2.4.2用流程图表示算法用流程图表示算法 流程图：流程图：用一些约定的几何图形来描述算法。用某用一些约定的几何图形来描述算法。用某种图框表示某种操作，用箭头表示算

13、法流程种图框表示某种操作，用箭头表示算法流程流程图（的符号及意义）流程图（的符号及意义）美国标准化协会美国标准化协会ANSI规定规定了一些常用的流程图符号，已为世界各国程序工作者普了一些常用的流程图符号，已为世界各国程序工作者普遍采用：遍采用：启止框输入输出框判断选择框处理框流程线连接点注释框t=1i=2t=t*ii=i+1i5结束 NY 开始例：例：求求5！为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益三种基本结构是：三种基本结构是：（1）顺序结构）顺序结构按指令的顺序依次执行按指令的顺序依次执行（2）判断选择结构：）判断

14、选择结构：根据判别条件有选择地改变根据判别条件有选择地改变执行流程执行流程（3）循环结构：）循环结构：有条件的重复地执行某个程序块有条件的重复地执行某个程序块2.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益n依次顺序执行程序语句依次顺序执行程序语句a块块b块块AB例如，令例如，令a、b的值的值分别为分别为5、10；a=5；b=10；(1)顺序结构程序设计顺序结构程序设计为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人

15、单位和职工的合法权益n首先判别条件，若条件满足，程序执行首先判别条件，若条件满足，程序执行a块，否则，执行块，否则，执行b块；块；n举例，求举例，求a、b两个两个数中的最大值；数中的最大值；条件成立？条件成立？执行执行a块块执行执行b块块成立成立不成立不成立b max？Max=a；max=b；YN(2)判别选择结构程序设计判别选择结构程序设计为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益n循环又分循环又分“当型循环当型循环”和和“直到型循环直到型循环”n举例，求1100的累加和。int i，sum=0；while（i=100

16、)sum=sum+i;i=i+1;i5打印打印t循环结构程序设计循环结构程序设计为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益当型循环：当型循环：当条件当条件p成立时，反复执行循成立时，反复执行循环体中指令，直到环体中指令，直到p条件不成立为止。当条件不成立为止。当型循环先判断，再决定是否执行循环体，型循环先判断，再决定是否执行循环体，所以在条件所以在条件p一次都不满足时，循环体可一次都不满足时，循环体可能一次都不执行能一次都不执行当条件当条件p满足时满足时执行循环中指令执行循环中指令为了规范事业单位聘用关系，建立和完善适应

17、社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益直直到到型型循循环环：当当条条件件p不不成成立立时时，反反复复执执行行循循环环体体中中的的指指令令，直直到到p条条件件成成立立为为止止。直直到到型型循循环环先先执执行行循循环环体体，然然后后再再判断条件判断条件p，所以循环体至少执行一次。，所以循环体至少执行一次。直到条件直到条件p满足为止满足为止执行循环中的指令执行循环中的指令为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益用伪代码表示算法（常常用于算法设计）用伪代码表示算法（常常用于算法设计）用传统

18、流程图、用传统流程图、N-S图表示算法，直观易懂，但绘制比较图表示算法，直观易懂，但绘制比较麻烦，在设计一个算法时，可能要反复修改，而修改流麻烦，在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的，因此，流程图适合表示算法，但在程图是比较麻烦的，因此，流程图适合表示算法，但在设计算法过程中使用不是很理想。为了设计算法方便，设计算法过程中使用不是很理想。为了设计算法方便，常使用伪代码工具。常使用伪代码工具。伪代码是用介于自然语言和计算机语言之间的文字和符伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。伪代码不用图形符号，书写方便，格式号来描述算法。伪代码不用图形符号，书写方

19、便，格式紧凑，便于向计算机语言算法过渡紧凑，便于向计算机语言算法过渡2.4.5用伪代码表示算法用伪代码表示算法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益用某种程序设计语言编写的程序本质上也是用某种程序设计语言编写的程序本质上也是问题处理方案的描述，并且是最终的描述。问题处理方案的描述，并且是最终的描述。在一般的程序设计过程中，不提倡一开始就在一般的程序设计过程中，不提倡一开始就编写程序，特别是对于大型的程序。编写程序，特别是对于大型的程序。程序是程序设计的最终产品，需要经过每一程序是程序设计的最终产品，需要经过每一步的细

20、致加工才能得到，如果企图一开始就编步的细致加工才能得到，如果企图一开始就编写出程序，往往会适得其反，达不到预想的结写出程序，往往会适得其反，达不到预想的结果果。2.4.6用计算机语言表示算法用计算机语言表示算法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例 求求5！，用！，用C语言表示语言表示void main()int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(“%d”,t);为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职

21、工的合法权益判断闰年的具体程序#include void main()int year,yes;year=2000;while(year=2500)if(year%4=0&year%100!=0|year%400=0)printf(%d年是闰年n,year);elseprintf(%d年不是闰年n,year);year+;为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例 求级数的值求级数的值void main()int sign=1;float deno=2.0,sun=1.0,term;while(deno=100)si

22、gn=-sign;term=sign/deno;sum=sum+term;deno=deno+1;printf(“%f”,sum);为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益结构化程序设计方法n一个结构化程序就是用高级语言表示的结一个结构化程序就是用高级语言表示的结构化算法。构化算法。n1、自顶向下、自顶向下2、逐步细化、逐步细化n3、模块化设计、模块化设计4、结构化编码、结构化编码为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益结构化程序设计方法结构化程序设计方法一个结构化程序就是用高级语言表示的结构化算法。一个结构化程序就是用高级语言表示的结构化算法。1、自顶向下、自顶向下 2、逐步细化、逐步细化3、模块化设计、模块化设计 4、结构化编码、结构化编码为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益作业nP36n 4（1）（4）（5）n 8（2）