高中信息技术全国青少年奥林匹克联赛教案算法基础.pdfVIP

全国青少年信息学奥林匹克联赛 算法基础篇 学习过程序设计的人对算法这个词并不陌生，从广义上讲，算法是指为 解决一个问题而 采用的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计语言的各种语句，为解 决特定的问题而构成的各种逻辑组合。我们在编写程序的过程就是在实施某种算法，因此程序 设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂，一个好的程序必 须有一个好的算法，一个没有有效算法的程序就像一个没有灵魂的躯体。 算法具有五个特征： 1、有穷性： 一个算法应包括有限的运算步骤，执行了有穷的操作后将终止运算，不能是 个死循环； 2、确切性： 算法的每一步骤必须有确切的定义，读者理解时不会产生二义性。并且，在 任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。如在算法 中不允许有“计算 8/0”或“将 7 或8 与x 相加”之类的运算，因为前者的计算结果是什么不 清楚，而后者对于两种可能的运算应做哪一种也不知道。 3、输入：一个算法有 0个或多个输入，以描述运算对象的初始情况，所谓 0 个输入是指 算法本身定义了初始条件。如在 5个数中找出最小的数，则有 5 个输入。 4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法设计 的目的。它们是同输入有着某种特定关系的量。如上述在 5 个数中找出最小的数，它的出输 出为最小的数。如果一个程序没有输出，这个程序就毫无意义了； 5、可行性： 算法中每一步运算应该是可行的。算法原则上能够精确地运行，而且人能用 笔和纸做有限次运算后即可完成。 如何来评价一个算法的好坏呢？主要是从两个方面： 一是看算法运行所占用的时间；我们用时间复杂度来衡量，例如：在以下 3 个程序中， （1）x:=x+1 （2）for i:=1 to n do x:=x+1 （3）for i:=1 to n do for j:=1 to n do x:=x+1 2 含基本操作“x增1”的语句x:=x+1的出现的次数分别为 1，n和n 则这三个程序段的时间 复杂度分别为O（1），O（n），O（n2 ），分别称为常量阶、线性阶和平方阶。在算法时间复杂度 的表示中，还有可能出现的有：对数阶O(log n)，指数阶O(2n)等。在n很大时，不同数量级的 2 3 n 时间复杂度有：O(1) O(log n)O(n) O(nlog n)O(n ) O(n ) O(2 )，很显然，指数阶的 算法不是一个好的算法。 二是看算法运行时所占用的空间，既空间复杂度。由于当今计算机硬件技术发展很快，程 序所能支配的自由空间一般比较充分，所以空间复杂度就不如时间复杂度那么重要了，有许 多问题人们主要是研究其算法的时间复杂度，而很少讨论它的空间耗费。 时间复杂性和空间复杂性在一定条件下是可以相互转化的。在中学生信息学奥赛中，对 程序的运行时间作出了严格的限制，如果运行时间超出了限定就会判错，因此在设计算法时首 1 先要考虑的是时间因素，必要时可以以牺牲空间来换取时间，动态规划法就是一种以牺牲空 间换取时间的有效算法。对于空间因素，视题目的要求而定，一般可以不作太多的考虑。 我们通过一个简单的数值计算问题，来比较两个不同算法的效率（在这里只比较时间复杂 度）。 例：求 N！所产生的数后面有多少个0（中间的 0不计）。 算法一：从 1 乘到n，每乘一个数判断一次，若后面有 0 则去掉后面的 0，并记下 0的个数。 为了不超出数的表示范围，去掉与生成 0 无关的数，只保留有效位数，当乘完 n次后就得到 0 的个数。（pascal 程序如下） var i,t,n,sum:longint; begin t:=0; sum:=1;