首页 理论教育 运算及设计方法

运算及设计方法

时间:2022-02-28 理论教育 版权反馈
【摘要】:一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。对于数值型的递推算法必须要注意数值计算的稳定性问题。递归是很重要的一种算法设计方法。通常,递归算法要比递推算法清晰易读,其结构比较简练。特别是在许多比较复杂的问题中,很难找到从初始条件推出所需结果的全过程,此时,设计递归算法要比递推算法容易得多。

2.1.2 算法的特征、运算及设计方法

算法具有可行性、确定性、有穷性和拥有足够的情报这四个重要特征。

1.算法的特征

作为一个算法,一般应具有以下四个特征:

(1)可行性

针对实际问题设计的算法,人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行。因此,算法在执行过程中往往要受到计算工具的限制,使执行结果产生偏差。例如,在进行数值计算时,如果某计算工具具有7位有效数字(如程序设计语言中的单精度运算),则在计算下列三个量

X=1012,Y=1,Z=-1012

的和时,如果采用不同的运算顺序,就会得到不同的结果,即

X+Y+Z=1012+1+(-1012)=0

X+Z+Y=1012+(-1012)+1=1

而在数学上,X+Y+Z与X+Z+Y是完全等价的。因此,算法与计算公式是有差别的。在设计一个算法时,必须要考虑它的可行性,否则是不会得到满意结果。

(2)确定性

算法的确定性,是指算法中的每一个步骤都必须是有明确定义的,不允许有模棱两可的解释,也不允许有多义性。这一性质也反映了算法与数学公式的明显差别。在解决实际问题时,可能会出现这样的情况:针对某种特殊问题,数学公式是正确的,但按此数学公式设计的计算过程可能会使计算机系统无所适从。这是因为根据数学公式设计的计算过程只考虑了正常使用的情况,而当出现异常情况时,此计算过程就不能适应了。

(3)有穷性

算法的有穷性,是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。数学中的无穷级数,在实际计算时只能取有限项,即计算无穷级数值的过程只能是有穷的。因此,一个数的无穷级数表示只是一个计算公式,而根据精度要求确定的计算过程才是有穷的算法。

(4)拥有足够的情报

一个算法是否有效,还取决于为算法所提供的情报是否足够。通常,算法中的各种运算总是要施加到各个运算对象上,而这些运算对象又可能具有某种初始状态,这是算法执行的起点或依据。因此,一个算法执行的结果总是与输入的初始数据有关,不同的输入将会有不同的输出结果。当输入不够或输入错误时,算法本身也就无法执行。一般来说,当算法拥有足够的情报时,此算法才是有效的,而当提供的情报不足时,算法可能无效。

综上所述,所谓算法是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。

2.算法的基本要素

一个算法通常由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构。

(1)算法中对数据对象的运算和操作

每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。因此,计算机算法就是计算机能处理的操作所组成的指令序列。

通常,计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中,基本的运算和操作有以下四类:

①算术运算:主要包括加、减、乘、除运算。

逻辑运算:主要包括“与”、“或”、“非”运算。

③关系运算:主要包括“大于”、“小于”、“等于”、“不等于”运算。

④数据传输:主要包括赋值、输入、输出操作。

(2)算法的控制结构

①算法中各操作之间的执行顺序称为算法的控制结构。

②描述算法的工具通常有传统流程图、N-s结构化流程图、算法描述语言等。

③一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。

3.算法设计基本方法

计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。计算机算法不同于人工处理的方法。

本节介绍常用的五种算法,在实际应用时,各种方法之间往往存在着一定的联系。

(1)列举法

列举法的基本思想是,根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。因此,列举法常用于解决“是否存在”或“有多少种可能”等类型的问题,例如求解不定方程的问题。

列举法的特点是算法比较简单。但当列举的情况较多时,执行列举算法的工作量将会很大。因此,在用列举法设计算法时,使方案优化尽量减少运算工作量是应该重点注意的。通常,在设计列举算法时,只要对实际问题进行详细的分析,将与问题有关的知识条理化、完备化、系统化,从中找出规律;或对所有可能的情况进行分类,引出一些有用的信息,这样可以大大减少列举量。

列举原理是计算机应用领域中十分重要的原理。许多实际问题若采用人工列举是不可想象的,但由于计算机的运算速度快、擅长重复操作,可以很方便地进行大量列举。列举算法虽然是一种比较笨拙而原始的方法,其运算量比较大,但在有些实际问题中(如寻找路径、查找、搜索等问题),局部使用列举法却是很有效的。因此,列举算法是计算机算法中的一个基础算法。

