计算机算法描述工具与算法抽象程度

1.2.5　计算机算法描述工具与算法抽象程度

同一算法，可用不同算法描述工具来表示；同一算法描述工具，可用来表示不同算法。同时，算法也可有不同抽象程度的表示形式。

一、算法描述工具概述

从技术进步视角来看，算法描述工具可分为“非结构化（例如：传统流程图）→结构化（例如：NS图、NSZ图、PDA图、伪代码）→对象化（注：作者认为—— 从程序设计发展史来看，采用术语“对象化”比“面向对象”Object-Oriented，能更简练、精当地刻画出所谓“面向对象程序设计”的技术特色和历史地位；故本书倡导并只用此术语。例如：Rose的活动图、UML序列图）→同构化（如周图、算法周码）”四个发展阶段。

从载体形式视角来看，算法描述工具可分为“图形化（例如：传统流程图、NS图、NSZ图）→准自然语言化（例如：近自然语言式伪代码）→准形式语言化（例如：类PASCAL伪代码、类C伪代码）→准混成语言化（例如：算法周码）”四个发展方向。

二、同构化算法描述新工具——算法周码简介

随着软件开发技术“非结构化→结构化→对象化→同构化”的不断历史进步，算法设计与数据结构的描述工具也须与时俱进，应朝着“对象化”大步前进，向着“同构化”快步发展。为此，笔者推出了算法设计与数据结构同构化创新描述工具——算法周码。它比现行算法设计与数据结构描述工具更为简明方便、先进优越、科学规范，顺应和反映了这种历史进步与发展趋势。它不仅便于人工设计，利于计算机辅助设计与自动设计，而且可适应全球“人本位”的网络化教育与终生化教育的新发展与新需要。

1．始终结构与注释结构的描述

任何算法，总是“有始、有终”（即有开始操作、结束操作的）。为描述算法这一重要特性，算法周码特提供始终结构，如图1.2所示。

图1.2　始终结构的同构化算法周码表示法

图1.2中：

（1）方框线不是算法周码的构成部分，仅是本文为叙述简明而额外增添的辅助线（下同，不再说明）；

（2）花括号及其内容是注释结构；

（3）操作块a末尾必须有用做顺序结构标志符的分号“；”；

（4）操作块a自身的控制结构，可以是顺序结构、选择结构、循环结构、并行结构及其任意结构化组合。

2．顺序结构的描述

顺序结构，是任何算法的基础结构。其算法周码描述如图1.3所示。图1.3中，除开始操作、结束操作外，其余各操作块末尾必须有分号“；”。

图1.3　顺序结构的同构化算法周码表示法

3．非顺序结构的描述

（1）构成块的描述

如图1.4所示构成块是构成“如果条件型选择结构的真（分支）块、假（分支）块，情况条件型选择结构的各情况（分支）块，当型、直到型、步长型循环结构的循环体，并行结构的各并行体”的总称。构成块自身是一个自成一统的操作序列；构成块内部，各操作间的结构关系为块内顺序结构，故其操作两两间必须用分号“；”相间隔，但最后一个操作的末尾不得有分号（以有别于一般顺序结构）。应当注意：构成块不可视为“独立操作”，故位于它所在整个控制结构结尾的最后一个构成块末尾的那个分号“；”，并不是该构成块的，而是“该构成块所在整个控制结构”的分号“；”。

图1.4　构成块的同构化算法周码表示法

图1.4中，起止符“\\”、“//”分别表征其构成块内操作序列的起始点、终止点。显然，当且仅当构成块由单操作构成时，方可省略其起止符。

（2）选择结构的描述

图1.5　如果条件型选择结构的同构化算法表示法（n≥1）

① 如果条件型选择结构的描述。如果条件型选择结构的算法周码描述法如图1.5所示。图中，“T：”为真块引导符（它引导着如果条件型选择条件为“真”时所要执行的操作块），“F：”为假块引导符（它引导着如果条件型选择条件为“假”时所要执行的操作块），且最后一个假块尾才能有分号。若最后一个假块为空，则其假块“F：假块”应省略，但其真块末尾须为有分号的“T：真块；”

② 情况条件型选择结构的描述。情况条件型选择结构，把所论选择对象整体选择条件分成n（≥2）种情况——n个分支选择条件i，让选择条件i唯一决定选择对象的一个取值集合i（i=1，2，…，n，且满足“任何两个取值集合的交集为空集合，所有取值集i的并集必须刚好是所论选择对象的整个取值集合”），使选择对象取值于取值集合i时就执行分支i的构成块——情况块i（即a_i块）；反之亦然。这里，只有最后一个分支可能为空块；且仅当最后一个分支n的取值集合n恰好是前n−1个取值集合i的余集（即除这n−1个取值集合以外的全部数据所构成的集合），才可用“其他”取代“取值集合n”。情况条件型选择结构的算法周码，如图1.6所示，图1.6中：“?：”为各情况块引导符（它引导着情况条件型选择结构的选择对象属于“取值集合I”时，所要执行的操作块i），且仅最后一个情况块即a_n块尾，才能有分号“；”。

