3.3　如何描述算法

算法包含算法设计和算法分析两方面内容。算法设计主要研究怎样针对某一特定类型的问题设计出求解步骤，算法分析则要讨论所设计出来的算法步骤的正确性和复杂性。

算法设计者必须将自己设计的算法清楚、正确地按步骤记录下来，这个过程称为描述算法。可以用不同的方法表示一个算法，常用的有自然语言、流程图、N-S流程图等，下面将介绍算法的描述。

3.3.1　自然语言

自然语言就是日常生活中的语言，可以是汉语、英语、日语等。一般采用自然语言描述一些简单问题的步骤。

但是自然语言也存在有严重的缺陷，概括其缺点如下：

（1）使用自然语言描述算法，文字冗长。

（2）易于产生歧义，一个词组通常会含有不同的含义。

（3）使用自然语言描述分支语句或循环语句时很不方便，不够直观。

下面通过具体实例来介绍自然语言：

【例3-1】编写程序，鸡兔同笼，共有头6只、脚16只，问鸡兔各几只？（源代码\ch03\3-1）

第一步：定义2个变量分别为x、y。x代表鸡的数量，y代表兔子的数量。

第二步：通过数学分析可得：x+y=6；2*x+4*y=16；变换方程式并计算鸡的数量x=（4*6-16）/2。

第三步：计算兔子的数量y=（16-2*6）/2。

第四步：打印输出鸡和兔子的数量。

    #include <stdio.h>
    int main()
    {
    int x,y;
    x=(4*6-16)/2;
    y=(16-2*6)/2;
    printf("鸡的数量x=%d \n兔的数量y=%d\n",x,y);
    return 0;
    }

运行上述程序，结果如图3-9所示。

图3-9　求鸡和兔的数量

【代码解析】

本例按照所描述的自然语言转换为计算机C代码编写程序实现算法。在代码中首先定义2个变量x，y。但计算机不会解方程式，而需要对模型进行求解。应分别求出鸡兔的数量与头、脚数量之间的关系，即抽象出两个方程式：x+y=6；2*x+4*y=16；再计算出鸡和兔子各是多少。所以自然语言来描述复杂型的算法会十分不便，除了简单的问题，一般情况下不建议使用自然语言描述。

【例3-2】编写程序，求正整数a和正整数b的最大公约数。（源代码\ch03\3-2）

第一步：首先输入两个整数a和b，然后判断大小。若a>b，就交换a与b的数据。

第二步：将小的整数作为被除数，用一个中间量i代替b，从i开始，如果b%i==0，则说明a，b的最大公约数就是b，否则执行第3步。

第三步：i自减1，再执行a%i，判断a%i==0，如果是，说明a能被i整除；执行第4步，否则再次执行第3步。

第四步：如果a和b能同时被i整除，最大公约数为i；否则执行第3步。

运行上述程序，结果如图3-10所示。

图3-10　求最大公约数

【代码解析】

本例根据自然语言所描述的算法编写出相应的程序，求出两个整数的最大公约数。在代码中首先定义了3个变量a、b、c以及i，然后使用scanf()函数通过输入端获取a、b的值，通过变量c，判断a与b的大小，若a>b，则交换a与b的数据，此时a中存放着b的数据。再用中间量i代替a，然后依次循环，直到i即能被a整除，又能被b整除，那i就是最大公约数。

3.3.2　流程图

流程图是一种传统的算法表示法，它用一些图框来代表各种不同性质的操作，用流程线来指示算法的执行方向。由于它简单直观，易于理解，所以应用广泛。常见的流程图符号如图3-11所示。

图3-11　流程图所使用的几何图形框

其中起止框用于表示算法的开始与结束；判断框用于对一个条件表达式进行判断，并且根据判断的结果来决定执行怎样的后续操作；输入输出框，用于数据的输入与输出；处理框通常用于执行表达式语句等；流程线用于将前后流程进行连接，并表明程序执行的方向；注释框是对执行语句的说明；连接点用于将两个不同的流程线连接起来。

