1.2 算法和算法的表示

1.2 算法和算法的表示

1.2.1 算法的概念

1.算法的基本概念

什么是算法？当代著名计算机科学家D.E.Knuth在他撰写的《THE ART OF COMPUTER PROGRAMMING》一书中写到："一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。"简单地说，任何解决问题的过程都是由一定的步骤组成的，把解决问题确定的方法和有限的步骤称作为算法。

需要说明的是，不是只有计算问题才有算法。例如，加工一张写字台，其加工顺序是：桌腿 桌面 抽屉 组装，这就是加工这张写字台的算法。当然，如果是按"抽屉 桌面 桌腿 组装"这样的顺序加工，那就是加工这张写字台有另一种算法，这其中没有计算问题。通常计算机算法分为两大类：数值运算算法和非数值运算算法。数值运算是指对问题求数值解，例如对微分方程求解、对函数的定积分求解、对高次方程求解等，都属于数值运算范围。非数值运算包括非常广泛的领域，例如资料检索、事务管理、数据处理等。数值运算有确定的数学模型，一般都有比较成熟的算法。许多常用算法通常还会被编写成通用程序并汇编成各种程序库的形式，用户需要时可直接调用。例如数学程序库、数学软件包等。而非数值运算的种类繁多，要求不一，很难提供统一规范的算法。在一些关于算法分析的著作中，一般也只是对典型算法作详细讨论，其它更多的非数值运算是需要用户设计其算法的。

下面通过三个简单的问题说明设计算法的思维方法。

例1-1：有黑和蓝两个墨水瓶，但却错把黑墨水装在了蓝墨水瓶子里，而蓝墨水错装在了黑墨水瓶子里，要求将其互换。

算法分析：这是一个非数值运算问题。因为两个瓶子的墨水不能直接交换，所以，解决这一问题的关键是需要引入第三个墨水瓶。设第三个墨水瓶为白色，其交换步骤如下：

① 将黑瓶中的蓝墨水装入白瓶中；② 将蓝瓶中的黑墨水装入黑瓶中；③ 将白瓶中的蓝墨水装入蓝瓶中； ④ 交换结束。

例1-2：计算函数M(x)的值。函数M(x)为：

算法分析：本题是一个数值运算问题。其中M代表要计算的函数值，有两个不同的表达式，根据x的取值决定采用哪一个算式。根据计算机具有逻辑判断的基本功能，用计算机解题的算法如下：

① 将a、b、c和x的值输入到计算机；

② 判断x≤a?如果条件成立，执行第③步，否则执行第④步；

③ 按表达式bx+a2计算出结果存放到M中，然后执行第⑤步；

④ 按表达式a(c-x)+c3计算出结果存放到M中，然后执行第⑤步；

⑤ 输出M的值；

⑥ 算法结束。

例1-3：给定两个正整数m和n（m≥n），求它们的最大公约数。
　　算法分析：这也是一个数值运算问题，它有成熟的算法，我国数学家秦九韶在《算书九章》一书中曾记载了这个算法。求最大公约数的问题一般用辗转相除法（也称欧几里德算法）求解。
　　例如：设m 35，n 15，余数用r表示。它们的最大公约数的求法如下：
　　35/15商2 余数为5 以n作m，以r作n,继续相除；
　　15/5商3 余数为0 当余数为零时，所得n即为两数的最大公约数。
　　所以35和15两数的最大公约数为5。
　　用这种方法求两数的最大公约数，其算法可以描述如下：
　　① 将两个正整数存放到变量m和n中；
　　② 求余数：计算m除以n，将所得余数存放到变量r中；
　　③ 判断余数是否为0：若余数为0则执行第⑤步，否则执行第④步；
　　④ 更新被除数和余数：将n的值存放到m中，将r的值存放到n中，并转向第②步继续循环执行；
　　⑤输出n的当前值，算法结束。
　　如此循环，直到得到结果。
　　由上述三个简单的例子可以看出，一个算法由若干操作步骤构成，并且这些操作是按一定的控制结构所规定的次序执行。如例1-1中的四个操作步骤是顺序执行的，称之为顺序结构。而在例1-2中，则不是按操作步骤顺序执行，也不是所有步骤都执行。如第三步和第四步的两个操作就不能同时被执行，它们需要根据条件判断决定执行哪个操作，这种结构称之为分支结构。在例1-3中不仅包含了判断，而且需要重复执行。如第二步到第五步之间的步骤就需要根据条件判断是否重复执行，并且一直延续到条件"余数为0"为止，这种具有重复执行功能的结构称之为循环结构。

