第二章  算法与程序设计
学完第一章后，知道了计算机所做的工作就是按指定的步骤执行一系列的操作，以完成某项特定的任务。因此，要计算机为我们做事，就必须事先为它设计出这一系列的操作步骤，并用计算机语言写成程序，这就是程序设计。解决问题的方法和步骤，称之为算法，它是程序设计的关键，因此，在学习用Quick BASIC语言进行程序设计之前，了解一点算法的知识是必要的，它是以后各章学习的基础。本章主要内容有：
? 算法的概念
? 用流程图表示算法
? 用结构化流程图（N-S图）表示算法
? 结构化程序设计步骤
2.1  算法的概念
2.1.1  什么是算法
计算一个算术式，要先乘除后加减，这个规则就是算法。使用算盘，珠算口诀就是算法。在日常生活中做任何一件事情，都是按照一定规则，一步一步地进行，比如乐队演奏、厨师炒菜都有各自的操作步骤，这也是算法。在工厂中生产一部机器，先把零件按一道道工序进行加工，然后，又把各种零件按一定方法组装成一部完整机器，它们的工艺流程就是算法；在农村中种庄稼有耕地、播种、育苗、施肥、中耕、收割等各个环节，这些栽培技术也是算法。总之，任何这些数值的计算或非数值计算的过程中的方法和步骤，都称之为算法。
计算机解决问题的方法和步骤，就是计算机的算法。计算机用于解决数值计算，如科学计算中的数值积分、解线性方程等的计算方法，就是数值计算的算法；用于解决非数值计算，如用于管理、文字处理、图形图像等的排序、分类、查找，就是非数值计算的算法。
下面举几个简单的例子，以说明计算机算法。
2.1 2  算法举例
[例2-1]  将两个变量X和Y的值互换。设X＝5，Y＝10。
问题分析：两人交换座位，只要各自去坐对方的座位就行了，这是直接交换。一瓶酒和一瓶醋互换，就不能直接从一个瓶子往另一个瓶子倒。必须借助于一个空瓶子，先把酒倒入空瓶，再把醋倒入空的酒瓶，最后把酒倒入已倒空的醋瓶，这样才能实现酒和醋的交换，这是间接交换。
计算机中交换两个变量的值不能用两个变量直接交换的方法，而必须采取间接交换的方法。因此，需设一中间变量为Z。
算法表示如下：
S1    将Y值存入中间变量Z：
S2    将X值存入变量中：X→Y
S3    将中间变量Z的值存入X中，Z→X
这里S1、S2…即Step1，Step2…的简写，用以标识执行的步骤，以后的例中均用此符号，不再说明。用一个示意图说明此算法，如图2-1所示。
 