在流程图的使用过程中，Bohra和Jacopini两人为了使算法的质量有所提高，经过研究提出了3种基本结构，分别是顺序结构、选择结构以及循环结构。他们认为传统的流程图若是无限制地使用流程线有可能会导致流程图毫无规律可言，而经过改造，使用上述3种基本结构可以构造出一个良好的算法基本单元，使得流程图具有规律性，并且这种改进也能够令流程图具有结构化的性质，人们在阅读时更能够理解所描述的算法。

3.3.3　三种基本结构

经研究发现，任何复杂的算法，都可以由顺序结构、选择结构和循环结构这3种基本结构组成，这3种基本结构之间可以并列，可以相互包含，但不允许交叉，不允许从一个结构直接转到另一个结构的内部。

整个算法都是由3种基本结构组成的，所以只要规定好3种基本结构的流程图的画法，就可以画出任何算法的流程图。

1．顺序结构

顺序结构是最简单的线性结构，它的代码在执行的时候是按照语句的先后顺序逐条执行的，也就是从上至下，一条一条执行，不会漏过任意一条语句或者代码。

顺序结构的执行过程，如图3-12所示。

图3-12　顺序结构

根据语句的先后顺序，先执行语句A，然后执行语句B。例如：输入两个数分别赋给变量a和b，再将这两个数分别输出。可以采用顺序结构来实现，如图3-13所示。

图3-13　采用顺序结构输出变量的值

2．选择结构

选择结构又称分支结构，有两种选择结构形式，如图3-14和图3-15所示。

图3-14　选择结构（一）

图3-15　选择结构（二）

通过判断某个条件表达式的结果成立与否，来执行相应的操作时，需要使用到选择结构。例如：输入一个数，判断该数是否是偶数，并给出相应提示。可以采用选择结构来实现，如图3-16所示。

图3-16　判断奇偶数

3．循环结构

如果一个算法需要根据条件的成立来不停地反复执行一系列操作，直到给定的条件不成立时才结束循环，这样的结构被称为循环结构。根据判断条件所在的位置的不同，可以分为两种循环，它们是当型循环和直到型循环。

当型循环与直到型循环，如图3-17、图3-18所示。

图3-17　当型循环

图3-18　直到型循环

在当型循环结构中，首先要判断条件是否成立，若条件成立，则执行操作A，然后再回到判断条件的步骤；若是条件仍成立，则继续执行操作A……直到判断条件不成立时，则结束循环。在当型循环中，若是第一次判断条件时不成立，那么会直接跳过循环。

在直到型循环结构中，首先执行一次操作A，然后进行条件判断环节，若是条件成立，则执行操作A，再进行条件判断……反复执行直到条件不成立时结束循环。在判断条件之前，需要执行一次操作A。

例如：求1到100（包括1和100）之间所有整数之和。本例用当型循环结构来表示的流程图，如图3-19所示。本例也可以用直到型循环结构来表示的流程图，如图3-20所示。

图3-19　当型循环求和

图3-20　直到型循环求和

4．综合运用

【例3-3】通过流程图将算法表示出来：求1*2*3*4*5，并将结果输出。（源代码\ch03\3-3）

用流程图表示，如图3-21所示。

图3-21　求1到5乘积的流程图

    #include <stdio.h>
    int main()
    {
    int i,j;
    i=1;
    j=1;
    while(i<=5)
    {
    j=j*i;
    i++;
    }
    printf("j=%d\n",j);
    return 0;
    }

运行上述程序，结果如图3-22所示。

图3-22　求1到5的乘积

【代码解析】

本例根据所绘算法的流程图，编写相应的程序，用于计算“1*2*3*4*5”。在代码中首先定义两个变量i和j，然后使用while循环，先计算一次“j=j*i”的值，然后做i的自增运算，然后在判断当i小于等于5时再次进行循环，直到i为5时停止循环，最后输出结果，也就是最后的阶乘。

【例3-4】通过流程图将算法表示出来：判断2010～2020年中的哪些年份为闰年，并打印出来。（源代码\ch03\3-4）

判断某年是否为闰年，用流程图表示，如图3-23所示。

