算法及其设计基础

《算法及其设计基础》由会员分享，可在线阅读，更多相关《算法及其设计基础（78页珍藏版）》请在金锄头文库上搜索。

1、第1章 算法及其设计基础,教学目的和要求 了解算法描述的基本要求和目的，掌握用自然语言方式、流程图方式、盒图(N-S图)、 伪代码方式、PAD图方式和计算机语言方式来描述一个算法。 重点： 流程图方式、盒图(N-S图)、PAD图方式。 难点： 完整地用盒图(N-S图)来描述一个算法。,1.1 引言,程序设计方法首先强调的是设计，其次才是实现（写出程序代码）。其核心是将程序设计过程分为两部分。 第一部分集中于问题及其解法或算法，与任何特定的计算机或计算机语言无关。 第二部分集中于选择某一种程序设计语言，把算法表达给特定的计算机。,1.2 算法的概念,广义地说，为解决一个问题而采取的方法和步骤，就

2、称为“算法”。 你想查看计算机CPU，首先必须将计算机断电，拆除连线，打开机箱，然后按下夹子解除夹口，最后取出CPU进行查看。 复制文件，首先要寻找所要复制的文件，然后选中，再进行复制，最后移动到需要的地方进行粘贴。,计算机算法的分类： 本书所讲述的算法只限于计算机算法，即计算机能执行的算法。在设计一个计算机算法时，应当考虑到计算机能否执行。 计算机算法可分为两大类别：数值运算算法和非数值运算算法。 数值运算的目的是求数值解，例如求方程的根，求一个函数的定积分等，都属于数值运算范围。 非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理等。目前，计算机在非数值运算方面

3、的应用远远超过了在数值运算方面的应用。,1.3 算法的特性,一个算法应该具有以下几个特性： 有穷性 确定性 输入 输出 有效性,1.3 算法的特性,1）有穷性 一个算法应包含有限的操作步骤，而不能是无限的。 但是要注意，“有穷性”往往指“在合理的范围之内”。如果让计算机执行一个历时几百年才结束的算法，这虽然是有穷的，但超过了合理的限度，人们也不把它视做有效算法。究竟什么算“合理限度”，并无严格标准，由人们的常识和需要而定。,确定性 算法中的每一个步骤，必须是确切定义的，而不应当含糊不清或模棱两可的。即算法的含义应当是唯一的，而不应当产生“歧义性”。 例如，某人只说请您“复制文件”或查看计算机的

4、CPU，是不确定的，因为此人没有说明复制哪一个文件或查看哪一台计算机的CPU。,1.3 算法的特性,输入 所谓输入是指在执行算法时需要从外界取得必要的信息。 例如，让计算机来完成“将N个正数按从小到大的次序排列”时，就需要输入N个正整数。一个算法可以有多个输入，也可以没有输入。,1.3 算法的特性,输出 算法执行过程中往往会产生一些数据，它们在算法执行之后被保存下来或传递给算法的调用者，这些数据被称为算法的输出。 一个算法可以有多个输出，没有输出的算法是没有意义的。 例如，计算机来完成“将N个整数按从小到大的次序排列”的算法时，输出的整数将是一组“从小到大的次序排列的N个整数”。,1.3 算法

5、的特性,有效性 一个算法应该是具有现实意义的，如果算法中含有不能实现的某一个步骤，则这个所谓的“算法”无法解决问题，因此，不能称为算法。 算法贯穿于程序设计的始终，希望读者对算法给予很大的重视，在解决一个问题之前应当首先构造出一个好的算法。在本书各章中都贯穿这一原则。,1.3 算法的特性,1.4 算法的结构,1966年，计算机科学家Bohm和Jacopini的研究表明，任何简单或复杂的算法都可以由下述3种基本控制结构组成。 1）顺序结构 2) 选择结构 3) 循环结构,1）顺序结构,这是最简单的一种基本结构。顺序结构中的各个部分是按书写顺序依次执行的。例如某个算法中可能出现下列形式的一组操作：

