C语言程序设计基础(第3版)：了解算法概念

2023-11-20 理论教育版权反馈

【摘要】：算法是对操作或行为的描述。算法代表着用系统的方法描述解决问题的策略。不同的算法可能用不同的时间、空间或效率来完成同样的任务。那么怎样衡量一个算法的正确性呢？算法包含的操作步骤应该是确定的，不允许有歧义。算法的实现是以得到计算结果为目的的，没有任何输出的算法没有任何意义。

所谓算法，简单地说，就是为了解决一个具体问题而采取的确定、有限有序、可执行的操作步骤。当然，程序设计中的算法仅指计算机算法，即计算机能够执行的算法。

程序设计是一门艺术，主要体现在算法设计和结构设计上。如果说结构设计是程序的“肉体”，那么算法设计就是程序的“灵魂”。

著名的计算机科学家沃思（N.Wirth）曾提出一个经典公式：

数据结构+算法＝程序

这个公式仅对面向过程的语言（如C语言）成立，它说明一个程序应由两部分组成：

（1）数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

（2）算法是对操作或行为（即操作步骤）的描述。算法代表着用系统的方法描述解决问题的策略。不同的算法可能用不同的时间、空间或效率来完成同样的任务。

计算机进行问题求解的算法大致可以分为以下两类：

①数值算法，主要用于解决数值求解问题。(www.chuimin.cn)

②非数值算法，主要用于解决需要用逻辑推理才能解决的问题，如人工智能中的许多问题以及搜索、分类等问题都属于这类算法。

那么怎样衡量一个算法的正确性呢？一般地，可用如下特征来衡量。

①有穷性。算法包含的步骤应该是有限的，每一步都应在合理的时间内完成，否则算法就失去了它的使用价值。

②确定性。算法包含的操作步骤应该是确定的，不允许有歧义。例如，“如果x≥0则输出Yes；如果x≤0，则输出No”就是有歧义的，即当x等于0时，既要输出Yes，又要输出No，这就产生了不确定性。

③有效性。算法中的每个步骤都应能有效执行，且能得到确定的结果，例如，对一个负数开平方或者取对数，就是一个无效的操作。

④允许没有输入或者有多个输入。有些算法不需要从外界输入数据，如计算5！；而有些算法则需要输入数据，如计算n！，而n的值是未知的，执行时需要从键盘输入n的值后再计算。

⑤必须有一个或者多个输出。算法的实现是以得到计算结果为目的的，没有任何输出的算法没有任何意义。