2.算法的两要素

由上述三个例子可以看出，任何简单或复杂的算法都是由基本功能操作和控制结构这两个要素组成。不论计算机的种类如何之多，但它们最基本的功能操作是一致的。计算机的基本功能操作包括以下四个方面：

(1) 逻辑运算：与、或、非；

(2) 算术运算：加、减、乘、除；

(3) 数据比较：大于、小于、等于、不等于、大于等于、小于等于；

(4) 数据传送：输入、输出、赋值。

算法的控制结构决定了算法的执行顺序。如以上例题所示，算法的基本控制结构通常包括顺序结构、分支结构和循环结构。不论是简单的还是复杂的算法，都是由这三种基本控制结构组合而成的。

算法是对程序控制结构的描述，而数据结构是对程序中数据的描述。因为算法的处理对象必然是问题中所涉及到的相关数据，所以不能离开数据结构去抽象地分析程序的算法，也不能脱离算法去孤立地研究程序的数据结构，而只能从算法和数据结构的统一上去认识程序。但是，在计算机的高级语言中，数据结构是通过数据类型表现的，本书在第三章、第七章、第十章和第十一章中，将通过对C语言数据类型的详细描述说明数据结构在程序设计中的作用。这里我们只讨论算法的问题。

需要强调的是，设计算法与演绎数学有明显区别，演绎数学是以公理系统为基础，通过有限次推演完成对问题的求解。每次推演都是对问题的进一步求解，如此不断推演，直到能将问题的解完全描述出来为止。而设计算法则是充分利用解题环境所提供的基本操作，对输入数据进行逐步加工、变换和处理，从而达到解决问题的目的。

1.2.2 算法的基本特征

算法是一个有穷规则的集合，这些规则确定了解决某类问题的一个运算序列。对于该类问题的任何初始输入值，它都能机械地一步一步地执行计算，经过有限步骤后终止计算并产生输出结果。归纳起来，算法具有以下基本特征：

(1) 有穷性：一个算法必须在执行有限个操作步骤后终止；

(2) 确定性：算法中每一步的含义必须是确切的，不可出现任何二义性；

(3) 有效性：算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的。例如，一个数被0除的操作就是无效的，应当避免这种操作。

(4) 有零个或多个输入：这里的输入是指在算法开始之前所需要的初始数据。这些输入的多少取决于特定的问题。例如，例l-1的算法中有2个输入，即需要输入a和b两个初始数据，而例l-2的算法中则需要输入四个初始数据。有些特殊算法也可以没有输入。

(5) 有一个或多个输出：所谓输出是指与输入有某种特定关系的量，在一个完整的算法中至少会有一个输出。如上述关于算法的三个例子中，每个都有输出。试想，如果例1-3中没有 "输出n的当前值"这一步，这个算法将毫无意义。

通常算法都必须满足以上五个特征。需要说明的是，有穷性的限制是不充分的。一个实用的算法，不仅要求有穷的操作步骤，而且应该是尽可能有限的步骤。例如，对线性方程组求解，理论上可以用行列式的方法。但是我们知道，要对n阶方程组求解，需要计算n+1个n阶行列式的值，要做的乘法运算是（n！）（n-l）（n+1）次。假如n取值为20，用每秒千万次的计算机运算，完成这个计算需要上千万年的时间。可见，尽管这种算法是正确的，但它没有实际意义。由此可知，在设计算法时，要对算法的执行效率作一定的分析。

