1.3 算法的描述工具

算法是为解决某个特定问题而采取的确定且有限的步骤，算法的描述工具也多种多样。本节主要介绍利用自然语言、图形和计算机语言的描述方法。

1.3.1 自然语言

采用自然语言对算法的描述称为伪代码。所谓伪代码是指用自然语言和指令语句（不要求绝对正确的语句）结合起来描述算法的一种方式。

这种方式的特点是比画流程图省时省力，转换为程序容易，但是清晰度层次性不如流程图。伪代码描述算法没有统一规定，写出来只要自己或别人能看懂就行。如已知圆的半径求圆的面积，算法可以描述为：

（1）输入半径r；

（2）计算面积：s=3.14*r2；

（3）输入面积：s。

1.3.2 图形

图形的描述方法通常有两种：传统的流程图和NS流程图。

1. 传统流程图

传统流程图是描述算法的一种常用工具，是由如图1-8 中所示的几种基本框和方向线组成。

由这些框和方向线组成的流程图来表示算法，允许任意转向，形象直观，简单方便。但是，用这种流程图描述复杂的算法时，所占篇幅较多，勾画费时费力，且描述复杂问题时不易阅读。

2. N-S流程图

N-S流程图是由美国学者I.Nassi和B. Shneiderman于1973年提出来用于描述算法的一种形式。算法的每一步都用一个矩形框来描述。把一个个的矩形框按执行的先后次序连接起来就构成了一个完整的算法描述。N-S流程图的特点是取消了流程线，禁止任意转向，描述复杂算法时和传统流程图相比所占篇幅要少得多，勾画时也省时省力，层次性、易读性要好于传统流程图。

N-S流程图常用的矩形框如图1-9、图1-10、图1-11和图1-12所示。

顺序结构框：先执行a块语句，再执行b块语句。

条件结构框：如果条件P成立（满足），则执行a块；如果条件P不成立（不满足），则执行b块。

循环结构框1：当给定条件满足执行a块一次，再次判断给定条件P是否满足，如果满足，则再次执行a块一次。如此往复直到给定条件不满足为止。

循环结构框2：先执行a块一次，判断给定条件是否满足，如果满足，则再次执行a块一次。如此往复直到给定条件不满足为止。

1.3.3 计算机语言

采用计算机语言对算法进行的描述，也就是计算机程序。采用计算机语言描述算法的关键是养成一种良好的程序书写风格。程序书写风格是程序设计人员在长期编程过程中所养成的一种书写程序的习惯。养成好风格的目的是为了阅读、修改程序的方便；好风格的程序可以减少程序的错误。要养成良好的程序书写风格需要从以下几个方面入手：结构化编码、程序的清晰性、变量和表达式、输入和输出、程序的效率、程序注释。

1. 结构化编码

结构化编码应遵循的原则是使用顺序、选择和循环三种基本结构来表示程序的逻辑结构；每种结构只能有一个入口和一个出口；复杂结构应是三种基本结构的组合；语言中没有的控制结构，应采用前后一致的方法来表示和模拟；严格控制GOTO语句的使用。

2. 程序的清晰性

保持程序的清晰性需要注意以下几个方面：简单明了地说明你的意图；培养好的书写程序的方式：一个语句占一行；利用空格和空行增加清晰性；采用锯齿（缩进）形式书写。使程序按自顶向下方式阅读；避免使用then if和空else结构；把与判定相联系的动作尽可能地紧挨着判定；使用使程序更简单的数据表示方法；使用子程序，实现模块化程序设计；每一个模块应能做好一件事情；让机器去干苦活。

3. 变量和表达式

程序中大量地使用变量和表达式，对变量和表达式的书写应注意：

（1）变量名的选择。变量名要有自说明性；不要用相似的变量名；不要有变量的多义性；对变量要先定义后使用；对重要变量作注释说明。

（2）表达式的书写。尽量少用中间变量；注意使用括号保持运算的顺序；注意浮点运算的误差；不要单独进行浮点数相等的比较；注意整数的运算（i/2*2）；注意复合条件式的书写。

4. 输入和输出的原则

输入和输出的原则主要有：输入的有效性校验；用文件尾或终止标志结束输入，而不用记数终止输入；使输入容易准备，输出容易解释；采用统一输入格式；把输入和输出局限在子程序内；确信在使用之前，变量已经赋值。

5. 程序的效率

在保证程序的效率上要注意：使用标准函数；使用公共表达式；程序要先保证正确，再求运行速度；使程序清晰比运行快更重要；让编译程序去做简单的优化。

6. 程序注释

程序注释可以提高程序的可读性，便于以后对程序的修改和完善。程序注释分为序言性注释和描述性注释。序言性注释是指出现在程序首部的注释，主要用于描述有关模块功能的描述；界面描述：调用形式、参数等；重要变量的使用与限制；开发历史：作者、复查修改日期等。描述性注释是指对程序的功能和状态进行的描述，它出现在被描述程序段的前后。

注释使用的原则是：注释应与程序一致；注释应提供一些从程序本身得不到的东西；对程序段注释，一般不对一个语句注释。

1.3.4 算法描述举例

【例1-1】求前N个自然数的和。

分析：用计算解决这个问题，首先考虑这N个自然数存放在哪？其和存放在哪？其次，考虑这N个自然数如何输入到计算机中；再次，考虑求和问题；最后考虑如何把和显示出来。

用自然语言描述：

（1）给出N的值；

（2）设求和变量S的初值为0；

（3）由x产生第1个自然数1；

（4）把x加到S中；

（5）x=x+1产生下一个自然数；

（6）如果x小于等于N就转到（4），否则，执行（7）；

（7）输出S。

用N-S图描述如图1-13所示。

用流程图描述如图1-14所示。

用C语言描述如下：

    #include "stdio.h"
    main()
    {
        int  x,n,s;                  /＊ 定义变量 ＊/
        printf("N=");                /＊ 提示输入N ＊/
        scanf("%d",&n);              /＊ 从键盘输入N的值 ＊/
        x=1;
        while(x<=n)                  /＊ 前N个自然数求和 ＊/
        {
            s=s+x;
            x=x+1;
        }
        printf("1+2+…+%d=%d\n",n,s); /＊ 打印和 ＊/
    }