6、 操作 1 操作 2 操作 3 如果这样一组操作的执行顺序与操作出现的前后顺序相同，即先进行“操作1”，然后进行“操作2”，再后进行“操作3”，那么这段算法的结构就是顺序结构。,2) 选择结构,这种结构也称为分支结构，它表示操作的处理步骤出现了分支，它需要根据某一特定的条件选择其中的一个分支执行。例如下述算法描述片段： 如果 成立 则执行 否则执行 和 之间构成了一种选择关系，两个操作中哪一个将被执行是通过对 的判断来控制的。,3) 循环结构,循环结构是指被重复执行的一个操作集合。例如下述算法描述片段： 重复执行 直到 不成立 这段描述指出 将被反复运行多次，直到 不成立为止。,注意： 通过上

7、述三种基本控制结构可以看到，它们有一个共同的特点，即：只有一个入口且只有一个出口，并且操作不会出现死循环。,1.5 算法的描述,算法的描述具有重要意义，描述一个算法的目的在于使其他人能够利用算法解决具体问题。 算法的描述方式没有统一规定，本书将介绍常用的自然语言、流程图、N-S图、PAD图、伪代码以及计算机语言等六种描述算法的方式。 注意： 不论是哪类方式，对它们的基本要求都是能提供对算法的无歧义的描述，以便使我们能够将这种描述很容易转换成计算机高级语言（程序）。,1.5.1 自然语言方式,自然语言就是人们日常使用的语言，可以是汉语、英语或其他任何形式的语言。,算法可以表示如下： 第1步 使s

8、ign=1（sign代表数值的符号） 第2步 使sum1（sum代表累加和变量） 第3步 使deno=2（deno代表分母变量） 第4步 sign(-1)*sign（求级数中各项的符号，它的值为l或-1） 第5步 termsign*(1/deno) （term代表级数中的某一项） 第6步 sum=sum+term 第7步 deno=deno+l 第8步 若deno20，转去执行第4步以及其后的各个步骤；否则 执行第9步 第9步 打印sum的值（即所求之总和） 第10步 算法结束,例1.1 求,例1.2 用选择排序法，将N个正整数数列按照从小到大 的顺序排列。 选择排序法基本思想：在选择排序方法

9、中，第一步在N个元素中选出最小元素，将其与第一个元素交换。第二步从剩下的N-1个元素中选出最小元素，将其与第二个元素交换，如此下去，直到剩下最后两个元素。,输入：将N个正整数放置在数组aN中。 第1步 使i=1 第2步 若iN-1，执行第3步；否则转第10步 第3步 使k=i，顺次执行第4步 第4步 使j=i+1，顺次执行第5步 第5步 若jN，执行第6步；否则转第8步 第6步 若ajak，则置k为j，然后顺次执行第7步；否则 直接执行第7步 第7步 使j=j+1，转第5步 第8步 若i!=k交换ai和ak的值(置t为 ai,ai为 ak， ak为 t )，顺次执行第9步；否则直接执行第9步

10、第9步 使i=i+1，转第2步 第10步 输出a1aN 第11步 算法结束,算法可以表示如下：,自然语言方式的优缺点： 用自然语言表示通俗易懂，但文字冗长，容易出现歧义性。 用自然语言描述的算法通用性差。例如，用汉语描述的算法只适合于懂得汉语的人，而用英语描述的算法也只能适合于懂得英语的人。 基于上述原因，除了很简单的问题以外，一般不用自然语言描述算法。,1.5.2 流程图方式,流程图是20世纪40年代末出现的一种描述算法或程序的工具，其特点是用一些图框表示各种类型的操作，用线表示这些操作的执行顺序。,图例中各结点的意义：,端点符：表示算法由此开始或结束。 处理框：表示一般的处理功能，应在框中