图3-23　判断某年是否为闰年流程图

运行上述程序，结果如图3-24所示。

图3-24　判断某年是否为闰年

【代码解析】

本例根据所绘算法的流程图，编写相应的程序，用于判断某年是否为闰年，并输出判断的结果。在代码中首先定义一个int型变量i，接着在2010~2020年依次查找，使用嵌套if…else语句对该年份进行判断，第一步先判断i是否能被4整除，若不能，则不是闰年，若能，则进行判断，i是否能被100整除，若不能，则是闰年，否则再进行判断，i是否能被400整除，若不能，则i不是闰年，若能，则i是闰年。

3.3.4　N-S流程图

N-S图如同一个多层的盒子，又称盒图（box diagram）。它比文字描述直观、形象、易于理解；比传统流程图紧凑易画，尤其是它废除了流程线，整个算法结构是由各个基本结构组成的，N-S流程图的上下顺序就是执行时的顺序，也就是图中位置在上面的先执行，外置在下面的后执行。写算法和看算法只需从上到下就可以了，十分方便。用N-S图表示的算法都是结构化的算法（它不可能出现程序无规律的跳转，而只能自上而下地顺序执行）。

一个结构化的算法是由一些基本结构顺序组成的；在基本结构之间不存在向前或向后跳转，流程的转移只存在于一个基本结构范围之内（如循环中流程的跳转）；一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变。如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化算法。

1．顺序结构

N-S流程图的顺序结构，如图3-25所示。

该图是通过A和B组成的顺序结构，其中A和B可以是简单的操作语句，也可以是3种基本结构其中之一，如图3-26所示。

图3-25　N-S流程图的顺序结构

图3-26　采用N-S顺序结构输出变量的值

2．选择结构

N-S流程图的选择结构，如图3-27所示。

其中，先判断条件，若是条件成立，则执行A操作，若是条件不成立则执行B操作，图中的“T”表示“true”，“F”表示“false”，如图3-28所示。

图3-27　N-S流程图的选择结构

图3-28　采用N-S选择结构判断奇偶数

3．循环结构

循环结构与传统流程图一样，也分为当型循环与直到型循环，如图3-29、图3-30所示。

图3-29　当型循环

图3-30　直到型循环

当型循环在执行时首先判断条件，若条件成立，则执行操作A，执行完毕后再返回判断条件，若条件仍成立，则继续执行操作A……直到判断条件不成立结束循环。

直到型循环在执行时，首先执行操作A，然后判断条件，若成立则继续执行操作A……如此反复直到条件不成立时结束循环。

当型循环与直到型循环虽然都具有循环的功能，但是当型循环是先判后执行，若是条件不成立，则一次都不会执行；而直到型循环是先执行后判，就算是条件不成立，也会执行一次。

当型循环求和与直到型循环求和的流程分别如图3-31和图3-32所示。

图3-31　当型循环求和

图3-32　直到型循环求和

4．综合运用

【例3-5】编写程序，通过流程图将算法表示出来：从输入端输入一个年份，如2016年，判断该年份是否为闰年，输出判断结果。（源代码\ch03\3-5）

判断某年是否为闰年，用流程图表示，如图3-33所示。

图3-33　N-S流程图查找闰年

运行上述程序，结果如图3-34所示。

图3-34　判断闰年

【代码解析】

本例根据所绘算法的流程图，编写相应的程序，用于判断某年是否为闰年，并输出判断的结果。在代码中首先定义一个int型变量y，接着通过输入端输入一个年份，使用嵌套if…else语句对该年份进行判断，第一步先判断y是否能被4整除，若不能，则不是闰年，若能，则进行判断，y是否能被100整除，若不能，则是闰年，否则再进行判断，y是否能被400整除，若不能，则y不是闰年，若能，则y是闰年。

3.3.5　伪代码

伪代码是一种使用文字与符号相结合的描述方法，它介于自然语言与机器语言之间。因为使用伪代码不必去遵循计算机语言那种严格的语法规则，使用时只需要借助一些计算机语言中的控制结构，通过自然语言以及程序设计语言对算法进行相应的描述即可。由于伪代码中不需要用到图形符号，所以书写起来十分方便，更易于理解，能够便于开发人员向计算机语言转化。

