第1章算法及其设计基础.pptVIP

第1章 算法及其设计基础 1.1 引言 程序设计方法首先强调的是设计，其次才是实现（写出程序代码）。其核心是将程序设计过程分为两部分。 第一部分集中于问题及其解法或算法，与任何特定的计算机或计算机语言无关。 第二部分集中于选择某一种程序设计语言，把算法表达给特定的计算机。 1.2 算法的概念 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。 ? 你想查看计算机CPU，首先必须将计算机断电，拆除连线，打开机箱，然后按下夹子解除夹口，最后取出CPU进行查看。 ? 复制文件，首先要寻找所要复制的文件，然后选中，再进行复制，最后移动到需要的地方进行粘贴。 计算机算法的分类： 本书所讲述的算法只限于计算机算法，即计算机能执行的算法。在设计一个计算机算法时，应当考虑到计算机能否执行。 计算机算法可分为两大类别：数值运算算法和非数值运算算法。 数值运算的目的是求数值解，例如求方程的根，求一个函数的定积分等，都属于数值运算范围。 非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理等。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。 1.3 算法的特性 1）有穷性 一个算法应包含有限的操作步骤，而不能是无限的。 但是要注意，“有穷性”往往指“在合理的范围之内”。如果让计算机执行一个历时几百年才结束的算法，这虽然是有穷的，但超过了合理的限度，人们也不把它视做有效算法。究竟什么算“合理限度”，并无严格标准，由人们的常识和需要而定。 1.3 算法的特性 确定性 算法中的每一个步骤，必须是确切定义的，而不应当含糊不清或模棱两可的。即算法的含义应当是唯一的，而不应当产生“歧义性”。 例如，某人只说请您“复制文件”或查看计算机的CPU，是不确定的，因为此人没有说明复制哪一个文件或查看哪一台计算机的CPU。 1.3 算法的特性 输入 所谓输入是指在执行算法时需要从外界取得必要的信息。 例如，让计算机来完成“将N个正数按从小到大的次序排列”时，就需要输入N个正整数。一个算法可以有多个输入，也可以没有输入。 1.3 算法的特性 输出 算法执行过程中往往会产生一些数据，它们在算法执行之后被保存下来或传递给算法的调用者，这些数据被称为算法的输出。 一个算法可以有多个输出，没有输出的算法是没有意义的。 例如，计算机来完成“将N个整数按从小到大的次序排列”的算法时，输出的整数将是一组“从小到大的次序排列的N个整数”。 1.3 算法的特性 有效性 一个算法应该是具有现实意义的，如果算法中含有不能实现的某一个步骤，则这个所谓的“算法”无法解决问题，因此，不能称为算法。 算法贯穿于程序设计的始终，希望读者对算法给予很大的重视，在解决一个问题之前应当首先构造出一个好的算法。在本书各章中都贯穿这一原则。 1.4 算法的结构 1966年，计算机科学家Bohm和Jacopini的研究表明，任何简单或复杂的算法都可以由下述3种基本控制结构组成。 1）顺序结构 2) 选择结构 3) 循环结构 1）顺序结构 这是最简单的一种基本结构。顺序结构中的各个部分是按书写顺序依次执行的。例如某个算法中可能出现下列形式的一组操作： …… 操作 1 操作 2 操作 3 …… 如果这样一组操作的执行顺序与操作出现的前后顺序相同，即先进行“操作1”，然后进行“操作2”，再后进行“操作3”，那么这段算法的结构就是顺序结构。 2) 选择结构 这种结构也称为分支结构，它表示操作的处理步骤出现了分支，它需要根据某一特定的条件选择其中的一个分支执行。例如下述算法描述片段： 如果 条件 成立 则执行 操作1 否则执行 操作2 操作1 和 操作2 之间构成了一种选择关系，两个操作中哪一个将被执行是通过对 条件 的判断来控制的。 3) 循环结构 循环结构是指被重复执行的一个操作集合。例如下述算法描述片段： 重复执行 操作 直到 条件 不成立 这段描述指出 操