11、对该功能进行简单标记和说明。 判断框：表示判断操作，应该在框中标明判断条件。此框具有两个或两个以上出口，在每个出口处标明出口的条件。 预定义功能框：代表未详细说明的一个或一组操作，通常用来表示调用一个已知的算法或函数，框中标明这个算法或函数的名字或入口地址。 连接符：表示连结点，框中标有数字。当流程图较复杂或分布在多张纸上时，用连接符表示各图之间的联系，相同符号的连接符是相互连接的（如图1.2所示）。 注释框：注释框不反映流程和操作，只是为了对流程图中某些框的操作做必要的补充说明，以帮助阅读流程图的人更好地理解流程图的作用。,端点符,处理框,输入输出框,预定义功能框,判断框,流程线,连接符,图

12、 1.1 流程图常用图形符号,使用流程图表示的顺序型、选择型、当型循环和直到型循环等四种基本控制结构如图1.3所示。,条件,处理2,处理1,顺序结构,处理2,处理,N,当型循环,直到型循环,选择结构,处理,条件,条件,Y,Y,N,处理,图 1.3 四种基本控制结构,N,Y,使用流程图表示的顺序型、选择型、当型循环和直到型循环等四种基本控制结构：,例1.3 求,的流程图如图1.4所示,例1.4 将N个正整数数列按照从小到大的顺序排列的算法用流程图表示。,流程图描述算法的不足之处?,随意地使用箭头控制算法的执行流程，从而造成算法的层次结构混乱。 降低了程序的可读性和可维护性。 不适于自顶向下、逐步

13、求精的程序开发方式。,使用程序流程图描述算法，具有简捷、直观、使用方便的特点。,流程图特点:,1.5.3 盒图(N-S图)方式,出于要有一种不允许违背结构化程序设计思想的图形工具的考虑，1973年美国学者Nassi和Shneiderman提出了一种新的流程图形式,称为盒图（box diagram）,又称为N-S图。 在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框。 N-S图十分适合描述结构化程序或算法的结构化实现，能够较好地反映算法和程序的层次结构，可读性好，具有自顶向下逐步求精的特征。,N-S 图基本符号以及控制结构的描述方法,例1.

14、5 求,图 1.7 N-S图描述,的N-S图表示。,例1.6 将N个正整数数列按照从小到大的顺序排列的N-S图描述,1.5.4 PAD图方式,PAD图是问题分析图（problem analysis diagram）的英文缩写，1973年由日本日立公司的二才 良彦等提出，是另一种可以用于算法和程序描述的图形工具。 PAD图用二维树型结构的图来表示程序的控制流，即可以用于表示程序中操作的逻辑顺序，也可用于表示数据结构，是一种结构化程序设计描述工具，适用于自顶向下、逐步求精的程序开发方法。,PAD图的符号及控制结构如图1.9和表1.1所示。,表1.1 PAD图的图形符号,例1.7求,的PAD图描述算

15、法,例1.8 将N个正整数数列按照从小到大的顺序排列。,图1.11 PAD图描述,1.5.5 伪代码方式,伪代码(pseudo code)就是程序设计语言的控制结构和其他一些元素的速记符号。一般来说，伪代码的语法规则分为“外层语法”和“内层语法”。 外层语法类似于一般编程语言控制结构的关键字，比较严格。 内层语法则是灵活自由的，可以用自然语言，也可用程序设计语言，或使用自然语言与程序设计语言的混合体，以便使用于不同工程项目的需要。 伪代码不用图形符号，因此书写方便、格式紧凑，也比较好懂，便于转换成计算机高级语言(即程序)。,1) 层次,算法的书写应该具有层次，下面的一层采用缩进方式，同层次的缩

16、进相同，例如： X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X,本书伪代码构成元素和书写规则如下：,2) 注释,其形式是由()括起来的中文或英文字符串。 3) 3种控制结构 (1) 顺序结构 书写格式如下： ,(2) 分支结构,有以下两种书写格式： 格式1： if() then else 格式2： if() then 多重选择的格式如下： ，执行 ，执行 ，执行,（3）循环结构,有以下三种书写格式： 格式l：do while() 格式2：while() do 格式3：for to 步长 ,4) 调用算法,书写方式如下： 调用() 5) 需要标明算法的“BEGIN(开始)”和“END(结束)”点。,例1.9 求,BEGIN sign=