算法与程序设计

第1章算法与程序设计简介

1.1初识算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。算法代表着用系统的方法描述解决问题的策略机制，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷或不适合于某个问题，执行这个算法将不会解决该问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时，能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。

在生活中，算法就是解决问题的步骤。例如，制作麻辣香锅的菜谱，会把制作麻辣香锅所必需的材料及用量都标注清楚，并且把烹制的过程、每一步需要的时间等都详细记录下来。只要完全按照菜谱的方法和步骤去做，就一定能烹制出美味的麻辣香锅。而算法就是能让程序员编写出可靠、高效的计算机程序的“菜谱”（如图1-1所示）。

编程的目的是让计算机解决特定的问题，编程之前首先需要明确计算机解决该问题的具体步骤，这个处理步骤就是编写该程序所需要的算法。解决一个问题可以用不同的方法和步骤，因而针对同一问题的算法也有多种多样的。例如，求1+2+3+…+100的和，有如图1-2所示的两种算法。

而编写程序就是通过某一种程序设计语言（比如C语言、Java语言）对算法的具体实现。算法独立于任何程序设计语言，同一算法可以用不同的程序设计语言来实现（如图1-3所示）。

1.1.1算法的基本概念

算法是解决问题的步骤，可以把算法定义成解决确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解决同一类问题的精确、有效的方法。算法+数据结构=程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序。解决同一个问题，我们会从两方面来考虑：一是与计算方法密切相关的算法问题（逻辑实现）；二是程序设计问题（物理实现）。算法和程序之间存在密切的关系。

1.算法的基本特征

（1）可行性（Effectiveness)

可行性是指算法中执行的任何计算步骤都可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称为有效性），简单地说就是：按着这个算法，是可以得出结果的，这种方法是可行的。

例如，若某计算工具具有7位有效数字，设A=1012，B=1，C=-1012，则A+B+C=0，A+C+B=1。所以，在设计一个算法的时候必须考虑可行性。

……