2.8　算法

2.8.1　算法概念

人们使用计算机，就是要利用计算机处理各种不同的问题，而要做到这一点，人们就必须事先对各类问题进行分析，确定解决问题的具体方法和步骤，再根据这些步骤，编制一组让计算机执行的指令（即程序），让计算机按人们指定的规则有效地工作。这些具体的方法和步骤，其实就是解决一个问题的算法。根据算法，依据某种规则编写计算机执行的命令序列，就是编制程序，而书写时所应遵守的规则即为某种语言的语法。由此可见，程序设计的关键之一是解题的方法与步骤，即算法。学习高级语言的重点和难点之一就是掌握分析问题、解决问题的方法，锻炼分析、分解问题并最终归纳整理出算法的能力。与此相对应的，具体语言（如C语言）的语法是工具，是算法的一个具体实现。所以在高级语言的学习中，一方面应熟练掌握该语言的语法——因为它是算法实现的基础；另一方面必须认识到算法的重要性，加强思维训练，寻找问题的最优解决方法，以编写出高质量的程序。

下面通过例2-8来介绍如何设计一个算法。

例2-8 设有一物体从高空坠下，每次落地后都反弹至距离原高度2/3差1m的地方，现在测得第9次反弹后的高度为2m，请编写程序，求出该物体从多高的地方开始下坠。

问题分析：

此题粗看起来有些无从着手，但仔细分析物体的运动规律后，能找到一些蛛丝马迹。假设物体坠落时的高度为h ₀ ，设第1～9次反弹的高度依次为h ₁ ，…，h ₉ ，现在只有h ₉ =2是已知的，但从物体的反弹规律能找出各反弹高度之间的关系：

可进一步转换为： ,i=1,2,…,9，这就是此题的数学模型。

算法设计：

上面从h ₉ 到h ₀ 的计算过程，其实是一个递推过程，这种递推方法在计算机解题中经常用到。另外，这些递推运算的形式完全一样，只是h _i 的下标不同而已。因此可以通过循环来处理。为了方便算法描述，统一用h ₀ 表示上一次的反弹高度，h ₁ 表示本次的反弹高度，算法可以详细描述如下：

5）若i≥1，转至步骤2。

6）输出h ₀ 的值。

其中第2～5步为循环，递推计算各次反弹的高度。

上面的示例演示了一个算法的设计过程，即从具体到抽象的过程，具体方法是：

1）弄清解决问题的基本步骤。

2）对这些步骤进行归纳整理，抽象出数学模型。

3）对其中的重复步骤，通过使用相同变量等方式求得形式的统一，然后简练地用循环解决。

算法的描述方法有自然语言描述、伪代码、传统流程图、N-S图及PAD图等，自然语言描述简单、明了，但是由于程序员之间母语的差别，妨碍了他们的正常交流，因此出现了后面四种算法描述形式，下面主要介绍流程图描述方法。如果读者对其他描述方法感兴趣，可以参考其他资料。

2.8.2　流程图与算法描述

可以用不同的方法来描述一个算法。常用的方法有自然语言、传统流程图、结构化流程图（N-S图）和伪代码等。

其中使用最广泛的是传统流程图。传统流程图又称为程序框图，是一种传统的算法表示法，它利用几何图形的框来代表各种不同性质的操作，用流程线来指示算法的执行方向。由于它直观形象，部分消除了不同国籍程序员之间的交流障碍，所以应用广泛。

下面首先介绍常见的流程图符号及流程图的示例。图2-2给出了一些常见的流程图标准符号。

●起止框。表示算法的开始和结束。一般内部只写“开始”或“结束”。

●输入/输出框。表示算法请求输入/输出需要的数据或算法将某些结果输出。一般内部常常填写“输入……”，“打印/显示……”。

●判断框（菱形框）。主要是对一个给定的条件进行判断，根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口，两个出口。给定条件成立时在出口处标明“是”或“Y”，不成立时标明“否”或“N”。

●处理框。表示算法的某个处理步骤，一般内部常常填写赋值操作。

●流程线。用于指示程序的执行方向。

●连接点。用于将画在不同地方的流程线连接起来。同一个编号的点是相互连接在一起的，实际上同一编号的点是同一个点，只是画不下才分开画。使用连接点可以避免流程线交叉或过长，使流程图更加清晰。

●注释框。注释框不是流程图中必要的部分，不反映流程和操作，只是为了对流程图中某些框的操作做必要的补充说明，以帮助阅读流程图的人更好地理解流程图的作用。

在上述基本流程图符号的基础上，可以用一个完整的流程图来描述例2-8的算法。其流程图如图2-3所示。