面向过程的程序设计的分析介绍

7.4.2　面向过程的程序设计

程序设计人员编写程序就是解决如何获得输入数据、如何存储处理数据、如何输出数据，要分析问题及解决问题的过程。算法和数据表示了程序设计中的两个紧密关联的方面，1984 年Turing奖的获得者N.Wirth用“算法+数据结构＝程序”精辟地表述了这两者在程序设计方法学中的核心地位。事实上，程序就是在数据的特定表达形式上对抽象的算法进行具体的描述。不了解施加于数据上的算法就无从决定如何构造数据；反过来，算法的设计又依赖于它所加工的数据的构造。因此，这两方面构成了一个不可分割的整体。

1．算法的特征

简单地说，算法就是解决确定的一类问题的操作序列，也就是解决问题的过程。机械地按一定的规则和次序执行这些操作，就可以对数据对象进行加工和变换，最终得到问题的解决。具有以下五个主要特征的操作序列才能被称为算法：

(1) 有穷性。一个算法执行有限个操作后必须终止。

(2) 确定性。它的每一个操作都必须有确切而无二义的定义。

(3) 能行性。算法的每一个操作都可以在有限的时间内完成。

(4) 输入。算法通常有若干个输入数据。

(5) 输出。算法要产生输出数据，一般是输入数据的最终变换结果，还可能包括一其它有用的信息。

因此，一个算法是一个有穷规则的有序集合，这些规则给出了解决某一类问题的一个确定而可行的计算序列，对于这类问题的任何一种合法的初始输入，通过按部就班的机械计算，都可以在有限步后终止计算，得到输出结果。例如，对于求两个正整数m和n的最大公因数问题，可以设计一个包含三个步骤的操作序列：(1)求m除以n的余数r；(2)如果r＝0，则输出n的值，终止；否则执行第(3)步；(3)以n为m的新值，r为n的新值，转向第(1)步。

显然，这个操作序列具有前述的五个特征，因此这是一个算法。对于给定的任意两个正整数，只要反复执行三个操作步骤若干次，总可以得到它们的最大公因数。

2．算法表示的逐步求精

由于要解决的问题头绪复杂，往往无法很快把握住每一个操作步骤的细节，因此，要构造解决问题的算法，通常应首先就问题的全局做出决策，设计出一个抽象算法。抽象算法由对抽象数据对象的一系列抽象操作组成，表达的是解决问题的总体策略。

然后，考虑抽象数据和抽象操作如何具体实现，算法进入下一个抽象程度降低了的层次，这个过程为“求精”。在求精过程的每一步里，抽象的数据和操作都进一步分解、精细和具体化，如此反复直到算法能够用某一种程序语言规定的成分来表示数据结构和操作过程为止。这时，原来的抽象的算法就演变成了一个能够被计算机系统识别、理解和执行的程序了。

例如，用筛法求2到自然数N间的全部素数，先从筛中筛去素数2的所有倍数。可以证明留在筛中的大于最近找到的素数的最小元素是下一个素数，因此3是素数，于是把它的所有倍数筛去……这样依次筛掉每个新找到的素数的所有倍数，在有限步后，筛中找到的新的素数一定是留在筛中的数里的最后一个元素，这样筛中留下的是2到N中的全部素数。

算法很直截了当，但是，“筛”是抽象的数据对象，“筛去”是对它的抽象操作，因此需要在一个更具体的层次上考虑它们的实现。例如，可以用一个集合表示筛，集合里的元素就代表留在筛上的数；再构造包含特定数的另一个集合，于是用两个集合的差运算就可以实现从筛中筛去特定数的操作。

到了程序设计层次，就得进一步考虑在具体的语言环境中如何实现集合的构造。如PASCAL语言是提供数据的集合类型的，可以直接定义一个集合变量。而在其它不支持集合定义的语言中，就需另谋出路，比如去定义一个数组，以数组元素的整数下标表示自然数，用数值元素的两个取值(如0和1；或“假”和“真”)来表示该自然数在或不在筛中，这样，用集合和差运算来表示的“筛去”操作就通过对数组元素的赋值操作得以实现了。

3．算法的分析

对于要解决的同一类问题，往往能够设计出多种算法。仍以找出2到N间的全部素数为例，利用数论中的结论，不必将筛法执行到只剩最后一个素数，而只需要将2到N间的素数的所有倍数筛去，剩下的一定都是素数了。显然，这种改进的筛法的效率要优于原来的筛法。当然也可以不用筛法而用其它方法，如顺次取出自然数I(3＜i＜N)，检查其被从2到(i -1)的各数除时余数是否为零，如全部不为零则i为素数，否则就不是素数。容易判别，这个方法比筛法的效率要差。

算法分析的任务就是在某些约定的标准下，去研究和判别一个个具体算法的优劣。衡量和评价算法通常采用“计算复杂性”的概念，一个算法需要耗费的时间和空间分别称为该算法的时间复杂性和空间复杂性。

