下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 02_第02章程序的灵魂——算法

02_第02章程序的灵魂——算法.ppt

02_第02章程序的灵魂——算法

tianxingmeizhou
2010-12-15 0人阅读 举报 0 0 暂无简介

简介:本文档为《02_第02章程序的灵魂——算法ppt》,可适用于工程科技领域

第二章程序的灵魂算法第二章程序的灵魂算法程序设计概述程序设计概述一个程序应包括对数据的描述和对数据处理的描述。.对数据的描述即数据结构。数据结构是计算机学科的核心课程之一有许多专门著作论述本课程就不再赘述。在C语言中系统提供的数据结构是以数据类型的形式出现的。程序设计概述程序设计概述.对数据处理的描述即计算机算法。算法是为解决一个问题而采取的方法和步骤是程序的灵魂。为此著名计算机科学家沃思(NikiklausWirth)提出一个公式:数据结构算法=程序实际上一个程序除了数据结构和算法外还必须使用一种计算机语言并采用结构化方法来表示。算法的概念算法的概念算法:是指解决一个具体问题的意义明确的步骤的集合。是有限的概括地说算法是指解题方案的准确而完整的描述。从程序来说也可以说算法是一个有限条指令的集合这些指令确定了解决某一特定类型问题的运算序列。对于同一个问题可以有不同的解题方法和步骤也就是有不同的算法。算法有优劣一般而言应当选择简单的、运算步骤少的既运算快、内存开销小的算法(算法的时空效率)。、简单算法举例、简单算法举例例求××××可先写出这样的算法:()先求×得到结果()将步骤得到的结果再乘以得到结果()将再乘以得到()将再乘以得到。上述算法太繁琐我们找一种通用的表示方法。S:设变量p被乘数p=s:设变量i,代表乘数i=s:使p×i,乘积放在被乘数变量p中,可表示为:p×ips:使i的值加即iis:如果i不大于返回重新执行步骤s以及其后的s、s否则算法结束。最后得到的p就是!的值。例求×××××如果题目改为求×××××。上述算法稍作改动:s:>ps:>is:p×i>ps:i>is:若i<=,返回s否则结束。例有个学生要求将他们之中成绩在分以上者打印出来。解:用n表示学生学号n代表第一个学生学号ni代表第i个学生学号。用g代表学生成绩gi代表第i个学生成绩算法表示如下:S:>iS:如果gi>=,则打印ni和gi,否则不打印。S:i>iS:如果i<=,返回s,继续执行否则算法结束。本例中变量i作为下标用它来控制序号(第几个学生第几个成绩)。当i超过时表示已对个学生的成绩处理完毕算法结束。例求下列级数的值可以写出下面的算法()使S=(S作为累加变量)()使N=(N代表分母)()SN>S(执行迭代S为迭代变量)()N>N()若N≤转去执行()以及其后的各步骤否则执行()()打印S的值(即所求之总和)。算法的特性算法的特性、有穷性:一个算法应当包含有限的步骤而不能是无限的步骤同时一个算法应当在执行一定数量的步骤后算法结束不能死循环。事实上“有穷性”往往指“在合理的范围之内”的有限步骤。如果让计算机执行一个历时年才结束的算法算法尽管有穷但超过了合理的限度人们也不认为此算法是有用的。 、确定性:算法中的每一个步骤都应当是确定的而不是含糊的、摸棱两可的。也就是说不应当产生歧义。特别是算法用自然语言描述时应当注意这点。例如:“将成绩优秀的同学名单打印输出”就是有歧义的。“成绩优秀”是要求每门课程都分以上还是平均成绩在分以上?不明确有歧义不适合描述算法步骤。、有个或多个输入(即可以没有输入,也可以有输入)所谓输入是指算法执行时从外界获取必要信息。(外界是相对算法本身的输入可以是人工键盘输入的数据也可以是程序其它部分传递给算法的数据)例如:不需要输入任何信息就可以计算出!(个输入)例如:如果要计算两个整数的最大公约数则需要输入个整数mn。(个输入) 、有个或多个输出(即算法必须得到结果)算法的输出:算法得到的结果。算法必须有结果没有结果的算法没有意义。(结果可以是显示在屏幕上的也可以是将结果数据传递给程序的其它部分)、有效性算法的每个步骤都应当能有效执行并能得到确定的结果。例如:b=则执行ab是不能有效执行的。怎样表示一个算法?怎样表示一个算法?为了表示一个算法可以用不同的方法。常用的算法表示方法:自然语言传统流程图结构化流程图(NS流程图)伪代码、计算机语言等。(重点:传统流程图NS流程图)用自然语言表示算法用自然语言表示算法自然语言就是人们常用的语言可以是汉语、英语或其他语言。用自然语言表示通俗易懂但文字冗长容易出现“歧义”性而且用自然语言描述包含分支和循环的算法不很方便。一般不使用自然语言描述算法自然语言描述举例例如:描述计算并输出z=yx的流程可以用自然语言描述如下:()输入xy。()判断x是否为:若X=,则输出错误信息否则计算yx>z且输出z。算法描述语言算法描述语言:是为了说明程序的流程而专门规定的某种语言。它一般介于自然语言与程序设计语言之间它具有自然语言灵活的特点同时又接近于程序设计语言的描述。◆注意:算法描述语言所描述的流程一般不能直接作为程序来使用最后还需转换成用某种程序设计语言所描述的程序。◆与程序设计语言的区别:前者比较自由不象后者那样受语法的约束只要描述得人们能理解就行而不必考虑计算机处理时所要遵循的规定或其它一些细节。用流程图表示算法用流程图表示算法一、流程的描述在程序设计过程中一般不可能在一开始就用某种程序设计语言编制计算机程序而是先用某种简单、直观、灵活的描述工具来描述处理问题的流程。当方案确定以后再将这样的流程转换成计算机程序这种转换往往是机械的已经不涉及功能的重新设计或控制流程的变化而只需考虑程序设计语言所规定的语法要求以及一细节问题。流程图:用一些约定的几何图形来描述算法。用某种图框表示某种操作用箭头表示算法流程流程图(的符号及意义)美国标准化协会ANSI规定了一些常用的流程图符号已为世界各国程序工作者普遍采用起止框输入输出框判断选择框处理框流程线连接点……注释框处理框:表示算法的某个处理步骤一般内部常常填写赋值操作。输入输出框:表示算法请求输入输入需要的数据或算法将某些结果输出。一般内部常常填写“输入…”,“打印显示…”起止框:表示算法的开始和结束。一般内部只写“开始”或“结束”。菱形框(判断框):作用主要是对一个给定条件进行判断根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口两个出口。连接点:用于将画在不同地方的流程线连接起来。同一个编号的点是相互连接在一起的实际上同一编号的点是同一个点只是画不下才分开画。使用连接点还可以避免流程线的交叉或过长使流程图更加清晰。……注释框:注释框不是流程图中必须的部分不反映流程和操作它只是对流程图中某些框的操作做必要的补充说明以帮助阅读流程图的人更好地理解流程图的作用。例:求!t=i=t=t*ii=ii>结束NY开始传统流程图的优缺点传统流程图的优缺点传统流程图采用流程线指出各框的执行顺序对流程线的使用没有严格限制。因此使用者可以不受限制地使流程转来转去使流程图变得毫无规律。人们对这种流程图进行改进规定几种基本的结构然后由这些基本结构按一定规律组成算法结构整个算法结构是由上而下地将各个基本结构顺序排列起来。这样可以在一定程度上提高算法的质量。三种基本结构和改进的流程图三种基本结构和改进的流程图三种基本结构是:()顺序结构按指令的顺序依次执行()判断选择结构根据判别条件有选择地改变执行流程()循环结构有条件的重复地执行某个程序块()顺序结构程序设计()顺序结构程序设计依次顺序执行程序语句执行a块执行b块a块b块AB传统流程图NS流程图()判别选择结构程序设计()判别选择结构程序设计首先判别条件,若条件满足,程序执行a块,否则,执行b块条件成立?执行a块执行b块成立不成立满足条件否满足不满足执行a块执行b块传统流程图NS流程图()循环结构程序设计()循环结构程序设计循环又分“当型循环”和“直到型循环”条件成立?执行循环体成立不成立条件成立?执行循环体成立不成立直到条件满足为止执行循环中的指令当条件满足时执行循环中指令当型直到型举例求~的累加和。intisum=while(i<=){sum=sumii=i}i<=?sum=sumii=i成立不成立i<=?sum=sumii=i三种基本结构有以下共同点:三种基本结构有以下共同点:只有一个入口:不得从结构外随意转入结构中某点。只有一个出口:不得从结构内某个位置随意转出(跳出)。结构中的每一部分都有机会被执行到。(没有“死语句”)结构内不存在“死循环”(无终止的循环)已经证明:由三种基本结构顺序组成的算法结构可以解决任何复杂问题。由基本结构组成的算法属于“结构化”算法。用NS流程图表示算法用NS流程图表示算法基本结构的顺序组合可以表示任何复杂的算法结构那么基本结构之间的流程线就属于多余的了于是美国学者INasii和Bshneiderman于年提出了一种新的流程图形式。全部算法写在一个矩形框内完全去掉了带箭头的流程线。这种流程图称为NS结构化流程图(盒图)。NS流程图适于结构化程序设计。顺序结构程序设计顺序结构程序设计依次顺序执行程序语句执行a块执行b块先执行a操作再执行b操作判别选择结构程序设计判别选择结构程序设计当条件成立执行a操作当条件不成立执行b操作。ab操作允许空操作即什么都不做。注意选择结构是一个整体代表一个基本结构。满足条件否满足不满足执行a块执行b块循环结构程序设计循环结构程序设计循环又分“当型循环”和“直到型循环”当条件p满足时执行循环中指令直到条件p满足为止执行循环中的指令例:求!的算法用NS图表示tiT*Itii直到i>打印t用伪代码表示算法用伪代码表示算法用伪代码表示算法(常常用于算法设计)用传统流程图、NS图表示算法直观易懂但绘制比较麻烦在设计一个算法时可能要反复修改而修改流程图是比较麻烦的因此流程图适合表示算法但在设计算法过程中使用不是很理想。为了设计算法方便常使用伪代码工具。伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。伪代码不用图形符号书写方便格式紧凑便于向计算机语言算法过渡用计算机语言表示算法用计算机语言表示算法用某种程序设计语言编写的程序本质上也是问题处理方案的描述并且是最终的描述。在一般的程序设计过程中不提倡一开始就编写程序特别是对于大型的程序。程序是程序设计的最终产品需要经过每一步的细致加工才能得到如果企图一开始就编写出程序往往会适得其反达不到预想的结果。例求!用C语言表示main(){inti,tt=i=while(i<=){t=t*ii=i}printf(“d”,t)}

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/33

02_第02章程序的灵魂——算法

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利