信息的学奥赛——算法入门教程.doc

实用标准文案
: .
全国青少年信息学奥林匹克联赛
算法讲义
算法基础篇 2
算法具有五个特征： 2
信息学奥赛中的基本算法（枚举法） 4
采用枚举算法解题的基本思路： 4
枚举算法应用 4
信息学奥赛中的基本算法（回溯法） 7
回溯基本思想 8
信息学奥赛中的基本算法（递归算法） 10
递归算法的定义： 10
递归算法应用 10
算法在信息学奥赛中的应用 （递推法） 13
递推法应用 14
算法在信息学奥赛中的应用 （分治法） 17
分治法应用 17
信息学奥赛中的基本算法（贪心法） 20
贪心法应用 21
算法在信息学奥赛中的应用（搜索法一） 23
搜索算法应用 24
算法在信息学奥赛中的应用（搜索法二） 28
广度优先算法应用 29
算法在信息学奥赛中的应用（动态规划法） 32
动态规划算法应用 33
精彩文档
实用标准文案
算法基础篇
学****过程序设计的人对算法这个词并不陌生，从广义上讲，算法是指为解决 一个问题而采用的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计 语言的各种语句，为解决特定的问题而构成的各种逻辑组合。我们在编写程序的 过程就是在实施某种算法，因此程序设计的实质就是用计算机语言构造解决问题 的算法。算法是程序设计的灵魂，一个好的程序必须有一个好的算法，一个没有 有效算法的程序就像一个没有灵魂的躯体。
算法具有五个特征：
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
含基本操作“ x增1”的语句x:=x+1的出现的次数分别为1，n和n2则这三个 程序段的时间复杂度分别为 0( 1)，0(n), 0(n2)，分别称为常量阶、线性阶和 平方阶。在算法时间复杂度的表示中，还有可能出现的有：对数阶 O(log n)，指 数阶0(2)等。在n很大时，不同数量级的时间复杂度有： 0(1)< O(log n)<O(n)v
O(nlog n)<O(n 2) <O(n ) <O(2 n)，很显然，指数阶的算法不是一个好的算法。
二是看算法运行时所占用的空间，既空间复杂度。由于当今计算机硬件技术 发展很快，程序所能支配的自由空间一般比较充分，所以空间复杂度就不如时间 精彩文档
复杂度那么重要了，有许多问题人们主要是研究其算法的时间复杂度，而很少讨 论它的空间耗费。
时间复杂性和空间复杂性在一定条件下是可以相互转化的。在中学生信息学 奥赛中，对程序的运行时间作出了严格的限制，如果运行时间超出了限定就会判 错，因此在设计算法时首先要考虑的是时间因素，必要时可以以牺牲空间来换取 时间，动态规划法就是一种以牺牲空间换取时间的有效算法。对于空间因素，视 题目的要求而定，一般可以不作太多的考虑。
我们通过一个简单的数值计算问题，来比较两个不同算法的效率(在这里只 比较时间复杂度)。
例：求N!所产生的数后面有多少个0 (中间的0不计)。
算法一：从1乘到n,每乘一个数判断一次，若后面有 0则去掉后面的0,并记下 0的个数。为了不超出数的表示范围，去掉与生成 0无关的数，只保留有