计算机等级考试二级C语言常用的算法

什么是程序？程序=数据结构+算法。
对于面向对象的编程，重点是数据结构，而对于C、P a s c a l、F O RT R A N等面向过程的编程语言，主要关注的是算法。掌握算法也为面向对象编程打下了坚实的基础。那么，什么是算法呢？

人们使用电脑来处理不同的问题。要做到这一点，人必须事先分析各种问题，确定解决问题的具体方法和步骤，然后编制一套指令，即程序，让计算机执行，交给计算机，使计算机按照人指定的步骤有效工作。这些具体的方法和步骤，其实就是解决一个问题的算法。根据算法，编写一个由计算机按照一定规则执行的命令序列就是编程，编写时要遵守的规则就是某种语言的语法。

因此，程序设计的关键之一是解决问题的方法和步骤，尤其是算法。学习高级语言的重点是掌握分析问题和解决问题的方法，即锻炼分析、分解并最终总结、整理算法的能力。相应的，特定语言的语法，比如C语言，就是工具，是算法的具体实现。所以在高级语言的学习中，一方面要熟练掌握该语言的语法，因为这是算法实现的基础；另一方面，要认识到算法的重要性，加强思维训练，才能写出高质量的程序。

以下示例显示了如何设计算法:

【例1-4】输入三个数字，然后输出数字。

首先，必须有一个地方来存放这三个数字。我们定义三个变量A，B，C，把这三个数依次输入A，B，C。另外，我们准备一个M A X数。由于计算机一次只能比较两个数，我们先把A和B的比值，较大的那个数放入MA X，然后把M A X和C比较，再把较大的那个数放入M A X，最后输出M A X，这时M A X包含A，B，C三个数中的一个，易科算法表

如下图所示:

1)输入a、b和C..

2)将A和B中较大的一个放入M A X。

3)将C和M A X中较大的一个放入M A X。

4)输出M A X，M A X是数字。

2)和3)的步骤还不清楚，不能直接转换成程序语句，可以进一步细化:

2)将A和B中较大的一个放入M A X，若A > B，则Max←A；否则MAX ←B b。

3)将C和M A X中较大的一个放入M A X，若C > M A X，则M A X ← C。

所以算法最终可以写成:

1)输入a、b和C..

2)若A > B，max←A；

否则m a x ← b。

3)如果C > M A X，M A X ← C。

4)输出M A X，M A X是数字。
这种算法可以很容易地转换成相应的程序语句。

【例1-5】猴子吃桃子的问题:桃子的数量未知。第一天，猴子吃了一半，觉得不够，又吃了一个。第二天，他又做了同样的事情，吃了一半剩下的桃子，又加了一个。这种事情每天都在发生。到了第十天早上，猴子发现只剩下一个桃子了。这堆里有多少桃子？

这个问题看起来有点粗糙，那么如何入门呢？假设第一天开始时有a1个桃子，第二天有a2个桃子，...第九天吃a9桃子，第十天吃a1 0桃子。在a1、a2、...，a1 0，只知道a1 0= 1。现在需要a1，我们可以看到a1、a2、...，a1 0:

a9= 2 * ( a1 0+ 1)

a8= 2 * ( a9+ 1)

┇

a1= 2 * ( a2+ 1)

即:ai= 2 * (ai+1+1) i=9，8，7，6，...,1

这是这个问题的数学模型。

然后考察上面从a9，a8到a1的计算过程，其实就是一个递归的过程。这种递归方法常用于计算机问题求解。另一方面，这九步操作在形式上是完全一样的，只是ai的下标不同。因此，我们引入循环处理方法，统一用a0表示前一天的桃子数，用a1表示第二天的桃子数，将算法改写如下:

1)a1 = 1；{第10天的桃数，初始值a1}

i = 9 .{计数器的初始值是9}

2) a0= 2 * ( a1+ 1).{计算一天中桃子的数量}

3) a1= a0 .{将当天的桃子数作为下一次计算的初始值}

4) i=i-1 .

5)如果i > = 1，则转2)。

6)输出a0的值。

2) ~ 5)是循环。

这是一个从具体到抽象的过程。具体方法是:

1)弄清楚如果是人做的话应该采取什么步骤。

2)总结这些步骤，抽象出数学模型。

3)对于重复的步骤，利用相同的变量找到形式的统一性，然后简单循环求解。

算法描述方法包括自然语言描述、伪代码、流程图、N-S图、PA D图等。

1.4.1流程图和算法的结构化描述

1.流程图

流程图是算法的传统表示法，用几何图形的方框来表示各种性质不同的运算，用流程线来表示算法的执行方向。因为简单直观，所以应用广泛，尤其是在语言早期阶段。只有流程图才能简洁地表达算法，流程图成为程序员交流的重要手段。直到结构化编程语言出现，对流程图的依赖才降低。

以下是一些常见的流程图符号和示例。
本章例1-1的算法流程图如图1-2所示。本章例1-2的算法流程图如图1-3所示。在流程图中，判断框左边的流程线表示判断条件为真时的流程，右边的流程线表示条件为假时的流程。有时，真、假或T、F、Y、N分别标在左右流线上方。

另外规定流线从下到上或从右到左时，必须有箭头。除此之外，没有画箭头，流线总是从上到下或者从左到右。

2.算法的结构化描述

早期的非结构化语言中有g o t o语句，允许程序直接从一个地方跳到另一个地方。这样做的好处是程序设计非常方便灵活，劳动复杂度降低，但其缺点也非常突出。大量的跳转语句使程序的过程变得非常复杂和无序，难以理解和验证程序的正确性。如果有错误，那就更难改正了。这个流程图所表达的混乱和复杂，正是程序员在软件危机中处境的生动写照。而结构化编程就是要理清这一团乱麻。