11-计算机科学与技术.pptVIP

计算机软件技术基础 第一部分 数据结构与算法基础 第1章 算法 第2章 数据结构的基础 第3章 线性表及其存储结构 第4章 栈和对列 第5章 树与二叉树 第7章 查找与排序 第1章 算法 1.1 算法的基本概念 1.2算法的描述方式 相同的输出； 3)有穷性：算法必须能在有限的时间内做完 即算法必须能在执行有限个步骤之后终止； 4)输入：具有零个或多个输入，它们是算 法开始前的初始量； 5)输出：至少产生一个输出，它们是与输入 有某种关系的量，是算法的执行结果。 ③关系运算：有“大于”、“小于”、“等于”、“不等于”等运算； ④数据传输：有赋值、输入、输出等操作。 ５）减半递推技术 所谓“减半”，是指将问题的规模减半，而问题的性质不变；这里所谓“递推”，是指重复“减半”的过程。 [猜数游戏] * * 机械工业出版社2007年7月 数据结构与算法的学习可以帮助我们更好地进行程序设计，数据结构直接关系到算法选择和程序实现效率。 应用 1)语言编译要使用“栈”—程序中利用“栈”来实现函数过程的调用; 2)操作系统中要用队列—打印队列，当计算机输出的数据用打印机打印时，由于打印机速度慢，此时可设置一个打印队列，将打印任务逐个打印，从而避免数据丢失或打印次序混乱; 3)数据库系统则使用线性表、链表等进行数据管理; 4)人工智能领域依据问题的差异涉及到诸如广义表、树、各种有向图等； 1.1 算法的基本概念 所谓算法是指解题方案的准确而完整的描述。 对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内，运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。 1.算法的基本特征 1）可行性：算法描述的每一个步骤必须能够实现，且能够达到预期的目的； 2）确定性：算法中的每一个步骤，必须经过明确的定义，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出 2.算法的基本要素 1）算法中对数据对象的运算和操作 通常，基本运算和操作有以下四类： ①算术运算：有加、减、乘、除等运算； ②逻辑运算：有“与”、“或”、“非”等运算； 2）算法的控制结构 算法中各操作之间的执行顺序，称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。 3. 算法设计的基本方法 算法设计的基本方法有列举法、归纳法、递推、递归、减半递推技术和回溯法。 1）列举法 列举法的基本思想是，根据提出的问题，列举所有的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。因此，列举法常用于解决“是否存在”或“有多少可能”等类型的问题，例如求解不定方程的问题。 2）归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。 3）递推 所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。 4）递归 人们在解决一些复杂问题时，为了降低问题的复杂程度，一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解。但是当解决了分解到最后的那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。 [找伪币]：假设16枚金币中有一枚是伪造的,真假金币的区别仅是重量不同,利用一个没有砝码的天平作工具,如何快速找出这枚伪造的金币? ６）回溯法 回溯法的基本思想是，通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解；若试探失败，就逐步回退，换别的路线再进行试探。 1.2 算法复杂度及算法的描述方式 1.算法复杂度 算法复杂度主要包括算法的时间复杂度和算法的空间复杂度。 1）算法的时间复杂度* 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 算法的工作量，一般用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即　 　　算法的工作量＝T(n) 其中，n是问题的规模。例如，两个n阶矩阵相乘，所需要的基本运算（即两个实数的乘法）次数是n的函数T(n)。算法如下： for(i=0;in;i++) /*执行n+1次*/ for(j=0;jn;