上一页  

1.2.3 算法的表示

原则上说，算法可以用任何形式的语言和符号来描述，通常有自然语言、程序语言、流程图、N-S图、PAD图、伪代码等。第一节中的三个例子就是用自然语言来表示算法，而所有的程序是直接用程序设计语言表示算法。流程图、N-S图和PAD图是表示算法的图形工具，其中，流程图是最早提出的用图形表示算法的工具，所以也称为传统流程图。它具有直观性强、便于阅读等特点，具有程序无法取代的作用。N-S图和PAD图符合结构化程序设计要求，是软件工程中强调使用的图形工具。

因为流程图便于交流，又特别适合于初学者使用，对于一个程序设计工作者来说，会看会用传统流程图是必要的。本书主要介绍和使用传统流程图表示算法，只对N-S图作简要说明。

1.流程图符号

所谓流程图，就是对给定算法的一种图形解法。流程图又称为框图，它用规定的一系列图形、流程线及文字说明来表示算法中的基本操作和控制流程，其优点是形象直观、简单易懂、便于修改和交流。美国国家标准化协会ANSI（American National Standard Institute）规定了一些常用的符号，表1-1中分别列出了标准的流程图符号的名称、表示和功能。这些符号已被世界各国的广大程序设计工作者普遍接受和采用。
起止框：用以表示算法的开始或结束。每个算法流程图中必须有且仅有一个开始框和一个结束框，开始框只能有一个出口，没有入口，结束框只有一个入口，没有出口，其用法如图1-1（a）所示。

输入/输出框：表示算法的输入和输出操作。输入操作是指从输入设备上将算法所需要的数据传递给指定的内存变量；输出操作则是将常量或变量的值由内存贮器传递到输出设备上。输入/输出框中填写需输入或输出的各项列表，它们可以是一项或多项，多项之间用逗号分隔。输入/输出框只能有一个入口，一个出口，其用法如图1-1（b）所示。

　　处理框：算法中各种计算和赋值的操作均以处理框加以表示。处理框内填写处理说明或具体的算式。也可在一个处理框内描述多个相关的处理。但是一个处理框只能有一个入口，一个出口，其用法如图1-1（c）所示

 　　判断框：表示算法中的条件判断操作。判断框说明算法中产生了分支，需要根据某个关系或条件的成立与否来确定下一步的执行路线。判断框内应当填写判断条件，一般用关系比较运算或逻辑运算来表示。判断框一般均具有两个出口，但只能有一个入口，其用法如图1-1（d）所示。
　　注释框：表示对算法中的某一操作或某一部分操作所作的必要的备注说明。这种说明不是给计算机的，而是给作者或读者的。因为它不反映流程和操作，所以不是流程图中必要的部分。注释框没有入口和出口，框内一般是用简明扼要的文字进行填写。其用法见图1-2所示。
　　流程线：表示算法的走向，流程线箭头的方向就是算法执行的方向。事实上，这条简单的流程线是很灵活的，它可以到达流程的任意处，可见它灵活的另一面是很随意。程序设计的随意性是软件工程方法中要杜绝的，因为它容易使软件的可读性、可维护性降低。所以，在结构化的程序设计方法中，常用的N-S图、PAD图等适合于结构化程序设计的图形工具来表示算法，在这些图形工具中都取消了流程线。但是，对于程序设计的初学者来说，传统流程图有其显著的优点，流程线非常明确的表示了算法的执行方向，便于读者对程序控制结构的学习和理解。
　　连接点：表示不同地方的流程图的连接。

 2.用流程图表示算法
　　下面将例1-1、例1-2和例1-3的解题算法用流程图表示。