评价算法还有一些其它重要标准，如对数值算法必须研究它的数值稳定性等，这里不一一细述了。

4．结构化程序设计方法

抽象原则是程序设计方法中最基本的原则之一，在前面已经看到了它在程序设计过程中在数据表达和操作表达方面的应用。一般的说，对于所面临的复杂间题，应当先抽取出其本质属性而置枝节于不顾，然后在抽象级上考虑解题的一般策略和问题解的一般结构，下一步再在现实级上考虑具体如何表述。一个实现级仍可以是一个抽象级，其上的概念由下一个更低的实现级层次负责表达，这样一步步做下去，直到最终的一个实现级上的全部表达手段能力解题的运行环境所接受、理解和执行为止。

抽象原则的应用产生了软件设计的结构化方法。结构化技术的方法是“自顶向下，逐步求精”。设计人员从最能直接反映问题体系结构的概念出发，确定解决问题的若干个子目标，再进一步考虑各个子目标(子问题)的解法，这样就把问题的解决过程精细了一步。逐步的精细化。

具体化导致子目标层层确立又层层被解决，当所有的表达概念都可以用某种程序设计语言描述时，解题过程就转换为程序了。

结构化方法的实质是，依据抽象原则，先确定子目标，以表达要“做什么”，再进一步考虑子目标的实现方法，即“怎样做”。这样，整个问题就分解为一系列相对独立的子问题，它们中的每一个都只涉及到局部的表达环境和手段条件。可以相对独立地加以解决，这样通过化繁为简，各个击破，整个问题就水到渠成，得以圆满解决。

结构化方法的运用必然使问题的解从形式上也呈现一种结构化的构造，即具有一种和自顶而下的求精过程相一致的层次构造，这是不言而喻的。

20世纪60年代末，人们的注意力普遍放在程序的编写方面。有两位学者利用数学方法严格证明了一条定理：“任何程序逻辑都可以只利用顺序、选择、循环三种基本结构的重复、组合、嵌套来实现”。在此基础上产生了结构化程序设计方法：通过先全局后局部、先抽象后具体、先宏观后细节的逐步求精方法，在自顶向下的求精过程中反复使用三种基本结构的重复、组合和嵌套来表达处理控制逻辑，最终自然产生高质量的结构化程序。

到了70年代中期，人们开始认识到，编写程序只是软件开发中的一个环节，而合理地建立系统结构更重要，因此研究的重点前移至设计阶段，将结构化方法应用于设计，由此产生了结构化系统总体设计方法。该方法以模块化为基本策略，所谓模块是指程序系统的结构单位，在语言环境中表现为子程序、过程、函数等形式。模块具有四种基本属性：有数据的输入／输出、有逻辑功能、有内部数据、与一般运行程序相对应。结构化的总体设计方法以功能为依据，遵循自顶向下、逐步细化的原则将总系统划分成若干个模块，系统的功能通过这些模块的具体功能来实现，而每个具体功能又可再划分成若干的下层模块来实现，一直到产生极细微但依然完整的底层功能为止。这样，整个程序系统呈现由模块之间调用关系所建立的一种层次结构。在本阶段只需关心模块的划分、模块输入／输出的定义、调用关系的确立等问题，至于模块的功能如何实现则是编写程序阶段的事情了。

5．算法的表示

常见用来表示算法的方法有程序流程框图、NS图和PDL逻辑语言。流程框图我们已经比较熟悉，NS图不适宜在中学中介绍，PDL逻辑描述是较实用的一种方式，简介如下：

PDL语言是介于自然语言和结构化程序设计语言之间的一种语言，常称为结构化英语或结构化汉语。遵循自顶向下， 逐步细化的原测，用简单的语法规则和自然语言相结合。很概括、很简单地描述模块的算法。特别适合于分析和讲解算法。

少量的法则：

用IF〈条件〉THEN〈工作1〉ELSE〈工作2〉描述选择结构。用SELECT CASE—END　SELECT 描述多分支结构。

用DO〈循环体〉LOOP　WHILE 〈条件〉描述条件控制循环。

用FOX X=初 TO 终—NEXT X 描述计数循环。

其它则用自然语言来说明。

例：某毕业班85学生，打印出毕业成绩部分在前三名的成绩。

读1名学生成绩X

第1名M1=X；第2名M2=X；第3名M3=X

FOR　I=1　TO　85

读X

IF M1〈 X　THEN 交换M1和X的值使 M1总是最大的

IF M2〈 X　THEN 交换M2和X 的值

IF M3〈 X THEN　M3=X

NEXT I

输出M1、M2、M3

可供思考的问题，要求打印出成绩总分在前三名的姓名和成绩。

6．中学BASIC程序设计语言的特点

中学主要介绍的是QBASIC程序设计语言，该语言是结构化程序设计语言，但将数据部分作了简化处理，而更多关注过程的控制和处理。因此，介绍语言的语法、语义和解决问题的算法就是教学的重点。