《c语言程序设计 第3章 程序的简单算法设计.ppt》由会员分享,可在线阅读,更多相关《c语言程序设计 第3章 程序的简单算法设计.ppt(43页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、C语言程序设计教程语言程序设计教程(第(第2版)版)第第3 3章章 简单算法设计简单算法设计 程序=数据结构数据结构数据结构数据结构+算法算法算法算法+程序设计方法程序设计方法程序设计方法程序设计方法+语言工具和环境语言工具和环境语言工具和环境语言工具和环境数据结构:数据结构:数据结构:数据结构:一个程序至少应包括对数据的描述和对操作一个程序至少应包括对数据的描述和对操作一个程序至少应包括对数据的描述和对操作一个程序至少应包括对数据的描述和对操作的描述两个部分的描述两个部分的描述两个部分的描述两个部分,其中对数据的描述就是指在程其中对数据的描述就是指在程其中对数据的描述就是指在程其中对数据的描
2、述就是指在程序中要指定数据的类型和数据的组织形式序中要指定数据的类型和数据的组织形式序中要指定数据的类型和数据的组织形式序中要指定数据的类型和数据的组织形式,这就这就这就这就是数据结构。是数据结构。是数据结构。是数据结构。算法:算法:算法:算法:对操作的描述就是对解决问题的操作步骤的对操作的描述就是对解决问题的操作步骤的对操作的描述就是对解决问题的操作步骤的对操作的描述就是对解决问题的操作步骤的描述,即所谓的算法。算法是程序的灵魂。描述,即所谓的算法。算法是程序的灵魂。描述,即所谓的算法。算法是程序的灵魂。描述,即所谓的算法。算法是程序的灵魂。一个程序除了数据结构和算法外,还与一个程序除了数据
3、结构和算法外,还与具体的程序设计环境和语言工具有关。必具体的程序设计环境和语言工具有关。必须使用一种计算机语言,像须使用一种计算机语言,像BASIC(True basic、Qbasic、Virtual Basic)语言、)语言、C语言、语言、PASCAL语言、语言、FORTRAN 语言等语言等都是计算机语言。都是计算机语言。本书将具体介绍本书将具体介绍C语言环境下数据结构语言环境下数据结构的定义与算法的实现。的定义与算法的实现。1.1算法算法 解决问题的方法和要遵循的步骤。算法描述了程序要执行的操作及操作的步解决问题的方法和要遵循的步骤。算法描述了程序要执行的操作及操作的步骤顺序。在计算机科学
4、中,算法是指描述用计算机解决给定问题的过程,骤顺序。在计算机科学中,算法是指描述用计算机解决给定问题的过程,是解题方案的准确而完整的描述,也是在有限步骤内求解某一问题所使用是解题方案的准确而完整的描述,也是在有限步骤内求解某一问题所使用的一组定义明确的规则。的一组定义明确的规则。算法并不给出问题的精确的解,只是说明怎样才能得到解。算法并不给出问题的精确的解,只是说明怎样才能得到解。每一个算法都是由一系列的操作指令组成的。这些操作包括加、减、每一个算法都是由一系列的操作指令组成的。这些操作包括加、减、乘、除、判断等,按顺序、选择、循环等结构组成。乘、除、判断等,按顺序、选择、循环等结构组成。算法
5、设计重点:掌握分析问题、解决问题的方法。算法设计重点:掌握分析问题、解决问题的方法。3.1算法的基本概念算法的基本概念【例1】要求从键盘输入3个数,找出其中最小的那个数,将其输出到屏幕。请给出解决这个问题的算法。分析:分析:程序对于从键盘输入的3个数必须用3个变量来保存,分别为a,b,c代表输入的3个数,另外,还需要一个变量min来保存最小的那个数。1.先比较a和b的值,把数值小的放入min中;2.再将min与c比较,又把数值小的放入min中。3.经过两次比较,min中已存放的是a,b,c 3个数中最小的数。把min的值输出就是所需结果。算法步骤:算法步骤:1输入3个数,其值分别赋给3个变量a
6、,b,c;2把a与b中较小的那个数放入变量min中;3把c与min中较小的那个数放入变量min中;4输出最后结果min的值。改进上面的算法描述,将第改进上面的算法描述,将第2 2步和第步和第3 3步的算法具体化。步的算法具体化。1输入三个数,其值分别赋给三个变量a,b,c;2比较a与b的值,如果ab,则min=a;否则min=b;3比较c与min的值,如果cmin,则min=c;4输出最后结果min的值。通过算法描述的步骤,可以很方便地用程序语言来实现。通过算法描述的步骤,可以很方便地用程序语言来实现。【例例例例2 2】:求:求:求:求1 123452345的的的的值值原始解原始解原始解原始解
7、题题步步步步骤骤:步步步步骤骤1 1:先求:先求:先求:先求1 122,得到,得到,得到,得到1 122的的的的结结果:果:果:果:2 2步步步步骤骤2 2:将步:将步:将步:将步骤骤1 1的的的的结结果果果果乘以乘以乘以乘以3 3,得到,得到,得到,得到1 12323的的的的结结果:果:果:果:6 6步步步步骤骤3 3:将步:将步:将步:将步骤骤2 2的的的的结结果果果果乘以乘以乘以乘以4 4,得到,得到,得到,得到1 1234234的的的的结结果:果:果:果:2424步步步步骤骤4 4:将步:将步:将步:将步骤骤3 3的的的的结结果果果果乘以乘以乘以乘以5 5,得到,得到,得到,得到1 1
8、23452345的的的的结结果:果:果:果:120120用用用用计计算机算法表示:算机算法表示:算机算法表示:算机算法表示:步步步步骤骤1 1:使:使:使:使k=1k=1步步步步骤骤2 2:使:使:使:使w=2w=2步步步步骤骤3 3:k=k=kwkw,结结果仍放在果仍放在果仍放在果仍放在k k中中中中步步步步骤骤4 4:使:使:使:使ww的的的的值值加加加加1 1(w+1ww+1w),),),),步步步步骤骤5 5:如果:如果:如果:如果ww的的的的值值不大于不大于不大于不大于5 5,再返回,再返回,再返回,再返回执执行步行步行步行步骤骤3 3、步、步、步、步骤骤4 4;否;否;否;否则结则
9、结束束束束最后得到最后得到最后得到最后得到1234512345的的的的结结果:果:果:果:120120【例例例例3 3】:判定:判定:判定:判定2000250020002500年之间的每一年是否为闰年之间的每一年是否为闰年之间的每一年是否为闰年之间的每一年是否为闰年,并输出该年是否为闰年的信息。年,并输出该年是否为闰年的信息。年,并输出该年是否为闰年的信息。年,并输出该年是否为闰年的信息。闰闰年条件:年条件:年条件:年条件:(1 1)年份能被)年份能被)年份能被)年份能被4 4整除,但不能被整除,但不能被整除,但不能被整除,但不能被100100整除整除整除整除(2 2)年份能被)年份能被)年份
10、能被)年份能被100100整除,同整除,同整除,同整除,同时时也能被也能被也能被也能被400400整除整除整除整除设设yearyear为为被被被被检测检测的年份,的年份,的年份,的年份,算法可表示如下:算法可表示如下:算法可表示如下:算法可表示如下:s1s1:2000 year2000 years2s2:若:若:若:若yearyear不能被不能被不能被不能被4 4整除,整除,整除,整除,则输则输出出出出“yearyear不是不是不是不是闰闰年年年年”,然后,然后,然后,然后转转到到到到s6s6;s3s3:若:若:若:若yearyear能被能被能被能被4 4整除但不能被整除但不能被整除但不能被整
11、除但不能被100100整除,整除,整除,整除,则输则输出出出出“yearyear是是是是闰闰年年年年”,然后,然后,然后,然后转转到到到到s6s6;S4S4:若:若:若:若yearyear能被能被能被能被100100整除又能被整除又能被整除又能被整除又能被400400整除,整除,整除,整除,则输则输出出出出“yearyear是是是是闰闰年年年年”,否,否,否,否则输则输出出出出“yearyear不是不是不是不是闰闰年年年年”,然后,然后,然后,然后转转到到到到s6s6;s5s5:输输出出出出“yearyear不是不是不是不是闰闰年年年年”S6S6:year+1 yearyear+1 yearS
12、7S7:当:当:当:当year2500year2500时时,返回,返回,返回,返回s2s2继续执继续执行,否行,否行,否行,否则结则结果果果果1.21.2算法的特性算法的特性算法的特性算法的特性有穷性:有穷性:无论算法有多么复杂,都必须在有限步之后无论算法有多么复杂,都必须在有限步之后无论算法有多么复杂,都必须在有限步之后无论算法有多么复杂,都必须在有限步之后结束并终止运行,即算法的步骤必须是有限的。在任何情结束并终止运行,即算法的步骤必须是有限的。在任何情结束并终止运行,即算法的步骤必须是有限的。在任何情结束并终止运行,即算法的步骤必须是有限的。在任何情况下,算法都不能陷入无限循环中。况下,
13、算法都不能陷入无限循环中。况下,算法都不能陷入无限循环中。况下,算法都不能陷入无限循环中。确定性:确定性:算法中的每一条指令必须有确切的含义,每算法中的每一条指令必须有确切的含义,每算法中的每一条指令必须有确切的含义,每算法中的每一条指令必须有确切的含义,每个步骤都有确定的执行顺序,即上一步在哪里,下一步是个步骤都有确定的执行顺序,即上一步在哪里,下一步是个步骤都有确定的执行顺序,即上一步在哪里,下一步是个步骤都有确定的执行顺序,即上一步在哪里,下一步是什么,都必须明确,无二义性。什么,都必须明确,无二义性。什么,都必须明确,无二义性。什么,都必须明确,无二义性。可行性:可行性:算法首先必须是
14、正确的,都是能够精确地执算法首先必须是正确的,都是能够精确地执算法首先必须是正确的,都是能够精确地执算法首先必须是正确的,都是能够精确地执行的。对于任意的一组输入,包括合理的输入与不合理的行的。对于任意的一组输入,包括合理的输入与不合理的行的。对于任意的一组输入,包括合理的输入与不合理的行的。对于任意的一组输入,包括合理的输入与不合理的输入,总能得到预期的输出。如果一个算法只是对合理的输入,总能得到预期的输出。如果一个算法只是对合理的输入,总能得到预期的输出。如果一个算法只是对合理的输入,总能得到预期的输出。如果一个算法只是对合理的输入才能得到预期的输出,而在异常情况下却无法预料输输入才能得到
15、预期的输出,而在异常情况下却无法预料输输入才能得到预期的输出,而在异常情况下却无法预料输输入才能得到预期的输出,而在异常情况下却无法预料输出的结果,那么它就不是正确的。出的结果,那么它就不是正确的。出的结果,那么它就不是正确的。出的结果,那么它就不是正确的。输入:输入:一个算法有零个或多个输入,这些输入的信息有一个算法有零个或多个输入,这些输入的信息有一个算法有零个或多个输入,这些输入的信息有一个算法有零个或多个输入,这些输入的信息有的是在执行过程中输入,而有的已被嵌入到算法之中。的是在执行过程中输入,而有的已被嵌入到算法之中。的是在执行过程中输入,而有的已被嵌入到算法之中。的是在执行过程中输
16、入,而有的已被嵌入到算法之中。输出:输出:一个算法之中可以有一个或多个输出。没有输一个算法之中可以有一个或多个输出。没有输一个算法之中可以有一个或多个输出。没有输一个算法之中可以有一个或多个输出。没有输出结果的算法是没有任何意义的。出结果的算法是没有任何意义的。出结果的算法是没有任何意义的。出结果的算法是没有任何意义的。一个问题的解决方案可以有多种表达方式,但只有满足以上一个问题的解决方案可以有多种表达方式,但只有满足以上一个问题的解决方案可以有多种表达方式,但只有满足以上一个问题的解决方案可以有多种表达方式,但只有满足以上5 5个条件的解个条件的解个条件的解个条件的解才能称之为算法。才能称之
17、为算法。才能称之为算法。才能称之为算法。在C语言算法的主要结构有如下3种。1顺序结构顺序结构顺序结构的特点:顺序结构的特点:程序在执行过程中是按语句的程序在执行过程中是按语句的先后顺序先后顺序来执行的,每一条来执行的,每一条语句都代表着一个功能。语句都代表着一个功能。2分支结构分支结构分支结构的特点:分支结构的特点:程序在执行过程中,会根据条件的不同程序在执行过程中,会根据条件的不同有选择的执行有选择的执行不同不同的功能。的功能。3循环结构循环结构循环结构的特点:循环结构的特点:程序在执行过程中,在一定的时间段内或一定的条件下,程序在执行过程中,在一定的时间段内或一定的条件下,重复地执行重复地
18、执行某个功能,直到时间已到或条件不再满足。某个功能,直到时间已到或条件不再满足。3.2结构化算法的三种结构结构化算法的三种结构3.3 结构化算法的描述方法常用的描述方法有自然语言、流程图、伪代码等。3.3.1 自然语言自然语言 用类自然语言表示算法。如:汉语、英语或其他语言。特点:通俗易懂,简单明了。【例3-2】从键盘输入两个变量的值a、b,请按输入值从小到大的顺序将这两个变量的值输出到屏幕。请写出这个问题的算法描述。算法描述:第1步:输入变量a和b的值;第2步:比较a和b的值;如果a大于等于b,则先输出a,再输出b;否则,先输出b,再输出a;第3步:算法结束。【例3-3】几何级数求和:sum
19、=1+2+3+4+5+(n1)+n。请写出该问题的算法。算法描述:第1步:给定一个大于0的正整数n的值;第2步:定义一个整型变量i,设其初始值1;第3步:定义整型变量sum,其初始值设置为0;第4步:如果i小于等于n,则转第5步,否则执行第8步;第5步:将sum的值加上i的值后,重新赋值给sum;第6步:将i的值加1,重新赋值给i;第7步:执行第4步;第8步:输出sum 的值;第9步:算法结束。思考:思考:该问题的其他描述。该问题的其他描述。用自然语言描述算法的缺陷。用自然语言描述算法的缺陷。3.3.2 流程图流程图流程图是一种算法的形象表示。流程图是由流程线流程线和几何图形框几何图形框连接而
20、成的。算法流程图的符号采用美国国家标准化协会(ANSI)规定的一些常用符号:开始框开始框判断框判断框结束框结束框执行框执行框数据框数据框连接符连接符流程线流程线算法流程图的3种基本结构:顺序结构、分支结构、循环结构1.顺序结构顺序结构顺序结构是一种简单的线性结构,根据流程线所示的方向,按顺序执行各矩形框的指令。基本流程图:注:注:指令A、指令B、指令C可以是一条或多条指令。执行顺序:ABC。2.分支结构分支分支结构结构要对给定的条件进行判断,看是否满足给定的条件,根据条件结果的真假而分别执行不同的执行框。基本流程图有两种:注:注:(1)虚线框表示可将分支结构看成一个矩形框。(2)指令A、指令B
21、可以是一条或多条指令,也可以是分支结构。3.循环结构循环循环结构结构是在条件为真的情况下,重复执行某个执行框中的内容。基本流程图有两种:注:注:(1)虚线框表示可将循环结构看成一个矩形框。(2)指令A称为循环体,可以是一条或多条指令,也可以是其 他分支或循环结构。(3)do_while结构可以转化成while结构。(1)while 循环:(2)do_ while 循环:循环结构的特点:在循环体指令A中必须要有对条件的值进行修改的语句,使得经过有限次循环后,循环一定能结束。while型循环中循环体可能一次都不执行,而do_while型循环则至少执行一次循环。do_while型循环可以转化成为wh
22、ile型循环结构,但while型循环不一定能转化为do_while型循环。关于结构化流程图的规则:1.可分别将顺序结构、分支结构、循环结构的基本流程图看成是一个执行框。2.任何两个按顺序的执行框可以合并为一个执行框。反复运用规则1和规则2可得到结构化流程图的最简形式:【例3-4】从键盘输入3个数,找出其中最小的那个数,将其输出到屏幕。下列用流程图表示的算法是否符合结构化的标准。运用规则【例3-5】从键盘输入两个整型变量a,b的值,按输入值从小到大的顺序输出到屏幕。用流程图来表示算法为:【例3-6】计算几何级数的和:sum=1+2+3+4+5+(n1)+n。用流程图来表示算法为:3.3.3 伪代
23、码伪代码伪代码是一种接近于程序语言的算法描述方法。特点:特点:采用有限的英文单词作为伪代码的符号系统,按照特定的格式来表达算法,可读性好,方便将算法改写成计算机的程序源代码。伪代码的伪代码的7 7个主要部分:个主要部分:(1)算法名称(2)指令序列(3)输出/输出(4)分支选择(5)赋值(6)循环(7)算法结束1算法名称算法名称 两种表示算法的伪代码:过程(Procedure)函数(Function)过程和函数的区别是:过程是执行一系列的操作,不需要返回操作的结果,无返回数据;函数是执行一系列的操作后,要将操作的结果返回,有返回数据。算法伪代码的书写规则:Procedure ()Functio
24、n ()如:Procedure Hanoi_Tower()表示名为Hanoi_Tower的一个过程。Function Fac(x)表示名为Fac的一个函数。Function Prog(n)表示名为Prog的一个函数。2指令序列指令序列指令序列是算法的主体。指令序列的书写规则:用Begin作为开始、用End作为结束;用“”作为开始、用“/”作为结束。例如:Begin 指令序列;End或者:指令序列;/3输出输出/输出输出输入:Input输出:Output 或 Return4分支选择分支选择两种分支:If Then 指令序列 /If Then 指令序列1 /else 指令2 /5赋值赋值用:=或者
25、作为赋值操作符,表示将赋值号右边的值赋值给左边的变量。例如:x:=x+1 或:yx*x6循环循环两种方式:计数式循环计数式循环和条件式循环条件式循环。(1)计数式循环 For 变量:=初值 To 终值 指令 循环次数:(终值初值+1)(2)条件式循环 While(条件)do 指令 条件为真,则循环执行指令,直到条件为假。7算法结束算法结束关键字End的后面加上算法名称,表示算法结束,是算法的最后一句。例如:End Hanoi_Tower End Fac 分别表示算法Hanoi_Tower和Fac的结束。【例3-8】从键盘输入3个数,将其中最小的那个数输出到屏幕。用函数伪代码表示算法如下:Fun
26、ction Minimal(a,b,c)Begin If(ab)min=a;Else min=b;If(cb)Output a,b;Else Output b,a;End PrtMin思考:怎样用函数来表示该算法。【例3-10】求几何级数求和:sum=1+2+3+4+5+(n1)+n。用函数表示的伪代码算法如下:Function Total(n)Begin i1;sum0;While(i=n)do sum sum+i;ii+1;/Return sum;End Total【例3-11】把从键盘输入的大写字母转换成小写字母输出,若为小写字母或其他字符,则不作任何转换直接输出。分析:用字符变量ch来
27、接收从键盘输入的字符。大、小写字母的ASCII码值相差32,大写字母A的值为65,而小写字母a的值为97。流程图描述的算法:【例3-12】已知实数a,b,计算u的值:u=(r+s)2,并将计算结果输出到屏幕。当a0,这样一来就不用去判别该一元二,这样一来就不用去判别该一元二次方程是否有实根了。次方程是否有实根了。#include#include#include#include main()main()float a,b,c,disc,x1,x2,p,q;float a,b,c,disc,x1,x2,p,q;scanf(ascanf(a=%=%f,bf,b=%=%f,cf,c=%=%f,&a,&
28、b,&cf,&a,&b,&c););disc=b*b-4*a*c;disc=b*b-4*a*c;p=-b/(2*a);p=-b/(2*a);q=sqrt(disc)/(2*a);q=sqrt(disc)/(2*a);x1=x1=p+qp+q;x2=x2=p-qp-q;printf(nx1=%5.2fnx2=%5.2fn,x1,x2);printf(nx1=%5.2fnx2=%5.2fn,x1,x2);程序运行时若输入:a=1,b=3,c=2 则输出为:x1=-1.00 x2=-2.00【例例例例】输入一个三位数,依次输出该数的正号或负号、百位、输入一个三位数,依次输出该数的正号或负号、百位、输
29、入一个三位数,依次输出该数的正号或负号、百位、输入一个三位数,依次输出该数的正号或负号、百位、十位、个位数字。十位、个位数字。十位、个位数字。十位、个位数字。#include main()char c1,c2,c3,c4;int x;scanf(%d,&x);/*/*输入输入1 1个个3 3位数的整数位数的整数*/if(x=0)c4=+;else c4=-;x=abs(x);c3=x%10+48;/*x%10/*x%10获得个位数字后加获得个位数字后加4848转换成对应字符转换成对应字符*/x=x/10;/*/*取得取得x x的前两位数字的前两位数字*/c2=x%10+48;/*x%10/*x
30、%10获得十位数字,加获得十位数字,加4848后转换成对应后转换成对应字符字符*/c1=x/10+48;/*x%10/*x%10获得百位数字,加获得百位数字,加4848后转换成对应字符后转换成对应字符*/printf(%cn%cn%cn%cn,c4,c1,c2,c3);例:例:编写程序,编写程序,键盘输入两个数存储起来,要求交换后键盘输入两个数存储起来,要求交换后实现输出。实现输出。main()int x1,x2,temp;printf(“input x1,x2n”);scanf(“%d%d”,&x1,&x2);/*键盘输入两个数分别键盘输入两个数分别赋予赋予x1,x2变量变量*/temp=x
31、1;x1=x2;x2=temp;printf(“after:x1=%dx2=%dn”,x1,x2);例例4-9:编写程序,要求把一个三位正整数逆序输出编写程序,要求把一个三位正整数逆序输出(如(如234,输出为,输出为432)。)。例例:输入一个数输入一个数3位正整数位正整数,取出其中的各位数取出其中的各位数字按逆序输出字按逆序输出.ain()int a,x,y,z;/*从键盘输入一个三位的正整数从键盘输入一个三位的正整数,赋予赋予a变量变量*/scanf(“%3d”,&a);x=a/100;/*取出取出a的百位数的百位数,赋予赋予x变量变量*/y=a%100/10;/*取出取出a的十分位数的
32、十分位数,赋予赋予y变量变量*/z=a%10;/*取出取出a的个位数的个位数,赋予赋予z 变量变量*/printf(“%d%d%dn”,z,y,x);运行时若输入:运行时若输入:789 则结果:则结果:987在上例中,程序执行时,首先要求输入一在上例中,程序执行时,首先要求输入一个三位数,再依次求出百位、十位、个位个三位数,再依次求出百位、十位、个位分别赋给分别赋给x、y、z变量,最后逆序输出个变量,最后逆序输出个位、十位、百位。程序执行是按语句出现位、十位、百位。程序执行是按语句出现的先后次序进行的。的先后次序进行的。例例:已知三角形的三边已知三角形的三边,求三角形的面积。求三角形的面积。从
33、数学知识知从数学知识知 求三角形面积的公式为求三角形面积的公式为 area=sqrt(s*(s a)*(s b)*(s c)其中其中s=(a+b+c)/2共需要变量共需要变量5个:三条边个:三条边a,b,c 周长的一半周长的一半 s 面积面积 area这些变量的值均为实数,可以用这些变量的值均为实数,可以用float 类型类型需要调用一个数学函数:需要调用一个数学函数:sqrt源程序代码如下:源程序代码如下:#include /*#include “math.h”*/main()float a,b,c,s,area;scanf(“%f,%f,%f”,&a,&b,&c);s=1.0/2*(a+b+c);area=sqrt(s*(s-a)*(s-b)*(s-c);printf(“nna=%7.2f,b=%7.2,c=%7.2,s=%7.2”,a,b,c,s);printf(“nnarea=%7.2f”,area);运行情况如下:运行情况如下:3,4,6 /*输入数据输入数据*/a=3.00,b=4.00,c=6.00,s=6.50,area=5.33这里不能写成:这里不能写成:s=1/2*(s=1/2*(a+b+ca+b+c););为什么?为什么?/*/*这里使用了数学函数这里使用了数学函数sqrtsqrt*/
限制150内