　　在例1-1中，我们将黑、蓝、白三个墨水瓶分别用A、B、C三个变量表示，其算法就是用计算机进行任意两数交换的典型算法，流程图如图1-2所示。图中有开始框、结束框、输入框、输出框和流程线。其控制流程是顺序结构。
　　对例1-2和例1-3，我们使用与原题完全一致的变量名，图中的Y表示条件为真，N表示条件为假。图1-3中计算函数值的控制流程是选择结构，图1-4的控制流程是循环结构。在图1-4中使用了注释框，用此说明本操作完成"求余数"。
　　通过以上三个实际例子可以看出，算法就是将需要解决的问题用计算机可以接受的方法表示出来。例如：2+8-7可以直接表示，而求定积分解、求方程的根等问题，就必须找到数值解法，不能直接表达给计算机。所以算法设计是程序设计中非常重要的一个环节，而流程图是直观地表示算法的图形工具。作为一个程序设计者，在学习具体的程序设计语言之前，必须学会针对问题进行算法设计，并且会用流程图的方法把算法表示出来。

上一页  

1.2.4 几种常用算法介绍

关于算法的研究可参阅有关的书籍，本书不可能罗列所有算法。这里只介绍几个典型算法，目的是使读者了解一些解题的基本思想和方法，了解如何设计算法。在本书后续各章中，我们将结合C语言的具体内容和实际应用问题进一步讨论算法的设计。

1.枚举法
　　枚举法也称为穷举法，它的基本思想是：首先根据问题的部分条件预估答案的范围，然后在此范围内对所有可能的情况进行逐一验证，直到全部情况均通过了验证为止。若某个情况使验证符合题目的全部条件，则该情况为本题的一个答案；若全部情况验证结果均不符合题目的全部条件，则说明该题无答案。

　　在实际应用问题中，许多问题需要用穷举法来解决。中国古代数学家张丘建在他的《算经》中曾提出著名的"百钱百鸡问题"，其题目如下：
　　例题1-4： 鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？
　　这就是一个典型的枚举问题。如果用x、y、z分别代表公鸡、母鸡、小鸡的数量，根据题意列方程：

　　据题意可知，x、y、z的范围一定是0到100的正整数，那么，最简单的解题方法是：假设一组x、y、z的值，直接带入方程组求解，即在各个变量的取值范围内不断变化x、y、z的值，穷举x、y、z 全部可能的组合，若满足方程组则是一组解。这样即可得到问题的全部解。
可见，利用枚举法解题需要以下步骤：
　　(1) 分析题目，确定答案的大致范围。
　　(2) 确定列举方法。常用的列举方法有：顺序列举，排列列举和组合列举。
　　(3) 作试验，直到遍历所有情况。
　　(4) 试验完后可能找到与题目要求完全一致的一组或多组答案，也可能没找到答案，即证明题目无答案。
　　枚举法的特点是算法简单，容易理解，但运算量较大。对于可确定取值范围但又找不到其它更好的算法时，就可以用枚举法。通常枚举法用来解决"有几种组合"、"是否存在"、求解不定方程等类型的问题。利用枚举法设计算法大多以循环控制结构实现。

2.迭代法
　　迭代法是一种数值近似求解的方法，在科学计算领域中，许多问题需要用这种方法解决。迭代法的特点是：把一个复杂问题的求解过程转化为相对简单的迭代算式，然后重复执行这个简单的算式，直到得到最终解。
　　迭代法有精确迭代法和近似迭代法。所谓精确迭代是指算法本身提供了问题的精确解。如对N个数求和、求均值、求方差等，这些问题都适合使用精确迭代法解决。

