程序设计初步讲义.pdfVIP

程序设计初步

3.1算法初步及其描述方法

3.1.1算法初步

1.什么是算法

算法是为解决一个特定问题而采取的特定的有的步骤。广义地说，做任何

事情都有算法，例如一X太极拳打法图解也可以看作是一个“太极拳算法”。因

此，算法概念不于算术问题，而是具有更广泛的含义。

从计算机应用的角度来说，算法是指完成一个任务所需要的具体步骤和方法

解（决问题的方案）。也就是说给定初始状态或输入数据，经过计算机程序的有

次运算，能够得出所要求或期望的终止状态或输出数据。

【算法3.1】给定两个正整数p和q,求其最大公因数。

古希腊数学家欧几里德给出的算法：

步骤1：如果pq,交换p和q。

步骤2：求p/q的余数r。

步骤3：如果r=0,则q就是所求的结果。

否则反复做如下工作：☆p=q,q=r,重新计算p和q的余数r,直到r=0为

止，则q就是原来的两正整数的最大公因数。

算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或

不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同

的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时

间复杂度来衡量。

从原则上说，有了算法，人们就可以借助纸、笔和算盘等工具直接求解问题

了。但如果问题比较复杂，计算步骤很多，则应通过编写计算机程序，使用计算

机解决。

2.算法的特征

算法是在有步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,

就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都

是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。

一个算法应该具有以下五个重要的特征：

(1)有穷性：一个算法必须保证执行有步之后结束。

(2)确切性：算法的每一步骤必须有确切的定义。

(3)输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0

个输入是指算法本身定义了初始条件。

(4)输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没

有输出的算法是毫无意义的。

(5)可行性：算法原则上能够精确地运行，而且人们用笔和纸做有次运算后

即可完成。

3.算法的类型和结构

(1)算法的类型

算法可分为两大类：数值算法和非数值算法。

数值算法是为数学问题形成一个构造性解法的完备而切的描述，并规定方

法中仅允许使用加、减、乘、除等基本的算术运算。

非数值算法广泛应用在“数据处理”的场合。需要对大量的信息(数据)进

行加工处理，包括转换、分类、查找、排序和存储等。常用的算法有穷举、递推、

顺序查找和冒泡排序等。

(2)算法的结构

一个算法是由“结构”和“原操作”构成的。原操作包括：输入、输出、赋

值和比较等。算法的三种基本结构是：顺序结构、分支结构和循环结构。用这三

种基本结构可以表示任意一个复杂的算法。

①顺序结构

顺序结构是指通过安排操作的排列顺序来决定算法流程的结构。在这种结构

中，各个操作是依次执行的。顺序结构是由若干个依次执行的处理块组成，这是

任何一个算法都离不开的基本主体结构。

②分支结构

在绝大多数情况下，算法不会按部就班地从第一条操作执行到最后一条操作，

往往由特定的条件决定执行哪个操作，这就是分支结构。分支结构是以条件或情

况的判断为起始点，它是人脑判断思维活动的抽象。最基本的分支结构是二分支

结构，根据判断逻辑是否成立而决定选择哪一边的处理块去执行。

③循环结构

循环结构是指在算