（3）循环结构的描述

① 当型选择结构的描述。当型循环结构的算法周码如图1.7所示。图1.7中，“当”为当型循环结构保留字，循环条件为逻辑型量；“@：”为循环体引导符，“循环体”（即满足循环条件时，所要执行的操作块）是当型循环结构的构成块（注：循环体是多操作构成块时，必须使用构成块的起止符）。

图1.6　情况条件型选择结构的同构化算法周码表示法（n≥2）

图1.7　当型循环结构的同构化算法周码表示法

② 直到型选择结构的描述。直到型循环结构的算法周码如图1.8所示。图1.8中，“直到”为直到型循环结构保留字，循环条件为逻辑型量。

图1.8　直到型循环结构的同构化算法周码表示法

③ 步长型选择结构的描述。步长型循环结构的算法周码如图1.9所示。

图1.9　（基于当型）步长型循环结构的同构化算法周码表示法

在图1.9中：

A．“对”为步长型循环结构保留字。

B．“循环变量←初值，终值，步长”顺次表示“循环变量、循环变量初值、循环变量终值，循环变量步长值”。

C．它的基型——“即作为其构造基础的循环结构类型”，可以是当型、直到型之一，但通常基本上都是当型循环结构，故本书只用后者。

（4）子算法结构的描述

① 子算法定义的描述。子算法定义的算法周码，其最简化语法图——语法周图，如图1.10所示（注：图1.10、图1.11所示语法周图中，各箭头线不是算法周码的构成部分，而是仅为“说明其后继语法成分是什么”的指向线。关于专用于描述计算机语言语法构造规则的语法周图，拟另文论述）。

图1.10　子算法定义的算法周码表示法的语法周图

② 子算法调用的描述。子算法调用的算法周码，其最简化语法周图如图1.11所示。

图1.11　子算法调用的算法周码表示法的语法周图

（5）特写结构的描述

应当明确指出，在程序设计中，“一眼就能洞穿、一气即可呵成”其算法的简单问题，一般说来并不多见。相反，对给定问题的算法设计通常不是一蹴而就的，往往要经过一系列逐步求精过程，才能越来越逼近并最终解决给定问题。为此，算法周码创新出可描述逐步求精过程的有力工具——特写结构，如图1.12所示。

图1.12中，“[ X=＆gt; ]”表示“特写结构X的缩影结构待扩大为其扩影结构”（如图1.12（A）所示）；“[ ＜=X ]”表示“特写结构X的扩影结构可缩小为其缩影结构”（如图1.12（B）所示）；而“特写结构X的缩影结构与扩影结构彼此本质等价”，且“特写结构X的缩影结构与扩影结构可以和必须最终合而为一——合成结构”（如图1.12（C）所示）。显然，不管是特写缩影结构还是特写扩影结构，其信息的内容和总量都完全相同。换言之，特写结构所表征的信息，既不因其缩影结构的缩小而减少，也不因其扩影结构的扩大而增加，更不因其合成结构的合成而变化。

图1.12　用于逐步求精的算法周码特写结构表示法

例1.2.1　解决“任给四个自然数作边长，试问可构成几个三角形？这些三角形的总面积是多少？”的算法Eg1201，可用算法周码描述如下：

算法Eg1201；{它是解决本书第1章第2节例1的算法（多组三角形判别并求总面积的算法）}

行输出 x，"，"，y，"，"，z，"可作三角形的三边，其面积为"，s；

@：\\ 输出 "自然数a，b，c，d=?"；输入a，b，c，d //；{输入任给4个整数}

直到a＆gt;0且b＆gt;0 且 c＆gt;0 且 d＆gt;0；{直到各整数全为自然数}

行输出 a，"，"，b，"，"，c，"，"，d，"作边长，可构成"，k，"个三角形；其总面积为"，s；

三、算法抽象程度

算法抽象程度，应可随其解决所论问题全过程的设计需要与描述粒度（指其精细化程度），而有所不同。因此，算法通常可分为三种（高、中、低）抽象度算法。

1．高抽象度算法

它非常粗略地描述解决所论问题的全过程，常用于算法总体框架设计。譬如解决例1.2.1的高抽象度算法Eg1201，可描述为：

入口参数：实型值参x，y，z；{提供三角形各边长}

出口参数：（函数名兼作）实型变参Fu01；{返回三角形面积}

2．中抽象度算法

它比较粗略地描述解决所论问题的全过程，多用于算法具体架构设计。譬如解决例1.2.1的中抽象度算法Eg1201，可描述为：

入口参数：实型值参x，y，z； {提供三角形各边长}

出口参数：（函数名兼作）实型变参Fu01； {返回三角形面积}

3．低抽象度算法

它比较详尽地描述解决所论问题的全过程，多用于算法指导编程设计。譬如例1.2.1所给出的算法Eg1201，实际上就是低抽象度算法，因为它已可很容易地用各种计算机高级语言来编程实现。