基础编程的思考方法

2018-04-23 09:13焦华

软件 2018年3期

焦华

（贵州商学院，贵州贵阳 550014）

0 引言

传说著名的瑞士计算机科学家尼克拉斯·沃思（Nicklaus Wirth）是凭借一句话获得图灵奖的，这句话就是众所周知的著名公式：“算法+数据结构=程序”，即程序包含了对数据的描述和对操作的描述两个方面——计算机的操作对象和操作步骤。[1]比如已知三角形的三个边a、b、c，用海伦公式求三角形的面积。数据的描述是a、b、c、p、s；算法的简单描述如下（为简单起见，这里假定输入的a、b、c满足两边之和大于第三边）：

Wirth公式对计算机科学的影响程度类似于物理学中爱因斯坦的质能方程“E=MC2”——一个公式揭示了程序的本质。事实上这个公式是 Wirth在1976年写的一本名著的书名——《Algorithms +Data Structures = Programs》。Wirth被誉为 PASCAL之父，同时也是好几种编程语言的主设计师，结构化程序设计的思想方法也是Wirth在上世纪70年代提出的。“顶层设计→逐步求精→模块实现”在当时的程序设计领域引发了一场革命，具有里程碑的意义，完全改变了人们对编程的思维方式。世界的复杂性与人类思维的局限性使得结构化编程方法是解决这一矛盾的有力工具！扩展的Wirth公式是：“算法+数据结构+结构化程序设计方法+语言工具=结构化程序”。因此 1984年获得的图灵奖是对 Wirth一系列重大贡献的回报[2]。

应当说Wirth公式贯穿了过程化程序设计始终，可以将所有的知识点都串起来。比如C语言程序设计包含的内容有：程序设计及C语言、算法——程序的灵魂、顺序结构程序设计、分支结构程序设计、循环结构程序设计、用函数实现模块化程序设计、利用数组处理批量数据、善于利用指针、结构体与共用体、对文件的输入输出。可以看出，这些内容都包含于扩展的Wirth公式中。

未来有众多的不确定性但不容置疑的是大数据时代已经到来，大数据的世界是程序的世

界！Wirth公式指出，算法是程序的灵魂，从而大数据的世界就是算法的世界！因此有必要对基础编程的核心——Wirth公式蕴含的思想加以梳理，相关概念和内容进行再认识。

1 W irth公式中相关概念的重述与再认识

计算机有硬件与软件之分，软件是程序和程序文档的总称，计算机的本质是“执行程序的机器”。由于 Wirth公式揭示了程序的本质，在此重温其相关术语和内容[3]。

算法（Algorithm）通俗地讲，是解决问题的方法与步骤；在数学中，算法通常是指遵照一定的规则解决某一类问题明确的且有效的步骤；在计算机科学中，算法是指解题方案的既准确又完整的描述，是一系列清晰指令的有限序列。算法应当具备正确性、有穷性、可读性、健壮性、人机交互性等特征。

数据（Data）是客观事物的符号表示，计算机科学里是指能输入至计算机且被计算机程序加工处理的符号的总称。

数据元素（Data Element）是数据的基本单位，计算机程序通常将它作为一个整体加以处理和考虑。

数据结构（Data Structure）是指数据元素自身特征以及它们之间的相互关系（结构）。它有四类基本结构：集合、线性结构、树型结构、图或网状结构。

数据类型（Data Type）是与数据结构密切有关的概念，最先出现在计算机高级语言中，用来刻画程序操作对象的特性。它是一个值的集合以及定义在该值集上一组操作的总称。

算法与数据结构的关系：算法依赖于具体的数据结构，数据结构关系到算法的选择与效益。因此很多时候是先确定数据结构，再确定算法。

程序（Program）是一组计算机能识别和执行的指令序列。编写程序的人称为程序员，编写程序的活动或过程称为程序设计。

类比实例 1：一盘已做好的美味菜肴比作一个程序，菜谱中需要的食材、佐料相当于数据结构，菜谱中的操作流程相当于算法，厨师相当于程序员，烹饪的过程相当于程序设计。

