文档介绍：第一节算法和数据结构的基本概念
一、算法
(一)算法的基本概念
算法是指解题方案的准确而完善的描述。通常,程序的编制不可能优于算法的设计。
算法的基本特征:
<1>可行性(effectiveness):算法受计算机工具的限制,使执行结果产生偏差。在设计一个算法时,必须要考虑它的可行性,否则是不会得到满意结果的。
<2>确定性(definiteness):算法的确定性,是指算法中的每一个步骤都必须有明确定义,不允许有歧义和多义。
<3>有穷性(finiteness):算法的有穷性是指计算时间和计算程序的有穷性。
<4>拥有足够的情报:初始数据的积累运用,避免输错或漏输。
:
一个算法通常由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构。
通常,计算机可以执行的基本操作是以指令的形式描述的。
一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。
在一般的计算机系统中,基本的运算和操作有以下几种:
<1>算术运算:主要包括加、减、乘、除等运算;
<2>逻辑运算:主要包括“与”“或”“非”等运算;
<3>关系运算:主要包括“大于”“小于”“等于”“不等于”等运算;
<4>数据传输:主要包括赋值、输入、输出等运算.
计算机程序也可以作为算法的一种描述,但由于在编制计算机程序时通常要考虑很多与方法和分析无关的细节问题(如语法问题),因此,在设计算法的一开始,通常并不直接用计算机程序来描述算法。
算法的主要特征着重于算法的动态执行,它区别于传统的着重于静态描述或按演绎方式求解问题的过程。传统的演绎数学是以公理系统为基础的,问题的求解过程是通过有限次推演来完成的,每次推演都将对问题作进一步描述,如此不断推演,直到直接将解描述出来为止。而计算机算法则是使用一些最基本的操作,通过对已知条件一步一步地加工和交换,从而实现解题目标。这两种解题方法的思路是不同的。
一个算法的功能不仅取决于所选用的操作,而且还和各操作之间的执行顺序有关。算法各操作之间的执行顺序称为算法的控制结构。
算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、循环、选择三种控制结构组合而成。
:
<1>列举法:通常用于解决“是否存在”或“有多少种可能”等类型的问题,例如求解不定方程的问题。同时列举算法在寻找路径、查找、搜索等实际问题中是很有效的。因此,列举算法是计算机算法中的一个基础算法。
<2>归纳法:要比列举法更能反映问题的本质,并且可以解决列举量为无限的问题。其基本思想为通过列举少量的特殊情况,经过分析,最后找出一般的关系。从本质上讲,归纳就是通过观察一些简单而特殊的情况,最后总结出一般性的结论。但由于在归纳过程中不可能对所有情况进行列举,因此,最后由归纳得到的结论还只是一种猜测,还需要对这种猜测加以必要的证明。
<3>递推:是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。其工程上很多递推关系式实际上是通过对实际问题的分析和归纳得到的,因此,递推关系式往往是归纳的结果。
递推算法在数值计算中是常见的。但