算法设计与分析

在 C语言中，有 5 种常用的算法描述方法：自然语言、流程图、N-S 图、伪代码和程序设计语言。

1. 自然语言描述算法

上一讲《算法是什么》中给出的解决问题的算法 a、算法 b 和算法 c 都是用自然语言来表示算法的。自然语言就是我们日常使用的各种语言，可以是汉语、英语、日语等。

用自然语言描述算法的优点是通俗易懂，当算法中的操作步骤都是顺序执行时比较直观、容易理解。缺点是如果算法中包含了判断结构和循环结构，并且操作步骤较多时，就显得不那么直观清晰了。

2. 用流程图描述算法

用流程图描述算法就可以解决上述缺点。所谓流程图(Flow Chart)，是指用规定的图形符号来描述算法。

结构化程序设计方法中规定的三种基本程序流程结构(顺序结构、选择结构和循环结构)都可以用流程图明晰地表达出来(见图 1)。

图 1：用流程图表示的顺序结构、选择(条件分支)结构、循环结构三种流程

3. 用 N-S 图描述算法

虽然用流程图描述的算法条理清晰、通俗易懂，但是在描述大型复杂算法时，流程图的流向线较多，影响了对算法的阅读和理解。因此有两位美国学者提出了一种完全去掉流程方向线的图形描述方法，称为 N-S 图(两人名字的首字母组合)。

N-S 图使用矩形框来表达各种处理步骤和三种基本结构(见图 2)，全部算法都写在一个矩形框中。

图 2：用 N-S 图表示的顺序结构、选择(条件分支)结构、循环结构三种流程

图 3 展示了分别用自然语言、流程图和 N-S 图解决同一问题的算法描述。

图 3：分别用自然语言、流程图和 N-S 图描述的算法

4. 用伪代码描述算法

伪代码是用在更简洁的自然语言算法描述中，用程序设计语言的流程控制结构来表示处理步骤的执行流程和方式，用自然语言和各种符号来表示所进行的各种处理及所涉及的数据(见图 4)。它是介于程序代码和自然语言之间的一种算法描述方法。这样描述的算法书写比较紧凑、自由，也比较好理解(尤其在表达选择结构和循环结构时)，同时也更有利于算法的编程实现(转化为程序)。

图 4：常见的三种流程结构的伪代码

5. 用程序设计语言来描述算法

算法最终都要通过程序设计语言描述出来(编程实现)，并在计算机上执行。程序设计语言也是算法的最终描述形式(见图 5)。无论用何种方法描述算法，都是为了将其更方便的转化为计算机程序。

图 5：用伪代码和程序设计语言(C语言)描述的算法