(2)归纳法

归纳法的基本思想是通过列举少量的特殊情况,经过分析,最后找出一般的关系。显然,归纳法要比列举法更能反映问题的本质,并且可以解决列举量为无限的问题。但是,从一个实际问题中总结归纳出一般的关系,并不是一件容易的事情,尤其是要归纳出一个数学模型更为困难。从本质上讲,归纳就是通过观察一些简单而特殊的情况,最后总结出一般性的结论。

归纳是一种抽象,即从特殊现象中找出一般关系。但由于在归纳的过程中不可能对所有的情况进行列举。因此,最后由归纳得到的结论还只是一种猜测,还需要对这种猜测加以必要的证明。实际上,通过精心观察而得不到证实或最后证明是错的,也是常有的事。

(3)递推

所谓递推,是指从已知的初始条件出发,逐次推出所要求的各个中间结果和最后结果。其中初始条件是问题本身已经给定的或是通过对问题的分析与化简而确定。递推本质上也属于归纳法,工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的。因此,递推关系式往往是归纳的结果。对于数值型的递推算法必须要注意数值计算的稳定性问题。

(4)递归

人们在解决一些复杂问题时,为了降低问题的复杂程度(如问题的规模等),一般总是将问题逐层分解,最后归结为一些最简单的问题。这种将问题逐层分解的过程,实际上并没有对问题进行求解,而只是当解决了最后那些最简单的问题后,再沿着原来分解的逆过程逐步进行综合,这就是递归的基本思想。由此可以看出,递归的基础也是归纳。在工程实际中,有许多问题就是用递归来定义的,数学中的许多函数也是用递归来定义的。递归在可计算性理论和算法设计中占有很重要的地位。

递归分为直接递归与间接递归两种。如果一个算法中显示的是调用自己则称为直接递归。如果算法P调用另一个算法Q,而算法Q又调用算法P,则称为间接递归调用。

递归是很重要的一种算法设计方法。实际上,递归过程能将一个复杂的问题归结为若干个较简单的问题,然后将这些较简单的问题再归结为更简单的问题,这个过程可以一直做下去,直到归结为最简单的问题为止。

有些实际问题,既可以归纳为递推算法,又可以归纳为递归算法。但递推与递归的实现方法是大不一样的。递推是从初始条件出发,逐次推出所需求的结果;而递归则是从算法本身到达递归边界的。通常,递归算法要比递推算法清晰易读,其结构比较简练。特别是在许多比较复杂的问题中,很难找到从初始条件推出所需结果的全过程,此时,设计递归算法要比递推算法容易得多。但递归算法的执行效率比较低。

(5)减半递推技术

实际问题的复杂程度往往与问题的规模有着密切的联系。因此,利用分治法解决这类实际问题是有效的。所谓分治法,就是对问题分而治之。工程上常用的分治法是减半递推技术。

所谓“减半”,是指将问题的规模减半,而问题的性质不变;所谓“递推”,是指重复“减半”的过程。

下面举例说明利用减半递推技术设计算法的基本思想。

例2-1 设方程f(x)=0在区间[a,b]上有实根,且f(a)与f(b)异号。利用二分法求该方程在区间[a,b]的一个实根。

用二分法求方程实根的减半递推过程如下:

首先取定区间的中点c=(a+b)/2。

然后判断f(c)是否为0。若f(c)=0,则说明c即为所求的根,求解过程结束;如果f(c)≠0,则根据以下原则将原区间减半:

若f(a)f(c)<0,则取原区间的前半部分;

若f(b)f(c)<0,则取原区间的后半部分。

最后判断减半后的区间长度是否已经很小:

若|a-b|<ε,则过程结束,取(a+b)/2为根的近似值;

若|a-b|≥ε,则重复上述的减半过程。

(6)回溯法

前面讨论的递推和递归算法本质上是对实际问题进行归纳的结果,而减半递推技术也是归纳法的一个分支。在工程上,有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤,并且也不能进行无限的列举。对于这类问题,一种有效的方法是“试”。通过对问题的分析,找出一个解决问题的线索,然后沿着这个线索逐步试探,对于每一步的试探,若试探成功,就得到问题的解,若试探失败,就逐步回退,换别的路线再进行试探。这种方法称为回溯法。回溯法在处理复杂数据结构方面有着广泛的应用。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