《信息学奥赛——算法入门教程》由会员分享，可在线阅读，更多相关《信息学奥赛——算法入门教程（35页珍藏版）》请在金锄头文库上搜索。
1、全国青少年信息学奥林匹克联赛算法讲义算法基础篇 .1算法具有五个特征： .2信息学奥赛中的基本算法(枚举法) .4采用枚举算法解题的基本思路： .4枚举算法应用 .4信息学奥赛中的基本算法(回溯法) .7回溯基本思想 .7信息学奥赛中的基本算法(递归算法) .10递归算法的定义： .10递归算法应用 .10算法在信息学奥赛中的应用 (递推法) .13递推法应用 .14算法在信息学奥赛中的应用 (分治法) .17分治法应用 .18信息学奥赛中的基本算法(贪心法) .20贪心法应用 .21算法在信息学奥赛中的应用（搜索法一） .24搜索算法应用 .24算法在信息学奥赛中的应用（搜索法二） .28广
2、度优先算法应用 .29算法在信息学奥赛中的应用（动态规划法） .32动态规划算法应用 .33算法基础篇学习过程序设计的人对算法这个词并不陌生，从广义上讲，算法是指为解决一个问题而采用的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计语言的各种语句，为解决特定的问题而构成的各种逻辑组合。我们在编写程序的过程就是在实施某种算法，因此程序设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂，一个好的程序必须有一个好的算法，一个没有有效算法的程序就像一个没有灵魂的躯体。算法具有五个特征：1、有穷性： 一个算法应包括有限的运算步骤，执行了有穷的操作后将终止运算，不能是个死循环； 2、
3、确切性： 算法的每一步骤必须有确切的定义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。如在算法中不允许有“计算 8/0”或“将 7 或 8 与 x 相加”之类的运算，因为前者的计算结果是什么不清楚，而后者对于两种可能的运算应做哪一种也不知道。 3、输入：一个算法有 0 个或多个输入，以描述运算对象的初始情况，所谓0 个输入是指算法本身定义了初始条件。如在 5 个数中找出最小的数，则有 5 个输入。4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法设计的目的。它们是同输入有着某种特定关系的量。如上述在 5 个
4、数中找出最小的数，它的出输出为最小的数。如果一个程序没有输出，这个程序就毫无意义了； 5、可行性： 算法中每一步运算应该是可行的。算法原则上能够精确地运行，而且人能用笔和纸做有限次运算后即可完成。 如何来评价一个算法的好坏呢？主要是从两个方面：一是看算法运行所占用的时间；我们用时间复杂度来衡量，例如：在以下 3个程序中，（1）x:=x+1（2）for i:=1 to n dox:=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则这三个程序段的时间复杂度分别为 O（1）
5、 ，O（n） ，O（n 2） ，分别称为常量阶、线性阶和平方阶。在算法时间复杂度的表示中，还有可能出现的有：对数阶 O(log n)，指数阶 O(2n)等。在 n 很大时，不同数量级的时间复杂度有：O(1)0 then inc(t) else break;如果不在 st 中，则退出循环if t=9 then writeln(x, ,x*2, ,x*3);end;end.在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不全面，就穷举不出正确的结果， 我们再看看下面的例子。例 一元三次方程求解(noip2001tg)问题描述 有形如：ax 3+bx2+cx+d=0 这样的一个一元三
6、次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根 (根的范围在-100 至 100 之间) ，且根与根之差的绝对值=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 2 位。提示：记方程 f(x)=0，若存在 2 个数 x1 和 x2，且 x1a2ar;（2） 其中第 i 位数(1r-i;我们按以上原则先确定第一个数，再逐位生成所有的 r 个数，如果当前数符合要求，则添加下一个数;否则返回到上一个数，改变上一个数的值再判断是否符合要求，如果符合要求，则继续添加下一个数，否则返回到上一个数，改变上一个数的值按此规则不断循环
7、搜索，直到找出 r 个数的组合，这种求解方法就是回溯法。如果按以上方法生成了第 i 位数 ai，下一步的的处理为：（1） 若 air-i 且 i=r，则输出这 r 个数并改变 ai 的值:a i=ai-1;（2） 若 air-i 且 ir，则继续生成下一位 ai+1=ai-1;（3） 若 air-1 则重复：若 air-i，若 i=r，则输出解，并且 ai:=ai-1;若 ir，则继续生成下一位：ai+1:=ai-1; i:=i+1;若 air-i then 符合条件 if i=r then 输出beginfor j:=1 to r do write(aj:3);writeln;ai:=ai-
8、1; endelse 继续搜索begin ai+1:=ai-1; i:=i+1;end else回溯 begin i:=i-1; ai:=ai-1;end; until a1=r-1;end.下面我们再通过另一个例子看看回溯在信息学奥赛中的应用。例 2 数的划分（noip2001tg ）问题描述 整数 n 分成 k 份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7 ， k=3，下面三种分法被认为是相同的。1，1，5; 1，5，1; 5，1，1;问有多少种不同的分法。输入：n，k (6=ai,则添加下一个元素 ai+1；（3） 如果 i=ai则继续搜索；若 sum=ai then 判断是否回溯begin inc(i);ai:=ai-1;sum:=sum-ai;end继续搜else begin dec(i); inc(ai); sum:=sum+ai+1-1; end;回溯end;until a1nk;writeln(t);end.回溯法是通过尝试和纠正错误来寻找答案，是一种通用解题法，在 NOIP 中有许多涉及搜索问题的题目都可以用回溯法来求解。信息学奥赛中的基本算法(递归算法)递归算法的定义：如果一个对象的描述中包含它本身，我们就称这个对象是递归的，这种用递归来描述的算法称为递归算法。我们先来看看大家熟知的一