　　例1-5： 计算S=1+2+3+4+…+100
　　其迭代方法如下：
　　首先确定迭代变量S的初始值为0；
　　其次确定迭代公式s+i→s；
　　当i分别取值1，2，3，4，…，100时，重复计算迭代公式s+i→s，迭代100次后，即可求出S的精确值。
　　其中，i的取值是一个有序数列，所以可以由计数器产生，即使i的初始值为1，然后每迭代一次就对i加1。图1-5是用迭代法求和的流程图。
　　迭代法的应用更主要的是数值的近似求解，它既可以用来求解代数方程，又可以用来求解微分方程。在科学计算领域，人们时常会遇到求微分方程的数值解或解方程f(x)=0等计算问题。这些问题无法用求和或求均值那样的直接求解方法。例如，一般的一元五次或更高次方程、几乎所有的超越方程以及描述电磁波运动规律的麦克斯韦方程等，它们的解都无法用解析方法表达出来。为此，人们只能用数值计算的方法求出问题的近似解，而解的误差是人们可以估计和控制的。
　　我们以求解方程f(x)=0为例说明近似迭代法的基本方法。首先把求解方程变换成为迭代算式x=g(x)，然后由估计的一个根的初始近似值X0出发，应用迭代计算公式xk+1=g(xk)求出另一个近似值X1，再由X1确定X2，…，最终构造出一个序列X0，X1，X2，…，Xn，…，就可逐次逼近方程的根。

　　例1-6：求方程x3-x-1=0在x=1.5附近的一个根。
　　首先将方程改写成：

　　用给定的初始近似值X0=1.5代入上式的右端，得到:

　　再用X1作为近似值代入(1)式的右端，又得到:

　　按这种方法重复以上步骤，可以逐次求得更精确的值。这一过程即为迭代过程。显然，迭代过程就是通过原值求出新值，再用新值替代原值的过程。
　　对于一个收敛的迭代过程，从理论上讲，虽然经无限多次迭代可以得到准确解，但实际计算时，只能迭代有限次，这就是计算机执行算法的有穷性特征。
　　由以上分析可见，使用近似迭代法构造算法的基本方法是：首先确定一个合适的迭代公式，选取一个初始近似值以及解的误差，然后用循环处理实现迭代过程，终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差。并认为最后一次迭代得到的近似值为问题的解。
迭代法通常用于非数值运算的求解问题。

3.递推和递归法
　　这是程序设计中常用的两种算法，都是利用某些公式的递推性。最常见的例子是计算级数，一般给出数列后项与前项的递推公式，要求计算数列通项。例如：
　　（1）f1(n)=2+ f1(n-1)，f1(1)=1 f1(n)={1，3，5，7，…}
　　这是首项为1公差为2的等差数列（等差级数）。
　　（2）f2(n)=2 f2(n-1)，f2(1)=1 f2(n)={1，2，4，8，…}
　　这是首项为1公比为2的等比数列。
　　（3）f3(n)=n f3(n-1)，f3(1)=1 f3(n)={1，2，6，24，…}
　　这个数列的通项f3(n)=n!。
　　（1）f4(n)= f4(n-1)+ f4(n-2)，f4(1)=1，f4(2)=1 f4(n)={1，1，2，3，…}
　　这就是有名的斐波那契数列。
　　以上数列的共同特点是，在数列的未知项与已知项之间存在着一定关系，借助于已知项和这一关系，就可逐项求出未知项。计算这些数列通常用递推和递归两种算法。
　　递推法：
　　所谓递推法，是指利用递推公式，由简到繁逐次迭代求解，

