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