图2-1  例1图
[例2-2]  求5个自然数的和 （即S＝1＋2＋3＋4＋5）
问题分析：该题有两个特点：
（1）重复执行加法，每加一个数，总和的值都在变；
（2）加数是一个有规则的等差数列，第1项是1，以后，每加一次，加数就增加1。因此，可以用以下算法实现。
算法1：
S1  设一存放累加和的变量S，初值置0，即0→S；设一个数变量N，初值0，即0→N。
S2  计算和S＋N→S，并把计数变量增值N＋1→N.
S3  判断：当N≤5时，返回第2步S2，再次求和，当N＞5时，顺序执行下一步S4。
S4  输出结果，S为所求之和。
算法2：
S1  0→S，1→N（同算法1）
S2  判断：当N≤5时，顺序执行下一步S3；当N＞5时，跳过S3、S4，执行第5步S5。
S3  S＋N→S，N＋1→N（同算法1）
S4  返回第2步S2。
S5  输出结果。（同算法1）
在这个算法里，出现了重复求和的操作，称为循环，这种循环必须用条件加以限制，让它进行有限次数就停止，否则，成为死循环。上述算法1的S3是条件判断，求和的操作是先执行，后判断：算法2的S2是条件判断，求的和操作是先判断，再执行。
[例2-3]  计算N！（即求1×2×3×…×N）的值。
问题分析：该题也有两个特点：（1）重复执行乘法的操作，每乘一次，积都在变；（2）乘数是一个有规则的等差级数，后项是前项加1，因此，可用以下算法实现。
S1  指定一个具体的N值，如5→N。
S2  设一累乘变量M，初值置1；设一计数变量P，初值置1。
S3  求积M×P→M，计数变量P增值P＋1→P。
S4  判断：当P＜N时，返回第3步S3；否则，往下执行S5。
S5  输出结果，即M为所求之和。
[例2-4]  求两个自然数M和N的最大公约数。
问题分析：最大公约数就是能同时整除M和N和最大正整数，这是一个古老的算术问题，我国宋代数学家秦九韶，希腊数学家欧几里得（Euclid）提出了各自不同的算法。
算法1：秦九韶算法
S1  输入两个自然数
S2  当m≠n时，顺序执行第3步，当m=n时，跳到第5步S5。
S3  当m＞n时，m-n→m，否则n-m→n
S4  返回第2步S2。
S5  输出结果，n为所求最大的公约数。
算法2：欧几里得算法
S1  输入两个自然数
S2  求余数：M/N，得到余数R（0＜R＜N）
S3  置换：N→M，R→N
S4  判断：当R≠0，返回第2步S2；当R＝0时，顺序执行第5步S5。
S5  输出结果，n为所求最大分约数。
综合上述算法示例看出，算法是解题方法的精确描述。算法并不给出问题的精确的解，只是说明怎样才能得到解。第一个算法都是由一系列的操作组成的。这些操作包括加、减、乘、除、判断、置数等，按顺序、分支、重复等结构组成。所以研究算法的目就是研究怎样把各种类型的问题的示解过程分解成一些基本的操作。
算法写好之后，要检查其正确性和完整性，再根据它编写出用某种高级语言表示的程序。程序设计的关键就在于设计出一个好的算法。所以，算法是程序设计的核心。
2.1.3  算法的特性
从上面的例子中，可以概括出算法的5个特性：
（1）算法中执行的步骤总是有限次数的，不能无休止地执行下去。这称之为有穷性。例如计算圆周率，可用如下公式：
π＝（1- …）
这个多项式的项数是无穷的，它是一个计算方法，不是算法。我们要计算π的值，只能取有限个项数。例如，取精确到第5位，那么，这个计算就是有限次的，因而才能称得上算法。
（2）算法中的每一步操作的内容和顺序必须含义确切。这称之为确定性。不能有二义性。
（3）算法中的每一步操作都必须是可执行的，这称之为有效性。
（4）要有数据输入。算法中操作的对象是数据，因此，应在进行操作前提供数据。
（5）要有结果输出，算法的目的是用来解决一个给定的问题，因此，它应向人们提供算法产生的结果，否则，就没有意义了。
了解算法的这些特性，对我们在程序设计中构造一个好的算法，是有重要指导意义的。
2.2  用流程图表示算法
描述算法有多种不同的工具，采取不同描述算法的工具对算法的质量有很大的影响。如上节中例1至4是用自然语言——汉语描述的算法。使用自然语言描述算法的最大优点是，人们比较习惯，容易接受，但也确实存着很多的缺点，一是容易产生二义性，例如，中文“走火”二字，既可以表达子弹从枪膛射出，又可表示电线上漏电，也可表示说话漏了嘴。二是比较冗长，三是在算法中如果有分支或转移时，用文字表示就显得不够直观，四是目前计算机不便于处理，所以自然语言不适合描述算法。在计算机中常用流程图、结构化流程图、计算机程序设计语言等类型的描述工具来表示算法。
流程图（Flowchart），亦称框图，它是用一些几何框图，流向线和文字说明表示各种类型的操作。流程图中的基本图形、图形意义和长度比例都有国家颁布的标准（GB ISO5807-85）。如图2-2所示。
 