　　例1-7：求n！，设n=15。
　　求解n！可由1！+2！+，…，n！来完成，其算法存在如下递推过程：
　　f(0)=0!=1
　　f(1)=1!=1 0! =1
　　f(2)=2!=2 1! =2
　　f(3)=3!=3 2! =6
　　……
　　f(n)=n!=n (n-1)! n f(n-1)
　　要计算15！，可以从递推初始条件f(0)=1出发，应用递推通项公式f(n)= n f(n-1)逐步求出f(1)、f(2)、f(3)、…、f(14)，即由简到繁逐次迭代，直到最后求出f(15)的值。
　　递推法的关键是找到进行递推的通项公式，求一个数的阶乘是一个简单问题，该通项公式f(n)= n f(n-1)可以直接看出来。但事实上，有些问题要找出通项公式是相当困难的，并且即便找到计算也并非简便。这里我们只介绍递推法的基本思想方法，本书在第九章将对递推法和递归法进行较详细的讨论。
　　递归法：
　　什么是递归法？它与递推法有什么不同？递归法也是利用递推公式，所不同的是，它是由繁化简，用简单的问题和已知的操作运算来解决复杂的问题。仍以例1-7为例：
　　f(1)=1
　　f(n)= f(n-1)n
　　将后一个式子从n到n-1、再到n-2逐步递推化简得到：，
　　f(n)= f(n-1)n= f(n-2)(n-1)n
　　=…=f(1) 2 3 … n (n>1)
　　每一次化简，自变量减1，但要多乘一个因子。在化简的每一步，f(n-1)，f(n-2)，…等仍为未知量，直到化简到f(1)，则因为f(1)已知，f(n)便可由最后一个式子求乘法得到。这个计算过程不是直接的，它包含两个过程：
　　① 由繁到简的递推化简；
　　② 由已知值f(1)经乘法运算回归到所求值。
　　可见，递推与递归是有区别的。
　　通常递归是这样定义的：如果一个过程直接或间接地有限次数地调用了它自身，则称这个该过程是递归的。

　　例1- 8：有如下递归定义函数：

　 由函数的定义可见，如果n=0， xn的值是1，如果n>0， xn的值就是xn-1的x倍。用递归法分析：对于任何大于0的整数n，xn的值是由xn-1的值确定的，而xn-1的值是由xn-2的值确定的，……，就这样逐次上溯调用其本身的求解过程，最终xn的值将归结到x0的定义上。而x0的定义是函数明确给出的，所以问题得到了结果。这就是递归的方法。
　　我们注意到在这个函数的右边使用了被定义形式xn本身，这就是"递归"这个词的意义。这种情况就是调用了它自身。
　　递归法的关键是必须有一个递归终止条件，即要有递归出口。无条件的递归是毫无意义的。上述函数的递归终止条件是n=0，这就是递归出口。在阶乘的递归定义中，当n=0时，n!=1也是阶乘递归定义的递归出口。
　　递归与递推是既有区别又有联系的两个概念。递推是从已知的初始条件出发，逐次递推出最后所求的值。而递归则是从需要求解的函数本身出发，逐次上溯调用其本身的求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值。一般说来，一个递推算法总可以转换为一个递归算法。
　　一般而言，递推算法可利用循环结构实现，比较简单。而递归算法则要求语言具有反复自我调用子程序的能力，有些高级语言不具有这种能力，如FORTRAN、BASIC等。递归算法往往比非递归算法要付出更多执行时间，但尽管如此，因有很多问题的数学模型或算法设计方法本来就是递归的。用递归过程来描述它们不仅非常自然，而且证明算法的正确性也比相应的非递归形式容易很多，因此，递归仍不失为一种强有力的算法设计方法。
　　递归的概念首先在数学领域出现，然而，按递归方法设计算法的策略不仅适用于计算数学问题，而且也适用于非数值运算领域。例如检索过程的求解等。

4.分治法
　　在求解一个复杂问题时，应尽可能地把这个问题分解为较小部分，找出各部分的解，然后再把各部分的解组合成整个问题的解，这就是所谓的分治法。
使用分治法时，往往要按问题的输入规模来衡量问题的大小。若要求解一个输入规模为n且它的取值又相当大时，应选择适当的设计策略，将n个输入分成k个不同的子集合，从而得到k个可分别求解的子问题，其中k的取值为1<k≤n。在求出各个子问题的解之后，就可找到适当的方法把它们合并成整个问题的解。这里要注意的是，子问题要独立、要尽可能小。如果得到的子问题相对来说还太大，则可再次使用分治法进行分解。割得更小。
　　分治法常用于解决非数值运算问题，在数据检索、快速分类选择等问题的算法中被广泛应用