1．伪代码的特点

（1）伪代码实际上是计算机代码的简略形式，它比流程图更像计算机代码。

（2）伪代码必须结构清晰，代码简单，可读性好。

（3）伪代码要求程序设计人员集中于解决问题而不是计算机语言。

2．伪代码的应用

伪代码（Pseudocode）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（Pascal、C、Java等）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。介于自然语言与编程语言之间。

伪代码只是像流程图一样用在程序设计的初期，帮助写出程序流程。简单的程序一般都不用写流程、写思路，但是复杂的代码，最好还是把流程写下来，总体上去考虑整个功能如何实现。写完以后不仅可以用来作为以后测试、维护的基础，还可用来与他人交流。但是，如果把全部的东西写下来必定会浪费很多时间，那么这个时候可以采用伪代码方式。

2．语法规则

例如，类Pascal语言的伪代码的语法规则是：在伪代码中，每一条指令占一行（else if例外）。指令后不跟任何符号（Pascal和C中语句要以分号结尾）。书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对于其父级模块的语句缩进。

例如：

    if 九点以前 then
     do 私人事务；
    else 9点到18点then
    工作；
    else
    下班;
    end if

这样不但可以达到文档的效果，同时可以节约时间；更重要的是，使结构比较清晰，表达方式更加直观。

【例3-6】编写程序，输入3个数，打印输出其中最大的数，可用如下的伪代码表示。（源代码、ch03\3-6）

首先使用伪代码表示算法：

    Begin(开始算法)
    input a b c Max;
    if a>b
    a->Max;
    else
    b->Max;
    if c>Max
    c->Max;
    print Max;
    end
    结束

将伪代码转换为C代码：

运行上述程序，结果如图3-35所示。

图3-35　输出最大值

【代码解析】

本例将排列大小伪代码转换为C语言代码。在代码中首先定义4个变量a、b、c、temp。然后通过输入端输入a、b、c的值，通过if..else嵌套语句对3个数进行排列：首先比较a与b的大小，若a<b，则将两数交换；然后判断a与c的大小，若a小于c则将两数交换；最后再比较b与c，若b<c，则将两数交换。此时，输出a、b、c，已经按照由大到小进行排列。

【例3-7】编写程序，求解1到100的和。（源代码\ch03\3-7）

首先使用伪代码表示算法：

    开始
    for i=1 to 100
    sum=sum+i;
    end for结束

将伪代码转换为C代码：

    #include <stdio.h>
    int main()
    {
    int i,sum;
    sum=0;
    printf("计算1到100的和\n");
    for(i=1;i<=100;i++)
    {
    sum=sum+i;
    }
    printf("sum=%d\n",sum);
    return 0;
    }

运行上述程序，结果如图3-36所示。

图3-36　计算1到100的和

【代码解析】

本例用于演示如何将求最大公约数的伪代码转换为C语言代码。在代码中首先定义两个变量i和sum。变量i用于for循环的条件表达式，sum用于存放每次累加后的值。然后通过for循环实现从1加到100，最后输出sum的值。

3.3.6　计算机语言

说起计算机语言，其实大家不会很陌生，例如使用VC进行编译运行的例子代码就是使用了计算机语言。使用计算机语言，要严格地遵守该语言的语法规则、书写规则等。

【例3-8】使用C语言编写程序，输入一个正整数，判断是奇数还是偶数。（源代码\ch03\3-8）

运行上述程序，结果如图3-37。

图3-37　判断奇偶数

【代码解析】

本例为简单的C语言判断，通过计算机语言将判断的算法通过计算机实现。在代码中首先定义变量a，并在键盘上输入一个正整数，然后使用if…else语句，对正整数进行判断。

由此可以看出计算机语言在表示算法时具有以下特点：

（1）由上至下。

（2）逐步细化。

（3）模块化的设计。

（4）结构化的编码。