图2-2  流程图的符号
处理框亦称矩形框有一个入口，一个出口。判断框亦称菱形框有一个入口，两个出口。在框内写上简明的文字或符号表示具体的操作，用带箭头和流向线表示操作的先后顺序。
流程图是人们交流算法设计的一种工具，不是输入给计算机的。只要逻辑正确，人们都能看得懂即可以了，一般是由上而下地按执行顺序画下来，下面是用流程图表示例1～4的算法。
从这4个例子看出，流程图的优点是形象直观，清晰明了，所以它很早就被广泛用在各种高级语言的程序设计中，常常称之为传流的流程图。
流程图可粗可细。粗流程图集中地概括了算法的总体逻辑结构，细流程图对算法的描述则比较细致而具体，其特点是详尽到足以直接凭借它就能用某种计算机语言顺畅地编写出相应的程序。
但是它也有不足之处，对于较复杂的问题，要详细地画出其过程，图形就显得特别长，占篇幅比较大。前后的流向线就不容易清楚表示。

                    
图2-3  交换变量流程图             图2-4  求5个自然数和流程图
                 
图2-5  求N! 流程图            图2-6  求最大公约数流程图
2.3  用结构化流程图（N-S图）表示算法
2.3.1  结构化程序的三种基本结构
1．什么是结构化程序
随着计算机的发展，编制的程序越来越复杂。一个复杂程序多达数千条语句，而且程序的流向也很复杂，常常用无条件转向语句去实现复杂的逻辑判断功能。因而造成质量差，可靠性很难保证，程序也不易阅读，维护困难，20世纪60年代末期，国际上出现了所谓“软件危机”。
为了解决定这一问题，就出现了结构化程序设计，它的基本思想是象玩积木游戏那样，只要有几种简单类型的结构，可以构成任意复杂的程序。这样可使程序设计规范化，便于用工程的方法来进行软件生产。基于这样的思想，1996年意大利的Bobra和Jacopini提出了3种基本结构，由这3种基本结构组成的程序，就是结构化程序（Structured Program）。
2．三种基本结构
（1）顺序结构
程序流程是沿着一个方向进行的有一个入口（A）、有一个出口（B），它包含两种情况：
? 简单的顺序结构，由程序的基本单元——语句组成的块，它没有分支，如图2-7（a）所示。
? 复合的顺序结构，它可以由若干基本结构的程序块组成，各块之间的关系是顺序走向的，没有分支的（这时，各块内可能有分支的情况）。如图2-7（b）所示。
          
（a）                                   （b）
图2-7  顺序结构
（2）选择结构
程序的流程发生分支，根据一定的条件选择其中之一，这就是选择结构。它也有一个入口（A），一个出口（B）。简单的选择结构是只有两个分支的情况，如图2-8所示。
 
图2-8  选择结构
（3）循环结构（亦称重复结构）
程序流程是有限次重复执行某一块程序。再退出循环。循环结构有两种类型：
? 当型（WHILE）循环结构，先判断条件是否满足，若满足时就执行循环体，如条件不满足时就不执行循环体，并转到出口。如图2-9（a）。
? 直到型（UNTIL）循环结构，它是后执行，先判断。当条件不满足时继续执行循环体；当条件满足时，停止执行，并转到出口。如图2-9（b）。
循环结构也有一个入口（A），一个出口（B），它应当使重复处理为有限次，不能无限制地下去。
                    
图2-9  循环结构
这种结构化程序具有以下特点：
? 只有一个入口和一个出口。
? 无死语句，既没有永远都执行不到的语句。
? 无死循环。即永远执行不完的循环。
2.3.2  结构化流程图（N-S图）
前面的图2-7、图2-8和图2-9，用框图表示了结构化程序的3种基本结构。看起来还清楚，但情况复杂时，图形中的流向线多，仍不便于阅读。所以美国人I.纳斯（I.Nassi）和B.施内德曼（B.Schneiderman）提出了一种的绘制流程图的方法。由于他二人的名字以N和S开头，故把这种流程图称为N-S图。这种结构化流程图，完全去掉了在描述中引起混乱的带箭头的流向线，全部算法由3种基本结构的框表示。
3种基本结构框的画法规定如下：
（1）顺序结构（Sequence Structure）
它由若干个前后衔接的矩形块顺序组成。一个顺序结构，如图2-10，先执行块A，然后执行块B。各块中的内容表示一条或若干条需要顺序执行的操作。
（2）选择结构（Choice Structure）
见图2-11所示，在此结构内有两个分支，它表示当给定的条件满足时A块的操作，条件不满足时，执行B块的操作。
        
