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

实用标准文案

全国青少年信息学奥林匹克联赛

算法讲义

算法基础篇 ........................................................................................................................................ 2

算法具有五个特征： ............................................................................................................... 2 信息学奥赛中的基本算法(枚举法) ............................................................................................... 7

采用枚举算法解题的基本思路： .......................................................................................... 7 枚举算法应用 ........................................................................................................................... 7 信息学奥赛中的基本算法(回溯法) ............................................................................................. 14

回溯基本思想 ......................................................................................................................... 14 信息学奥赛中的基本算法(递归算法) ......................................................................................... 18

递归算法的定义： ................................................................................................................. 18 递归算法应用 ......................................................................................................................... 19 算法在信息学奥赛中的应用 (递推法) ....................................................................................... 25

递推法应用 ............................................................................................................................. 26 算法在信息学奥赛中的应用 (分治法) ....................................................................................... 32

分治法应用 ............................................................................................................................. 33

精彩文档

实用标准文案

信息学奥赛中的基本算法(贪心法) ............................................................................................. 38

贪心法应用 ............................................................................................................................. 39 算法在信息学奥赛中的应用（搜索法一） ............................................................................... 44

搜索算法应用 ......................................................................................................................... 45 算法在信息学奥赛中的应用（搜索法二） ............................................................................... 48

广度优先算法应用 ................................................................................................................. 50 算法在信息学奥赛中的应用（动态规划法） ........................................................................... 56

动态规划算法应用 ................................................................................................................. 58

算法基础篇

学习过程序设计的人对算法这个词并不陌生，从广义上讲，算法是指为解决一个问题而采用的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计语言的各种语句，为解决特定的问题而构成的各种逻辑组合。我们在编写程序的过程就是在实施某种算法，因此程序设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂，一个好的程序必须有一个好的算法，一个没有有效算法的程序就像一个没有灵魂的躯体。

算法具有五个特征：

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

精彩文档