第03章 计算机软件技术基础—算法与数据结构-new

《第03章 计算机软件技术基础—算法与数据结构-new》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第03章计算机软件技术基础—算法与数据结构-new本文由xufeng3804贡献ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。计算机软件技术基础(3)(3)算法与数据结构计算机软件技术基础设计程序首先要研究要解决的问题，提出适当的计算模型并列出解决问题的方法和步骤。模型一旦建立起来，就要选择合适的算法，并将解题步骤表述出来；同时需要确定合适的数据结构本章着重讨论解决问题的核心--算法以及算法的处理对象--数据的结构如何解决农夫过河问题一个农夫带着一只狼、一只羊和一棵白菜，身处河南岸，要把东西全部运到北岸。约束条件是只有一条能容下他和

2、一件物品的小船，只有农夫能撑船。不能单独留下羊和白菜，也不能单独留下羊和狼，狼不爱吃白菜。计算机软件技术基础3.1算法解题过程的准确、完整的描述称作解该问题的算法算法程序就是用计算机语言表述的算法，流程图程序流程图就是图形化了的算法流程图著名计算机科学家、PASCAL语言发明者N·沃思(NiklausWirth)教授进一步提出如下的著名公式：程序＝算法＋数据结构——不能离开数据结构去抽象地分析程序的算法，也不能脱离算法去孤立地研究程序的数据结构，而只能从算法与数据结构的统一上去认识程序计算机软件技术基础3.1.1算法的两要素算法由操作与控制结构两要素组成1.操作(1)逻

3、辑运算：“与”、“或”、“非”；(2)算术运算：加、减、乘、除；(3)数据比较：大于、小于、等于、不等于；(4)数据传送：输入、输出、赋值。计算机软件技术基础2.控制结构算法的控制结构，决定了各操作的执行次序。用流程图可以形象地表示出算法的控制结构任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成（1966年，Bohm和Jacopini证明）S1S2S3BS1S2SBTFBTSF(a)(b)(c)(d)3.1.2算法的特征1.算法是由一套计算规则组成的一个过程2.组成算法的规则是确定的、可执行的3.每种算法必须有确定的结果，产生一个或多个输出4.每个算法必须有0

4、个（自动生成初始数）或多个输入5.解答必须在有限步内得到,不能出现“死循环”我们可以得出如下的结论：算法是一个过程，这个过程由一套明确的规则组成，这些规则指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答3.1.3算法的表示算法设计一般是由粗到细的过程，一般可以使用下面几种类型的工具描述算法:自然语言用自然语言描述算法通俗易懂，但它存在着难以克服的缺陷：易产生歧义性。自然语言往往要根据上下文才能判别其含义，不太严格。语句比较繁琐冗长，并且很难清楚地表达算法的逻辑流程。如果算法中包含判断、循环处理，尤其是这些处理的嵌套层数增多，自然语言描述其流程既不直观又很难表

5、达清楚。当今的计算机尚不能处理用自然语言表示的算法计算机软件技术基础专用工具常用的有流程图、PAD图和N-S图、伪代码等程序设计语言算法描述语言为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。在本书中为类VB语言继续流程图是采用不同的几何图形来描述算法的逻辑结构，每个几何图形表示不同性质的操作常用流程图符号：常用流程图符号：开始结束(a)起止框、连接框A输入a,bAN>10truefalse(b)输入输出框(c)判断框i+1→iN为正整数(d)处理框(e)注释框(f)流向线返回计算机软件技术基础类VB语言一览表计算机软件技术基础类VB语言一览表（续）3

6、.1.4常用算法1.枚举法（穷举法）枚举法（）基本思想是：先依据题目的部分条件确定答案的大致范围在此范围内对所有可能的情况逐一验证，直到全部情况验证完若某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解2.迭代法使一个复杂问题的求解过程转化为相对简单的迭代算式的重复执行过程使用迭代法构造算法的基本方法是：首先确定一个合适的迭代公式，选取一个初始近似值以及解的误差然后用循环处理实现迭代过程，终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差并认为最后一次迭代得到的近似值为问题的解。3.递归法如果一个

7、过程直接或间接地调用它自身，则称该过程是递归的1n=0n>0例：求阶乘。n!＝n(n-1)!Funcfac(nAsInteger)Ifn=1thenfac=1Elsefac=n*fac(n-1)Endif递归过程必须有一个递归终止条件，当n=0时定义为1，是阶乘递归定义的递归出口递归则是从函数本身出发，逐次上溯调用其本身求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值4.递推法所谓递推法，它的数学公式也是递归的。只是在实现计算时与递归相反。从给定边界出发逐步迭代到达指定计算参数。例：求阶乘f(n)＝n!＝n×(n-1)!＝n