类比实例 2：一座已建好的雄伟建筑比作一个程序，建筑中需要的钢筋、水泥、砖瓦等建材相当于数据结构，动工之前的建筑物设计图相当于算法，设计师及建筑工人相当于程序员，从动工到完工验收的过程相当于程序设计。

在扩展的Wirth公式中，如果将“数据结构+语言工具”比作人体的组织、器官，那么“算法+结构化程序设计方法”则是人的思想、灵魂。你可以用你的思想去支配你身体的各器官随意运动。深入下去就是哲学中物质与意识的关系。

2 用流程图表示算法

程序的概念从“指令序列”转到“算法+数据结构”，两者并不矛盾，而是为解决问题必经的具体化历程。比如线性方程组的求解要用到初等行变换算法；而职工工资收入的高低排列要用到排序算法。算法的表示就是解决具体问题的思路描述[4]。

算法的表示（描述）方法有：自然语言、流程图、N—S结构图、PAD问题分析图、伪代码、计算机语言等。实际上用计算机语言表示算法就已经是源程序了。

最早描述算法应当是自然语言，虽然这种方式通俗易懂但容易出现歧义，且描述分支和循环极不方便，于是人们发明了流程图。这是用一些图框来表示各种操作，图形表示的算法既直观形象又易于理解。

实例1：判定2000——2500年中每一个年份是否是闰年，并将结果输出。

算法的流程图如下：

一级算法：

图1 判定闰年的一级算法流程图[5]Fig.1 Flow chart of first order algorithm for judging leap year

二级求精：

图2 判定闰年的细化流程图Fig.2 A thinning flow chart for judging leap year

其实二级求精流程图可以简化、不需要分支嵌套，故意复杂化是编程训练的需要。

实例 2：欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。

欧几里得算法的流程图如下[6]：

3 程序（流程）的三种基本结构

在传统的流程图中是用流程线来指明各框的执行顺序，对流程线的使用无限制，于是乱麻一样的“面条算法”出现了。为解决这一问题，Bohra和Jacopini在1966年提出了三种基本结构——顺序结构、选择结构、循环结构，用这三种基本结构作为基本单元去搭建的算法称为结构化算法。可以证明无论多么复杂的流程都可以用三种基本结构排列、组合、嵌套得到（所有非结构化算法可转化为结构化算法）。色彩学上的三色理论，是指红、绿、蓝这三种颜色相互独立，但自然界的任何色彩都可以由三种颜色按不同的比例混合而成。顺序结构、选择结构、循环结构相互独立，虽然人类开发的程序千千万万，但任何程序都可用这三种基本结构搭建得到，如同俄罗斯方块游戏中用七种不同形状的构件去搭建城墙一样[7]。

图3 欧几里德算法流程图Fig.3 Flow chart of euclid algorithm

顺序结构强调流程的次序，先做什么后做什么很重要，次序不能颠倒。比如一个大学生早晨起床后要做的事：穿衣→洗脸刷牙→整理书包→食堂吃饭→教室上课。如果次序改变为：洗脸刷牙→穿衣→食堂吃饭→回宿舍整理书包→教室上课。这将是糟糕的顺序。自然与社会中的时间次序、空间次序、事件次序可以举出很多例子。

选择结构也称为分支结构，在多种选择（分支）中只能取一种，如同在多岔路口你只能走其中的一条。“选择比努力更重要”表达的就是一旦选定将无法更改，这世界从来没有“后悔药”，“机会”错过就不再有了。

循环结构也称为重复结构，是指反复执行某一部分操作。循环是天体宇宙的法则。地球每天都在孤独地旋转：自转一圈24小时，形成白天黑夜的交替；公转一圈365天，形成春夏秋冬的轮回。生活在地球上的人类也因此“日出而作，日落而栖”地重复，感受春花秋月的浪漫、夏日冬雪的无奈……。

