1.3 程序算法简介
1.3 程序算法简介
什么是算法？当代著名计算机科学家D.E.Knuth在他撰写的《THE ART OF COMPUTERPROGRAMMING》一书中写到：“一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。”简单地说，任何解决问题的过程都是由一定的步骤组成的，把解决问题确定的方法和有限的步骤称做算法。
1.3.1 算法举例
下面通过例子来介绍如何设计一个算法：
输入3个数，然后输出其中最大的数。
首先，得先有个地方装这3个数，我们定义3个变量A、B、C，将3个数依次输入到Ａ、B、C中，另外，再准备一个MAX装最大数。
由于计算机一次只能比较两个数，我们首先把A与B比，大的数放入MAX中，再把MAX与C比，又把大的数放入MAX中。
最后，把MAX输出，此时MAX中装的就是Ａ、Ｂ、C3个数中最大的一个数。算法可以表示如下：
（1）输入A、B、C。
（2）A与B中大的一个放入MAX中。
（3）把C与MAX中大的一个放入MAX中。
（4）输出MAX，MAX即为最大数。
其中的（2）、（3）两步仍不明确，无法直接转化为程序语句，可以继续细化；（2）把A与B中大的一个放入MAX中，若A>B，则MAX←A；否则MAX←B；（3）把C与MAX中大的一个放入MAX中，若C>MAX，则MAX←C。
于是算法最后可以写成：
（1）输入A，B，C。
（2）若A>B，则MAX←A；否则MAX←B。
（3）若C>MAX，则MAX←C。
（4）输出MAX，MAX即为最大数。
这样的算法已经可以很方便地转化为相应的程序语句了。
下面再看一例：猴子吃桃问题。有一堆桃子不知数目，猴子第1天吃掉一半，觉得不过瘾，又多吃了一只，第2天照此办理，吃掉剩下桃子的一半另加一个，天天如此，到第10天早上，猴子发现只剩一只桃子了，问这堆桃子原来有多少个？
此题粗看起来有些无从着手的感觉，那么怎样开始呢？假设第一天开始时有a1只桃子，第二天有a2只，……，第9天有a9只，第10天是a10只，在a1,a2,…，a10中，只有a10=1是知道的，现要求a1，而我们可以看出，a1,a2,…，a10之间存在一个简单的关系：
a9=2*(a10+1)
a8=2*(a9+1)
M
a1=2*(a2+1)
也就是：ai=2*(ai+1+1) i=9,8,7,6,…,1
这就是此题的数学模型。
再考察上面从a9，a8直至a1的计算过程，这其实是一个递推过程，这种递推的方法在计算机解题中经常用到。另一方面，这9步运算从形式上完全一样，不同的只是ai的下标而已。由此，我们引入循环的处理方法，并统一用a0表示前一天的桃子数，a1表示后一天的桃子数，将算法改写如下：
（1）a1=1。｛第10天的桃子数，a1的初值｝i=9。｛计数器初值为9｝。
（2）a0=2*(a1+1)。｛计算当天的桃子数｝。
（3）a1=a0。｛将当天的桃子数作为下一次计算的初值｝。
（4）i=i-1。
（5）若i>=1，转步骤（2）。
（6）输出a0的值。
其中步骤（2）～步骤（5）为循环。
这就是一个从具体到抽象的过程，具体方法是：
（1）弄清如果由人来做，应该采取哪些步骤。
（2）对这些步骤进行归纳整理，抽象出数学模型。
（3）对其中的重复步骤，通过使用相同变量等方式求得形式的统一，然后简练地用循环解决。
1.3.2 算法应具备的特性
算法是一个有穷规则的集合，这些规则确定了解决某类问题的一个运算序列。对于该类问题的任何初始输入值，它都能机械地一步一步地执行计算，经过有限步骤后终止计算并产生输出结果。归纳起来，算法具有以下基本特征：
· 有穷性。一个算法必须在执行有限个操作步骤后终止。
· 确定性。算法中每一步的含义必须是确切的，不可出现任何二义性。
· 有效性。算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的。例如，一个数被0除的操作就是无效的，应当避免这种操作。
· 有零个或多个输入。这里的输入是指在算法开始之前所需要的初始数据。这些输入的多少取决于特定的问题。
· 有一个或多个输出。所谓输出是指与输入有某种特定关系的量，在一个完整的算法中至少会有一个输出。
1.3.3 流程图表示法
原则上说，算法可以用任何形式的语言和符号来描述，通常有自然语言、程序语言、流程图、N-S图、PAD图、伪代码等。
提示：因为流程图便于交流，又特别适合于初学者使用，对于一个程序设计工作者来说，会看会用传统流程图是必要的。
下面以求最大公约数为例说明这个算法用流程图的表示方法。
1．算法分析
算法分析也是一个数值运算问题，它有成熟的算法，我国数学家秦九韶在《算书九章》一书中曾记载了这个算法。求最大公约数的问题一般用辗转相除法（也称欧几里德算法）求解。
例如：设m35，n15，余数用r表示。它们的最大公约数的求法如下：35/15商2余数为5以n作m，以r作n，继续相除；15/5商3余数为0当余数为零时，所得n即为两数的最大公约数。所以35和15两数的最大公约数为5。用这种方法求两数的最大公约数，其算法可以描述如下：
（1）将两个正整数存放到变量m和n中。
（2）求余数。计算m除以n，将所得余数存放到变量r中。
（3）判断余数是否为0。若余数为0则执行第（5）步，否则执行第（4）步。
（4）更新被除数和余数。将n的值存放到m中，将r的值存放到n中，并转向第（2）步继续循环执行。
（5）输出n的当前值，算法结束。
如此循环，直到得到结果。
2．流程图表示
流程图是一种传统的算法表示法，它利用几何图形的框来代表各种不同性质的操作，用流程线来指示算法的执行方向。由于它简单直观，所以应用广泛，特别是在早期语言阶段，只有通过流程图才能简明地表述算法，流程图成为程序员们交流的重要手段，直到结构化的程序设计语言出现，对流程图的依赖才有所降低。下面介绍几种常见的流程图符号及流程图的例子。
在流程图中，判断框左边的流程线表示判断条件为真时的流程，右边的流程线表示条件为假时的流程，有时就在其左、右流程线的上方分别标注“真”、“假”或“T”、“F”或“Y”、“N”。图1-1就表示了几种流程图的基本组成元素图。
图1-2是求最大公约数算法的流程图。
图1-1 常见流程图的基本组成元素图
图1-2 求最大公约数算法的流程图
|
图1-3 求3个数的最大值得N-S图
|
N-S图是另一种算法表示法，是由美国人I.Nassi和B.Shneiderman共同提出的，其根据是：既然任何算法都是由3种结构（本章后边介绍）组成的，各基本结构之间的流程线就是多余的。N-S图也是算法的一种结构化描述方法。
在N-S图中，一个算法就是一个大矩形框，框内又包含若干基本的框。下面介绍如图1-3所示介绍N-S流程图。
该图表述的基本算法含义描述如下：
（1）输入A、B、C。
（2）若A>B，则MAX←A；否则MAX←B。
（3）若C>MAX，则MAX←C。
（4）输出MAX，MAX即为最大数。