图2-10  顺序结构流程图             图2-11  选择结构流程图
（3）循环结构（Repetition Structure）：
① 当型（WHILE）循环结构，见图2-12（a）。先判断条件是否满足，若满足就A块（循环体），然后再返回判断条件是否满足，如满足A块，如此循环执运，直到条件不满足为止。
② 直到型（UNTIL型）循环结构。见图2-12（b）。它先A块（循环体）然后判断条件是否满足，如不满足则返回再A块，若满足则不再继续执行循环体了。
        
图2-12  循环结构
用N-S图表示1至例4中算法，见图2-13至图2-16。
           
    图2-13  交换变量               图2-14  求5个自然数的和
              
  图2-15  求N！                图2-16  求最大公约数
将图2-13至图2-16的N-S图与图2-3到图2-6的传统流程图相比较，从中明显看出：N-S流程图是由基本结构单元组成的，各基本结构单元之间是顺序执行关系，即从上到下，一个结构一个结构地顺序执行下来。这样的程序结构，对于任何复杂的问题，都可以很方便地用以上3种基本结构顺序地构成。因而它描述的算法是结构化的，这是N-S图的最大优点。
和N-S图表示算法，思路清晰，阅读起来直观、明确、容易理解，大大方便了人们对结构化程序的设计，并能有效地提高算法设计的质量和效率。对初学者来说，使用N-S图还能培养良好的程序设计风格，因此本书在表示算法时，主要地采用了这种N-S图。
2.4  结构化程序设计步骤
在学习编写程序之前，对结构化程序设计的全过程有个全面的了解，从中可以知道用机器语言编写程序在全过程中的地位，这对培养和提高程序设计的能力很有好处。
完成一个正确的程序设计任务，一般可分为以下几个步骤进行，如图2-17所示。
 
图2-17  设计程序步骤
（1）提出和分析问题
即弄清提出任务的性质和具体要求。例如，提供什么数据，得到什么结果，打印什么格式，允许多大误差，都要确定。若没有详细而确切的了解，匆忙动手编程序，就会出现许多错误，造成无谓的返工或损失。
（2）构造模型
即把工程或工作中实际的物理过程，经过简化，构成物理模型，然后，用数学语言来描述它，这称为建立数学模型。
（3）选择计算法
即选择用计算机求解该数学模型的近似方法。不同的数学模型，往往要进行一定的近似处理。对于非数值计算则要考虑数据结构等问题。
（4）算法设计
即制订出计算机运算的全部步骤。它影响运算结果的正确性和运行效率的高低。
（5）画流程图
即用结构化流程图把算法形象地表示出来。
（6）编写程序
即根据流程图用一种高级语言把算法的步骤写出来，就构成了高级语言源程序。
（7）输入程序
即将编好的源程序，通过计算机的输入设备送入计算机的内存存贮中。
（8）进行试算（调试）
即用简单的、容易验证结果正确性的所谓“试验数据”输入到计算机中，经过执行、修改错误、再执行的反复过程，直到得出正确的结果为止。
（9）正式运行
即输入正式的数据，以得到预期的输出结果。
（10）整理资料
即写出一份技术报告或程序说明书，以便作为资料交流或保存。
2.5  本章小结
本意主要介绍了算法的概念和表示方法。
（1）算法就是为解决一个问题而采取的方法和步骤，程序设计的关键就是选择正确的、高效率的算法。计算机中的算法必须是计算机能执行的、无二义性、有限次执行后能停止的。
（2）算法的表示方法有很多种，本章仅介绍了传流程图N-S结构化流程图两种。在程序设计中，应重视用流程图表达算法。
（3）学习程序设计的过程，就是不断地讨论算法、积累算法，并用流程图和程序设计语言描述算法的过程，因此，在以后的学习中，应着重对问题进行分析，明确解题的思路和方法。
习题
1．什么是算法？它有何特征？为什么要研究它？
2．结构化程序设计有哪3种基本结构？用3种基本结构进行程序设计有何好处？
3．对下列各题写出算法，并画出N－S流程图。
（1）求n个数的平均值。
（2）求1至100之间全部奇数之和。
（3）求1+ …+ 之和。
（4）有10个数：a1,a2,……a10,找出其中的最大数。