5.2 算法的描述方法
5.2 算法的描述方法
算法是用于描述一个问题的解决方法，但是算法在描述问题时，也要有一个类似人们交流语言的工具作为描述载体，通常可以使用自然语言描述、流程图描述、伪代码描述和使用程序设计语言描述。本节将围绕这 4 种方法进行介绍。
5.2.1 使用自然语言描述法
例 5-1 至例 5-3 中所使用的算法描述方法都是用自然语言描述。自然语言描述就是运用日常交流语言作为描述算法的工具对算法设计操作步骤。自然语言可以是现今使用的多种语言，例如汉语、英语、法语、德语等都可以用于描述算法。
采用自然语言描述算法，通俗易懂，便于理解，通用性比较强，即使是不懂计算机的人也能够看懂用自然语言描述的算法。但是自然语言有其自身的缺点，例如同样的语言描述在不同的环境中，会使人产生不同的理解，具有一定的歧义性；自然语言描述问题时比较冗长，通常情况下对于比较简单的问题才用自然语言描述。
5.2.2 使用流程图描述法
流程图描述法是美国国家标准化协会 ANSI（American National Standard Institute）提出的，目前已被各国程序设计工作者所普遍使用。流程图描述法是采用图形描述法，对于算法阅读者而言，图形描述简洁、易懂、直观形象。
流程图中的元素包括起止框、输入/输出框、判断框、处理框、流程线、连接点、注释框等，其各个元素的对应形状如图 5.1 所示。在流程图描述法中，一个流程图只允许有一个开始符和一个结束符，因此在流程图的构成元素中起止框在一个流程图中只允许出现两次，一个用于开始，一个用于结束；输入输出框用于描述输入/输出数据；判断框用于描述选择结构的程序语句，所以判断框有两个输出，分别对应「是」和「否」两种条件判定结果。
处理框用于描述顺序结构的程序语句；流程线用于将流程图中的各个元素连接起来；连接点用于将各个流程图连接起来，当流程图比较庞大时，将其合并在一起比较困难，此时就需要将流程图分裂开来，分裂时通常从流程图的某一条流程线处分开，并在此流程线处标注分裂号，同时在另一流程图的入口位置标注同样的分裂号，以表示两个流程图在此标号处连接，如图 5.2 所示。
加载中...
图 5.1 流程图构成元素
加载中...
图 5.2 流程图连接点
注释框的作用在于为流程图中各个操作添加说明。注释框不是程序流程图的必要构成部分，可以根据需要在流程图的适当位置，为其添加必要的文字说明，以帮助流程图的阅读者更好地理解流程图的作用。例 5-1 用流程图法描述如图 5.3 所示，例 5-3 用流程图法描述如图 5.4 和图 5.5 所示，例 5-4 流程图法描述如图 5.6 所示。
从上述的几个例子中，可以看到流程图是按自上而下顺序执行的，对于简单的问题，采用流程图描述法直观形象；由于流程图中的流程线可以随意拉向任意方向，所以当算法算得比较复杂时，流程线会变得比较乱，判断符号比较多时，流程线会随条件判定的结果形成任意走向，上上下下的流程线造成多线交叉的局面，即使运用连接点可以缓解此类问题，但仍然无法从根本上解决流程图的混乱局面。这样会使流程图的阅读者顺着流程线转来转去，最终陷入混乱的逻辑走向。
例 5-1、例 5-3、例 5-4 是很有代表性的例子，每个例子都代表了程序的 3 种基本结构之一，其中例 5-1 是一个顺序结构程序，例 5-3 是一个选择结构程序，例 5-4 是一个循环结构程序。这 3 种基本结构是 1966 年 Bohra 和 Jacopini 提出的。
顺序结构程序指的是程序按从上到下的顺序执行，在程序流程图上看就是处理框描述的信息，按照流程线指示的方向逐步执行至结束。选择结构程序是一种条件判断语句，当条件满足不同条件时，执行对应的语句，在程序流程图中就是判断框描述判断的条件，判断框的出口分别对应了所要执行的语句，两个出口中，只会执行一个出口的语句，因为条件判定结果，要么为真，要么为假。循环结构程序是指设定循环变量初始值和循环进行的条件，在循环内部可以包含顺序结构程序和选择结构程序用于处理数据。在程序流程图中，没有专门的元素描述循环结构的程序，循环结构的程序是由顺序结构与选择结构共同描述的，例如在图 5.6 中所描述的循环结构。
加载中...
图 5.3 例 5-1 算法流程图
加载中...
图 5.4 例 5-3 常规算法流程图
加载中...
图 5.4 例 5-3 优化后的流程图
加载中...
图 5.6 例 5-4 算法流程图
5.2.3 使用 N-S 图描述法
N-S 图描述法是 1973 年美国学者 I.Nassi 和 B.Shneiderman 提出的一种全新的流程图表示形式。其表示方法是将全部算法都描述在一个矩形框内，矩形框之间可以相互嵌套，矩形框内省略了传统流程图的流程线。N-S 图对 3 种基本结构的描述如图 5.7 至图 5.10 所示。
加载中...
图 5.7 顺序结构描述
加载中...
图 5.8 选择结构描述
加载中...
图 5.9 while 型循环描述
加载中...
图 5.10 直到型循环描述
Tips
循环结构分为 2 种，即 while 型循环和直到型循环，还有一种 for 型循环，其本质上同于 while 型循环。在传统流程图中这两种循环在表示形式上只有一种，需要靠转化循环条件来表示。在 N-S 图中可以用两种结构明确表示两种循环。这两种循环的区别在于：条件判定的先后，是否让循环体执行一次，对于 while 循环，循环体只有当条件满足时才可以执行，而直到型循环的循环体至少会执行一次，当条件满足时会有后续的循环，条件不满足时，会跳出循环体，继续执行其余程序语句。