第一讲-算法的描述与评价.ppt

数据结构与算法设计第一章数据结构与算法的引入1第一章内容简介第五节数据结构中的基本术语第一节算法的描述与评价第二节Pascal语言中的数据类型第三节建立数学模型第四节程序的调试数据结构与算法设计2概论“程序=算法+数据结构”是由著名的计算机科学家沃斯(N·Writh)提出的程序公式,简明的概括了程序的组成。从中可以看出,编程解决各种各样的实际问题,只学****掌握好诸如pascal、C等程序设计语言是远远不够的,另外还必须具备数据结构和算法的相关知识。数据结构主要讲述客观世界中纷繁复杂的事物及其内在的联系如何有效地在计算机中进行表示;算法主要讲解建立在这种表示基础上的一些常用的解决实际问题的思想、方法和步骤。二者是一个相辅相成的统一体,是缺一不可的两个方面。有了它们以后,我们才能比较顺利地编写程序。3数据结构与算法的密切关系数据结构是建立在算法的基础上,而选择什么样的数据结构对于程序设计来说,是至关重要的决策,它直接影响到程序的效率。选择一个合适的数据结构便很容易形成一个简洁有效的算法;否则,如果数据结构选择不好,除了影响程序开发速度之外,更重要的是影响设计出来的程序的运行效率。概论4第一节算法的描述与评价第一节算法的描述与评价5算法什么是“算法”?算法是为解决一个问题而采用的方法和步骤。或者说,算法是解题方法的精确描述,解决一个问题的过程就是实现一个算法的过程。,不能含糊其辞,不能存在歧义,否则就会使执行者无所适从。如计算”3/0”或”将3或4与X相乘”等是不允许的。、可行性一个算法必须包含有限个操作步骤,即执行若干步之后,算法能够终止,而不能无限地执行下去。当然,这种有穷性还应该在一个合理的范围之内,即在有限的时间内做完。比如一个算法要执行一万年才能得到结果,尽管它不是无限的,但显然没有什么实际意义。(可行性与确定性、有穷性是相容的。),整个算法执行完毕后必须得到确定的结果。例如,求-5的平方根,求所有自然数的和,就无法在计算机上有效地执行。,这些输入信息是算法所需的初始数据,取自某一特定的集合。,他们通常可以被解释为“对输入的计算结果。”7算法的描述描述算法的方法,常用的有自然语言、程序流程图、N-S图、类程序设计语言和程序设计语言等。(1)用自然语言描述算法(2)用流程图来描述算法框图结构化流程图(N-S图)(3)用程序语言来描述算法8(1)用自然语言描述算法自然语言主要是通过文字或数学式来描述解决问题的过程。例如:交换X、Y的值。第一步:给X、Y分别赋初值;第二步:把X的值送给A;第三步:把Y的值送给X;第四步:把X的值送给Y;这种描述通俗易懂,但比较繁琐,容易出现二义性,对算法中的判断和转移等描述的不够直观清楚。9(2)用流程图来描述算法所谓流程图法,就是指用图形来表示程序的方法,它采用一些几何图形来代表各种性质的操作,是程序设计中广泛使用的一种辅助设计手段。流程图主要有两种模式:框图和结构化流程图(N-S图)10