算法及其设计基础.ppt

《算法及其设计基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、机。1.2算法的概念广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。•你想查看计算机CPU，首先必须将计算机断电，拆除连线，打开机箱，然后按下夹子解除夹口，最后取出CPU进行查看。•复制文件，首先要寻找所要复制的文件，然后选中，再进行复制，最后移动到需要的地方进行粘贴。计算机算法的分类：本书所讲述的算法只限于计算机算法，即计算机能执行的算法。在设计一个计算机算法时，应当考虑到计算机能否执行。计算机算法可分为两大类别：数值运算算法和非数值运算算法。数值运算的目的是求数值解，例如求方程的根

3、，求一个函数的定积分等，都属于数值运算范围。非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理等。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。1.3算法的特性一个算法应该具有以下几个特性：有穷性确定性输入输出有效性1.3算法的特性1）有穷性一个算法应包含有限的操作步骤，而不能是无限的。但是要注意，“有穷性”往往指“在合理的范围之内”。如果让计算机执行一个历时几百年才结束的算法，这虽然是有穷的，但超过了合理的限度，人们也不把它视做有效算法。究竟什么算

4、“合理限度”，并无严格标准，由人们的常识和需要而定。确定性算法中的每一个步骤，必须是确切定义的，而不应当含糊不清或模棱两可的。即算法的含义应当是唯一的，而不应当产生“歧义性”。例如，某人只说请您“复制文件”或查看计算机的CPU，是不确定的，因为此人没有说明复制哪一个文件或查看哪一台计算机的CPU。1.3算法的特性输入所谓输入是指在执行算法时需要从外界取得必要的信息。例如，让计算机来完成“将N个正数按从小到大的次序排列”时，就需要输入N个正整数。一个算法可以有多个输入，也可以没有输入。1.3算法的特

5、性输出算法执行过程中往往会产生一些数据，它们在算法执行之后被保存下来或传递给算法的调用者，这些数据被称为算法的输出。一个算法可以有多个输出，没有输出的算法是没有意义的。例如，计算机来完成“将N个整数按从小到大的次序排列”的算法时，输出的整数将是一组“从小到大的次序排列的N个整数”。1.3算法的特性有效性一个算法应该是具有现实意义的，如果算法中含有不能实现的某一个步骤，则这个所谓的“算法”无法解决问题，因此，不能称为算法。算法贯穿于程序设计的始终，希望读者对算法给予很大的重视，在解决一个问题之前应当

6、首先构造出一个好的算法。在本书各章中都贯穿这一原则。1.3算法的特性1.4算法的结构1966年，计算机科学家Bohm和Jacopini的研究表明，任何简单或复杂的算法都可以由下述3种基本控制结构组成。1）顺序结构2)选择结构3)循环结构1）顺序结构这是最简单的一种基本结构。顺序结构中的各个部分是按书写顺序依次执行的。例如某个算法中可能出现下列形式的一组操作：……操作1操作2操作3……如果这样一组操作的执行顺序与操作出现的前后顺序相同，即先进行“操作1”，然后进行“操作2”，再后进行“操作3”，那么

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

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