全国青少年信息学奥林匹克联赛算法讲义算法入门教程.doc
《全国青少年信息学奥林匹克联赛算法讲义算法入门教程.doc》由会员分享,可在线阅读,更多相关《全国青少年信息学奥林匹克联赛算法讲义算法入门教程.doc(35页珍藏版)》请在启牛文库网上搜索。
1、全国青少年信息学奥林匹克联赛全国青少年信息学奥林匹克联赛 算法讲义算法讲义 算法算法基础篇基础篇 . 2 算法具有五个特征: . 2 信息学奥赛中的基本算法(枚举法) . 4 采用枚举算法解题的基本思路: . 4 枚举算法应用 . 4 信息学奥赛中的基本算法(回溯法) . 7 回溯基本思想 . 8 信息学奥赛中的基本算法(递归算法) . 10 递归算法的定义: . 10 递归算法应用 . 11 算法在信息学奥赛中的应用 (递推法) . 14 递推法应用 . 14 算法在信息学奥赛中的应用 (分治法) . 18 分治法应用 . 18 信息学奥赛中的基本算法(贪心法) . 21 贪心法应用 . 2
2、1 算法在信息学奥赛中的应用(搜索法一) . 24 搜索算法应用 . 25 算法在信息学奥赛中的应用(搜索法二) . 28 广度优先算法应用 . 29 算法在信息学奥赛中的应用(动态规划法) . 32 动态规划算法应用 . 33 算法算法基础基础篇篇 学习过程序设计的人对算法这个词并不陌生,从广义上讲,算法是指为解决一个问题而采用的方法和步骤;从程序计设的角度上讲,算法是指利用程序设计语言的各种语句,为解决特定的问题而构成的各种逻辑组合。我们在编写程序的过程就是在实施某种算法,因此程序设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂,一个好的程序必须有一个好的算法,一个没有有
3、效算法的程序就像一个没有灵魂的躯体。 算法具有五个特征: 1、有穷性: 一个算法应包括有限的运算步骤,执行了有穷的操作后将终止运算,不能是个死循环; 2、确切性: 算法的每一步骤必须有确切的定义,读者理解时不会产生二义性。并且,在任何条件下,算法只有唯一的一条执行路径,对于相同的输入只能得出相同的输出。如在算法中不允许有“计算 8/0”或“将 7 或 8 与 x 相加”之类的运算,因为前者的计算结果是什么不清楚,而后者对于两种可能的运算应做哪一种也不知道。 3、输入:一个算法有 0 个或多个输入,以描述运算对象的初始情况,所谓 0个输入是指算法本身定义了初始条件。如在 5 个数中找出最小的数,
4、则有 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 fo
5、r j:=1 to n do x:=x+1 含基本操作“x 增 1”的语句 x:=x+1 的出现的次数分别为 1,n 和 n2则这三个程序段的时间复杂度分别为 O(1) ,O(n) ,O(n2) ,分别称为常量阶、线性阶和平方阶。在算法时间复杂度的表示中,还有可能出现的有:对数阶 O(log n),指数阶 O(2n)等。在 n 很大时,不同数量级的时间复杂度有:O(1) O(log n)O(n) O(nlog n)O(n2) O(n3) O(2n),很显然,指数阶的算法不是一个好的算法。 二是看算法运行时所占用的空间,既空间复杂度。由于当今计算机硬件技术发展很快,程序所能支配的自由空间一般比较
6、充分,所以空间复杂度就不如时间复杂度那么重要了,有许多问题人们主要是研究其算法的时间复杂度,而很少讨论它的空间耗费。 时间复杂性和空间复杂性在一定条件下是可以相互转化的。在中学生信息学奥赛中,对程序的运行时间作出了严格的限制,如果运行时间超出了限定就会判错,因此在设计算法时首先要考虑的是时间因素,必要时可以以牺牲空间来换取时间,动态规划法就是一种以牺牲空间换取时间的有效算法。对于空间因素,视题目的要求而定,一般可以不作太多的考虑。 我们通过一个简单的数值计算问题,来比较两个不同算法的效率(在这里只比较时间复杂度) 。 例:求 N!所产生的数后面有多少个 0(中间的 0 不计) 。 算法一:从
7、1 乘到 n,每乘一个数判断一次,若后面有 0 则去掉后面的 0,并记下0 的个数。为了不超出数的表示范围,去掉与生成 0 无关的数,只保留有效位数,当乘完 n 次后就得到 0 的个数。(pascal 程序如下) var i,t,n,sum:longint; begin t:=0; sum:=1; readln(n); for i:=1 to n do begin sum:=sum*i; while sum mod 10=0 do begin sum:=sum div 10; inc(t);计数器增加 1 end; sum:=sum mod 1000;舍去与生成 0 无关的数 end; wri
8、teln(t:6); end. 算法二:此题中生成 O 的个数只与含 5 的个数有关,n!的分解数中含 5 的个数就等于末尾 O 的个数,因此问题转化为直接求 n!的分解数中含 5 的个数。 var t,n:integer; begin readln(n); t:=0; repeat n:=n div 5 ; inc(t,n); 计数器增加 n until n5; writeln(t:6); end. 分析对比两种算法就不难看出,它们的时间复杂度分别为 O(N) 、O(logN),算法二的执行时间远远小于算法一的执行时间。 在信息学奥赛中,其主要任务就是设计一个有效的算法,去求解所给出的问题。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国青少年 信息学 奥林匹克 联赛 算法 讲义 入门教程