第2章算法--C语言程序设计(谭浩强第三版).ppt
- 文档编号:10917605
- 上传时间:2023-05-28
- 格式:PPT
- 页数:36
- 大小:637.50KB
第2章算法--C语言程序设计(谭浩强第三版).ppt
《第2章算法--C语言程序设计(谭浩强第三版).ppt》由会员分享,可在线阅读,更多相关《第2章算法--C语言程序设计(谭浩强第三版).ppt(36页珍藏版)》请在冰点文库上搜索。
1,高级语言程序设计(c),2,第二章算法,3,引言:
一、一个程序应包括两个方面的内容:
对数据的描述:
数据结构(datastructure)对操作的描述:
算法(algorithm),著名计算机科学家沃思提出一个公式:
数据结构+算法=程序,数据结构算法程序设计方法语言工具,完整的程序设计应该是:
描述数据的类型、数据的组织形式,描述对数据的操作步骤,程序设计方法:
结构化程序设计方法语言工具:
c语言,4,二、简单的程序设计一般包括:
1、确定数据结构2、确定算法3、编码4、调试程序5、整理并写出文档资料,5,2.1算法的概念,例如:
描述太极拳动作的图解,就是太极拳的算法。
一首歌曲的乐谱,也可以称为该歌曲的算法。
1、算法定义:
广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”。
2、对同一个问题,可以有不同的解题方法和步骤。
算法决定事情的成败、效率和代价的高低。
算法的时空效率选择既运算快、内存开销小的算法,3、计算机算法可分为两大类别:
数值运算算法:
求数值解,例如求方程的根非数值运算算法:
包括的面十分广泛,如图书检索、人事管理、行车调度管理等。
高斯算法,6,2.2算法的特性,
(1)有穷性。
一个算法应包含有限的操作步骤,不能是无限的。
(2)确定性。
算法中的每一个步骤都应当是确定的,而不应当是含糊的、模棱两可的。
对于相同输入必须得到相同结果。
(3)有零个或多个输入。
所谓输入是指在执行算法时需要从外界取得必要的信息。
(4)有一个或多个输出。
算法的目的是为了求解,“解”就是输出。
(5)有效性。
算法中的每一个步骤都应当能有效地执行,并得到确定的结果。
7,2.3算法的表示,为了表示一个算法,可以用不同的方法。
归纳为两大类:
(1)文字
(2)图形(符号)常用的方法有:
自然语言传统流程图N-S流程图伪代码PAD图等。
8,2.3.1用带序号的自然语言直接表示算法(例2.1-例2.5),自然语言就是人们日常使用的语言,可以是汉语或英语或其它语言。
用自然语言表示通俗易懂,但文字冗长,容易出现“歧义性”。
9,例2.1求12345算法1:
步骤1:
先求12,得到结果2。
步骤2:
将步骤1得到的乘积2再乘以3,得到结果6。
步骤3:
将6再乘以4,得24。
步骤4:
将24再乘以5,得120。
如果要求121000,则要写999个步骤算法2:
上述算法太繁琐,我们找一种通用的表示方法。
s1:
设变量p,代表被乘数,p=1;s2:
设变量i,代表乘数,i=2;s3:
使pi,乘积仍放在被乘数变量p中,可表示为:
pip;s4:
使i的值加1,即i+1i;s5:
如果i不大于5,返回重新执行步骤s3以及其后的s4、s5;否则,算法结束。
最后得到的p就是5!
的值。
10,求1357911上述算法稍作改动:
s1:
1p;s2:
3i;s3:
pip;s4:
i+2is5:
若i11,返回s3;否则,结束。
用这种方法表示的算法具有通用性、灵活性。
s3到s5组成一个循环,在实现算法时,要反复多次执行s3、s4、s5等步骤,直到某一时刻,执行s5步骤时经过判断,乘数i已超过规定的数值而不返回s3步骤为止。
此时,算法结束,变量P的值就是结果。
计算机实现循环是轻而易举。
所有高级语言中都有实现循环的语句。
11,例2.2有50个学生,要求将他们之中成绩在80分以上的学号和成绩输出,ni代表第i个学生学号。
gi代表第i个学生成绩,算法如下:
S1:
1iS2:
如果gi80,则输出ni和gi;否则不输出S3:
i+1iS4:
如果i50,返回S2,继续执行;否则,算法结束。
本例中,变量i作为下标,用它来控制序号(第几个学生,第几个成绩)。
当i超过50时,表示已对50个学生的成绩处理完毕,算法结束。
12,例2.3判定2000-2500年中的每一年是否是闰年,闰年的条件是:
(1)能被4整除,但不能被100整除的年份是闰年,如1996年、2004年;
(2)能被400整除的年份是闰年,如1600年、2000年。
设y为被检测的年份。
可采用以下步骤:
S1:
2000yS2:
若y不能被4整除,则输出“y不是闰年”。
然后转到S6S3:
若y能被4整除,不能被100整除,则输出“y是闰年”。
然后转到S6S4:
若y能被400整除,输出“y是闰年”,然后转到S6S5:
输出“y不是闰年”S6:
y+1yS7:
当y2500时,转S2继续执行,否则算法停止。
13,例2.4求1-1/2+1/3-1/4+1/99-1/100,算法如下:
S1:
sign=1;/作为加数符号S2:
sum=1;/sum作为累加变量S3:
deno=2;/作为加数分母S4:
sign=(-1)*signS5:
term=sign*(1/deno)/term作为加数S6:
sum=sum+termS7:
deno=deno+1S8:
若deno100返回S4;否则算法结束。
14,2.3.2用流程图表示算法,流程图:
用一些约定的几何图形来描述算法。
用某种图框表示某种操作,用箭头表示算法流程。
美国国家标准化协会ANSI(AmericanNationalStandardInstitute)规定了一些常用的流程图符号:
15,例2.6将例2.1求5!
的算法用流程图表示,用图框来表示各种算法:
灵活、自由、直观、形象、直观,可表示任何算法。
16,2.3.3三种基本结构和改进的流程图,1.传统流程图的弊端传统流程图用流程线指出各框的执行顺序,对流程线的使用没有严格限制。
因此,使用者可以毫不受限制地使流程随意地转向,使流程图变得毫无规律。
如图:
解决办法:
必须限制箭头的滥用,即不允许无规律地使流程随意转向,只能顺序地进行下去,改进为:
只有三种基本结构的流程图,17,2.三种基本结构1966年,Bohra和Jacopini提出了以下三种基本结构:
顺序结构、选择结构、循环结构用这三种基本结构作为表示一个良好算法的基本单元。
现在:
任何复杂的算法都是由这三种基本结构按一定规律组成。
18,三种基本结构的图示:
顺序结构,19,选择结构,菱形代表条件判断,分段函数intmax(intx,inty)if(xy)z=x;elsez=y;,20,循环结构的图示:
当型(While型)循环结构,直到型(Until型)循环,21,三种基本结构,有以下共同点:
(1)只有一个入口:
不得从结构外随意转入结构中某点。
(2)只有一个出口:
不得从结构内某个位置随意转出(跳出)。
(请注意:
一个菱形判断框有两个出口,而一个选择结构只有一个出口。
不要将菱形框的出口和选择结构的出口混淆。
)(3)结构中的每一部分都有机会被执行到。
(没有“死语句”)(4)结构内不存在“死循环”(无终止的循环)已经证明:
由三种基本结构顺序组成的算法结构,可以解决任何复杂问题。
由基本结构组成的算法属于“结构化”算法。
22,扩展:
只要具有上述四个特点的都可以作为基本结构。
可以自己定义基本结构,并由这些基本结构组成结构化程序。
23,例2.6将求5!
的算法用流程图表示,如果需要将最后结果打印出来,可在菱形框的下面加一个输出框。
24,2.3.4用N-S流程图表示算法,1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式。
在这种流程图中,完全去掉了带箭头的流程线。
全部算法写在一个矩形框内,在该框内还可以包含其它的从属于它的框,或者说,由一些基本的框组成一个大的框。
这种流程图又称N-S结构化流程图。
25,
(1)顺序结构:
A和B两个框组成一个顺序结构。
(2)选择结构:
当条件p成立时执行操作A,条件p不成立则执行操作B。
26,(3)循环结构:
当型循环结构下,图符表示先判断后执行,当条件p成立时反复执行操作A,直到条件p不成立为止。
直到型循环结构下,图符表示先执行后判断,当条件p不成立时反复执行A操作,直到p条件成立为止。
27,用三种N-S流程图中的基本框,可以组成复杂的N-S流程图。
图中的A框或B框,可以是一个简单的操作,也可以是三个基本结构之一。
A框可以是一个选择结构,B框可以是一个循环结构,28,例2.11求5!
算法用N-S图表示,29,2.3.5用伪代码表示算法,用伪代码表示算法(常常用于算法设计)用传统流程图、N-S图表示算法,直观易懂,但绘制比较麻烦,在设计一个算法时,可能要反复修改,而修改流程图是比较麻烦的,因此,流程图适合表示算法,但在设计算法过程中使用不是很理想。
为了设计算法方便,常使用伪代码工具。
伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。
伪代码不用图形符号,书写方便,格式紧凑,便于向计算机语言算法过渡。
30,开始置t的初值为1置i的初值为2当i=5,执行下面操作:
使t=ti使i=i+1循环体到此结束输出t的值结束,也可以写成以下形式:
BEGIN算法开始1t2iwhilei5titi+1iprinttEND算法结束,例2.16求5!
。
用伪代码表示算法:
31,2.3.6用计算机语言表示算法,概念:
用计算机实现算法。
计算机是无法识别流程图和伪代码的。
只有用计算机语言编写的程序才能被计算机执行。
因此在用流程图或伪代码描述出一个算法后,还要将它转换成计算机语言程序。
特点:
用计算机语言表示算法必须严格遵循所用的语言的语法规则,这是和伪代码不同的。
用处:
要完成一件工作,包括设计算法和实现算法两个部分。
设计算法的目的是为了实现算法。
32,#includevoidmain()inti,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(“%dn”,t);,例2.20将例2.16表示的算法(求5!
)用C语言表示。
33,2.4结构化程序设计方法,结构化程序设计方法强调程序设计风格和程序结构的规范化,提倡清晰的结构。
一个复杂的问题,难以一下子写出一个层次分明、结构清晰、算法正确的程序。
结构化程序设计方法的基本思路是:
把一个复杂的问题的求解过程分阶段进行,每个阶段处理的问题都控制在人们容易理解和处理的范围内。
为保证程序满足结构化程序设计,可以采取如下方法:
自顶向下逐步细化模块化设计结构化编码,34,对于一个具体问题一般有两种方法自顶向下、逐步细化自下而上、逐步积累例如:
写文章、建造房屋提倡采用自顶向下、逐步细化的程序设计方法,其过程是将问题求解由抽象逐步具体化的过程。
特点:
考虑周全,结构清晰,层次分明,作者容易写,读者容易看。
如果发现某一部分中有一段内容不妥,需要修改,只需找出该部分修改有关段落即可,与其它部分无关。
注意:
用这种方法便于验证算法的正确性,在向下一层展开之前应仔细检查本层设计是否正确,只有上一层是正确的才能向下细化。
35,模块设计的方法是一种“分而治之”的思想,把一个大任务分为若干个子任务,每一个子任务就相对简单了。
拿到一个程序模块以后,根据程序模块的功能将它划分为若干个子模块,如果这些子模块的规模还嫌大,还再可以划分为更小的模块。
这个过程采用自顶向下方法来实现。
子模块一般不超过50行。
划分子模块时应注意模块的独立性,即:
使一个模块完成一项功能,耦合性愈少愈好。
结构化编码将设计好的算法用计算机语言来实现,实现时使用的是与三种基本结构对应的语句。
36,作业,教材p121.3、1.5教材p3624(4)、2.5(4)2.7,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 语言程序设计 谭浩强 第三