“顺序不能倒、选择是唯一、循环有条件”是三种基本结构必须遵循的原则，三种基本结构是自然和社会的法则。在计算机科学中，我们只要定义了三种基本结构的图形表示，任何复杂问题的算法都可由这三种图形排列、组合、嵌套得到[8]。

值得一提的是另一种非主流的观点认为：流程不是三种而是四种基本结构，它将函数的调用回返也作为一种基本结构，这种思考方式可理解为函数的调用回返是和顺序、选择、循环一样，都是相当重要的结构。

4 用N—S结构图和PAD问题分析图表示算法

N—S结构图也称为盒图，是由美国学者I.Nassi和 B.Shneiderman于1973年提出的一种在流程图中完全去除流程线，所有算法写在一个矩形框内，在框内还可以包含其他从属于它的框，即大框套小框、框框排列的形式表达算法。命名为N-S结构流程图是纪念这两位学者的（用两个人姓名的头一个字母组成）。N—S结构图特别能表达“自顶向下、逐步细化、模块化”的编程思想，与中国古代哲学“太极生两仪、两仪生四象；四象生八卦、八卦定乾坤。”是相通的[9]。

实例2欧几里得算法的N—S结构图如下：

图4 欧几里德算法的N—S结构图Fig.4 N - S structure diagram of euclid algorithm

PAD问题分析图[problem analysis diagram]是日本日立公司二村良彦等人于 1973年提出的一种表示算法的图形工具。其优点是PAD图是二维树形结构，从上到下的各部分是流程执行顺序，而从左往右的展开则代表层次关系。它的特点是结构清晰、易于阅读、结构化程度高。最左边纵线是程序的主干线，对应于程序第一层结构，之后每增加一层，PAD图就向右扩展一条纵线，纵线数就是程序层次数。程序执行时是从PAD图最左边主干线的上端结点开始，从上而下、自左往右依次执行，最后终止于最左主干线[2]。

实例2欧几里得算法的PAD问题分析图如下：

图5 欧几里德算法的PAD问题分析图Fig.5 PAD problem analysis diagram of euclid algorithm

伪代码是使用自然语言与计算机语言之间的文字及符号来表示算法。软件从业人员一般习惯使用伪代码，这是由于复杂而庞大的问题，画 N—S结构图或PAD问题分析图很费事，使用伪代码不受约束、自由自在。伪代码还有容易转化为真代码（源程序）的优势，但表达的流程不清晰、不直观、尤其对分支与循环描述困难。

传统流程图、N—S结构图、PAD问题分析图是基础编程的基本功！是学习程序设计必经的思维训练历程！

5 结构化程序设计方法

结构化程序设计是用工程的方法设计程序。其基本思想就是“自顶向下、逐步细化、模块化编程”，是将问题的求解从抽象逐步具体化的过程。在模块化分工完成后，即把一个大任务分解为若干个子任务后，对每一个子任务（小模块）的编码则是“自下而上、逐步积累”的过程。类比例子是设计房屋，先要“自顶向下、逐步细化”作整体规划、确定建筑物方案……有了设计图之后，施工阶段则是一砖一瓦“自下而上、逐步积累”完成的[2]。

实例3：输入两个自然数a与b，求出它们的最大公约数和最小公倍数。

C语言是函数式的语言，它的特点决定了它是最容易实现结构化编程的优秀语言。在C语言中对一个较复杂的规模较大的问题编程时，代码通常由一个主函数和若干个其它函数组成。一个函数就是一个程序模块。主函数可调用其它函数，其它函数也可相互调用，但主函数只能被操作系统调用。同一函数可被一个或多个函数调用任意多次（“代码重用”）。函数必须先定义后使用，函数之间的关系是相互独立的、地位是平行的。和“组装汽车”、“组装电脑”相类似，结构化编程就是“组装程序”，而函数就是“组装程序”的部件。

下面的函数调用回返的树型模块图（方向向右的树，可旋转改变方向。）可反映复杂程序的结构脉络。