我们来自五湖四海,不为别的,只因有共同的爱好,为中国互联网发展出一分力!

算法

2012年10月03日01:18 阅读: 16718 次
什么是程序?程序= 数据结构+ 算法。

对于面向对象程序设计,强调的是数据结构,而对于面向过程的程序设计语言如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比,大的数放入M A 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。

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只,. . .,第9天有a9只,第1 0天是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; {第1 0天的桃子数,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语句,它允许程序从一个地方直接跳转到另一个地方去。执行这样做的好处是程序设计十分方便灵活,减少了人工复杂度,但其缺点也是十分突出的,一大堆跳转语句使得程序的流程十分复杂紊乱,难以看懂也难以验证程序的正确性,如果有错,排起错来更是十分困难。这种转来转去的流程图所表达的混乱与复杂,正是软件危机中程序人员处境的一个生动写照。而结构化程序设计,就是要把这团乱麻理清。

经过研究,人们发现,任何复杂的算法,都可以由顺序结构、选择(分支)结构和循环结构这三种基本结构组成,因此,我们构造一个算法的时候,也仅以这三种基本结构作为“建筑单元”,遵守三种基本结构的规范,基本结构之间可以并列、可以相互包含,但不允许交叉,不允许从一个结构直接转到另一个结构的内部去。正因为整个算法都是由三种基本结构组成的,就像用模块构建的一样,所以结构清晰,易于正确性验证,易于纠错,这种方法,就是结构化方法。遵循这种方法的程序设计,就是结构化程序设计。

相应地,只要规定好三种基本结构的流程图的画法,就可以画出任何算法的流程图。

(1) 顺序结构

顺序结构是简单的线性结构,各框按顺序执行。其流程图的基本形态如图1 - 4所示,语句的执行顺序为:A→B→C。

(2) 选择(分支)结构

这种结构是对某个给定条件进行判断,条件为真或假时分别执行不同的框的内容。其基本形状有两种,如图1-5 a)、b)所示。图1-5 a)的执行序列为:当条件为真时执行A,否则执行B;图1 - 5 b)的执行序列为:当条件为真时执行A,否则什么也不做。

1 、(3) 循环结构循环结构有两种基本形态:w h i l e型循环和d o - w h i l e型循环。
2、a. while 型循环如图1 - 6所示。其执行序列为:当条件为真时,反复执行A,一旦条件为假,跳出循环,执行循环紧后的 语句。



 

b. do-while型循环如图1 - 7所示。

执行序列为:首先执行A,再判断条件,条件为真时,一直循环执行A,一旦条件为假,结束循环,执行循环紧后的下一条语句。

在图1 - 6、图1 - 7中,A被称为循环体,条件被称为循环控制条件。要注意的是:

1) 在循环体中,必然对条件要判断的值进行修改,使得经过有限次循环后,循环一定能结束,如图1 - 3中的i = i - 1。2) 当型循环中循环体可能一次都不执行,而直到型循环则至少执行一次循环体。3) 直到型循环可以很方便地转化为当型循环,而当型循环不一定能转化为直到型循环。

例如,图1 - 7可以转化为图1 - 8。

2 用N-S图描述算法

N - S图是另一种算法表示法,是由美国人I . N a s s i和B . S h n e i d e r m a n共同提出的,其根据是:既然任何算法都是由前面介绍的三种结构组成,所以各基本结构之间的流程线就是多余的,因此,N - S图也是算法的一种结构化描述方法。

N - S图中,一个算法就是一个大矩形框,框内又包含若干基本的框,三种基本结构的N - S 图描述如下所示:

1. 顺序结构如图1 - 9所示,执行顺序先A后B。
2. 选择结构
对应于图1 - 5的N - S图为图1 - 1 0。图1-10 a)条件为真时执行A,条件为假时执行B。图1 - 1 0 b )条件为真时执行A,为假时什么都不做。


3. 循环结构
1) while型循环的N - S图如图1 - 11所示,条件为真时一直循环执行循环体A,直到条件为假时才跳出循环。
2) do-while型循环的N - S图如图1 - 1 2,一直循环执行循环体A,直到条件为假时才跳出循环。
本章例1 - 1的N - S图如图1 - 1 3,例1 - 2的N - S图如图1 - 1 4。应该说,N - S图比流程图更直观易懂,而且相对简练一些。



3 用PAD图描述算法
PA D(Problem Analysis Diagram),是近年来在软件开发中被广泛使用的一种算法的图形表示法,与前述的流程图、N - S图相比,流程图、N - S图都是自上而下的顺序描述,而PA D图除了自上而下以外,还有自左向右的展开,所以,如果说流程图、N - S图是一维的算法描述的话,则PA D图就是二维的,它能展现算法的层次结构,更直观易懂。
下面是PA D图的几种基本形态:
1. 顺序结构:
如图1 - 1 5所示。
2. 选择结构
(1) 单分支选择,条件为真执行A,如图1-16 a)。
(2) 两分支选择,如图1-16 b),条件为真执行A,为假执行B。
(3) 多分支选择,如图1-16 c),当I = I1时执行A,I= I2时执行B,I = I3时执行C,I = I4时执行D。

3. 循环结构
如图1 - 1 7所示。图1-17 a)为w h i l e型循环,图1-17 b)为d o - w h i l e型循环。

本章例1 . 1的PA D图如图1 - 1 8,例1 - 2的PA D图如图1 - 1 9。

分享到: 更多
蓝客门户
©2001-2017 中国蓝客联盟 版权所有.
关于蓝客联盟历史宗旨章程技术服务联系我们蓝客社区