信息学奥赛——算法入门教程497.pdf

《信息学奥赛——算法入门教程497.pdf》由会员分享，可在线阅读，更多相关《信息学奥赛——算法入门教程497.pdf（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、全国青少年信息学奥林匹克联赛 算法讲义 算法基础篇.2 算法具有五个特征：.2 信息学奥赛中的基本算法(枚举法).4 采用枚举算法解题的基本思路：.4 枚举算法应用.4 信息学奥赛中的基本算法(回溯法).7 回溯基本思想.8 信息学奥赛中的基本算法(递归算法).10 递归算法的定义：.10 递归算法应用.11 算法在信息学奥赛中的应用(递推法).14 递推法应用.14 算法在信息学奥赛中的应用(分治法).18 分治法应用.18 信息学奥赛中的基本算法(贪心法).21 贪心法应用.21 算法在信息学奥赛中的应用（搜索法一）.24 搜索算法应用.25 算法在信息学奥赛中的应用（搜索法二）.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 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则这三个程序段的时间复杂度分别为 O（1），O（n），

5、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 不计）。算法一：从 1 乘到 n，每乘一个数判断一次，若后面有 0 则去掉后面的 0，并记下0 的个数。为了不超出数的表示范围，去掉与生成 0 无关的数，只保留有效位数，当乘完 n 次后就得到 0 的个数。（pascal 程序如下

7、）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;writeln(t:6);end.算法二：此题中生成 O 的个数只与含 5 的个数有关，n！的分解数中含 5 的个数就等于末尾 O 的个数，因此问题转化为直接求 n！的分解数中含 5 的个数。var t,n:integer;begin

8、 readln(n);t:=0;repeat n:=n div 5;inc(t,n);计数器增加 n until n5;writeln(t:6);end.分析对比两种算法就不难看出，它们的时间复杂度分别为 O（N）、O（logN）,算法二的执行时间远远小于算法一的执行时间。在信息学奥赛中，其主要任务就是设计一个有效的算法，去求解所给出的问题。如果仅仅学会一种程序设计语言，而没学过算法的选手在比赛中是不会取得好的成绩的，选手水平的高低在于能否设计出好的算法。下面，我们根据全国分区联赛大纲的要求，一起来探讨信息学奥赛中的基本算法。信息学奥赛中的基本算法(枚举法)枚举法，常常称之为穷举法，是指从可能

9、的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。采用枚举算法解题的基本思路：（1）确定枚举对象、枚举范围和判定条件；（2）一一枚举可能的解，验证是否是问题的解 下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这三个方面来探讨如何用枚举法解题。枚举算法应用 例 1：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。现在，请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象（分

10、别设为 x,y,z）,以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*3+y*2+z)为判定条件，穷举各种鸡的个数。下面是解这个百鸡问题的程序 var x,y,z:integer;begin for x:=0 to 100 do for y:=0 to 100 do for z:=0 to 100 do 枚举所有可能的解 if(x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln(x=,x,y=,y,z=,z);验证可能的解，并输出符合题目要求的解 end.上面的条件还有优化的空间，三种鸡的和是固定的，我们只要枚举二种鸡

11、（x,y），第三种鸡就可以根据约束条件求得（z=100-x-y），这样就缩小了枚举范围，请看下面的程序：var x,y,z:integer;begin for x:=0 to 100 do for y:=0 to 100-x do begin z:=100-x-y;if(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln(x=,x,y=,y,z=,z);end;end.未经优化的程序循环了 1013 次，时间复杂度为 O(n3)；优化后的程序只循环了（102*101/2）次，时间复杂度为 O(n2)。从上面的对比可以看出，对于枚举算法，加强约束条件，缩

12、小枚举的范围，是程序优化的主要考虑方向。在枚举算法中，枚举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的枚举对象可以获得更高的效率。如下例：例 2、将 1,2.9 共 9 个数分成三组,分别组成三个三位数,且使这三个三位数构成 1:2:3 的比例,试求出所有满足条件的三个三位数.例如:三个三位数 192,384,576 满足以上条件.(NOIP1998pj)算法分析：这是 1998 年全国分区联赛普及组试题（简称 NOIP1998pj，以下同）。此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举：for a:=1 to 9 do for

13、 b:=1 to 9 do for i:=1 to 9 do 这样下去，枚举次数就有 9次，如果我们分别设三个数为 x,2x,3x，以 x 为枚举对象，穷举的范围就减少为，在细节上再进一步优化，枚举范围就更少了。程序如下：var t,x:integer;s,st:string;c:char;begin for x:=123 to 321 do枚举所有可能的解 begin t:=0;str(x,st);把整数 x 转化为字符串，存放在 st 中 str(x*2,s);st:=st+s;str(x*3,s);st:=st+s;for c:=1 to 9 do枚举 9 个字符，判断是否都在 st 中

14、 if pos(c,st)0 then inc(t)else break;如果不在 st 中，则退出循环 if t=9 then writeln(x,x*2,x*3);end;end.在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不全面，就穷举不出正确的结果，我们再看看下面的例子。例 一元三次方程求解(noip2001tg)问题描述 有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100 至 100 之间)，且根与根之差的绝对值=1。要求由小到大依次在同一行输出这三个实

15、根(根与根之间留有空格)，并精确到小数点后 2 位。提示：记方程 f(x)=0，若存在 2 个数 x1 和 x2，且 x1x2，f(x1)*(x2)0，则在(x1，x2)之间一定有一个根。样例 输入：1 -5 -4 20 输出：-2.00 2.00 5.00 算法分析：由题目的提示很符合二分法求解的原理，所以此题可以用二分法。用二分法解题相对于枚举法来说很要复杂很多。此题是否能用枚举法求解呢？再分析一下题目，根的范围在-100 到 100 之间，结果只要保留两位小数，我们不妨将根的值域扩大 100 倍（-10000=x=10000），再以根为枚举对象，枚举范围是-10000到 10000，用原

16、方程式进行一一验证，找出方程的解。有的同学在比赛中是这样做 var k:integer;a,b,c,d,x:real;begin read(a,b,c,d);for k:=-10000 to 10000 do begin x:=k/100;if a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2,);end;end.用这种方法，很快就可以把程序编出来，再将样例数据代入测试也是对的，等成绩下来才发现这题没有全对，只得了一半的分。这种解法为什么是错的呢？错在哪里？前面的分析好象也没错啊，难道这题不能用枚举法做吗？看到这里大家可能有点迷惑了。在上面的解法中，枚举范围和枚举对

17、象都没有错，而是在验证枚举结果时，判定条件用错了。因为要保留二位小数，所以求出来的解不一定是方程的精确根，再代入 ax3+bx2+cx+d 中，所得的结果也就不一定等于 0，因此用原方程ax3+bx2+cx+d=0 作为判断条件是不准确的。我们换一个角度来思考问题，设 f(x)=ax3+bx2+cx+d，若 x 为方程的根，则根据提示可知，必有 f(x-0.005)*(x+0.005)0，如果我们以此为枚举判定条件，问题就逆刃而解。另外，如果 f(x-0.005)=0，哪么就说明 x-0.005 是方程的根，这时根据四舍 5 入，方程的根也为 x。所以我们用(f(x-0.005)*f(x+0.

18、005)0)和(f(x-0.005)=0)作为判定条件。为了程序设计的方便，我们设计一个函数 f(x)计算 ax3+bx2+cx+d 的值，程序如下：$N+var k:integer;a,b,c,d,x:extended;function f(x:extended):extended;计算 ax3+bx2+cx+d 的值 begin f:=(a*x+b)*x+c)*x+d;end;begin read(a,b,c,d);for k:=-10000 to 10000 do begin x:=k/100;if(f(x-0.005)*f(x+0.005)a2ar;（2）其中第 i 位数(1=ir-i

19、;我们按以上原则先确定第一个数，再逐位生成所有的 r 个数，如果当前数符合要求，则添加下一个数;否则返回到上一个数，改变上一个数的值再判断是否符合要求，如果符合要求，则继续添加下一个数，否则返回到上一个数，改变上一个数的值按此规则不断循环搜索，直到找出 r 个数的组合，这种求解方法就是回溯法。如果按以上方法生成了第i 位数 ai，下一步的的处理为：（1）若 air-i 且 i=r，则输出这 r 个数并改变 ai 的值:ai=ai-1;（2）若 air-i 且 ir，则继续生成下一位 ai+1=ai-1;（3）若 air-1 则重复：若 air-i，若 i=r，则输出解，并且 ai:=ai-1;

20、若 ir，则继续生成下一位：ai+1:=ai-1;i:=i+1;若 air-i then 符合条件 if i=r then 输出 begin for j:=1 to r do write(aj:3);writeln;ai:=ai-1;end else 继续搜索 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 份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：

21、n=7，k=3，下面三种分法被认为是相同的。1，1，5;1，5，1;5，1，1;问有多少种不同的分法。输入：n，k (6n=200，2=k=6)输出：一个整数，即不同的分法。样例 输入：7 3 输出：4 四种分法为：1,1,5;1,2,4;1,3,3;2,2,3;算法分析：此题可以用回溯法求解，设自然数 n 拆分为 a1,a2,ak,必须满足以下两个条件：（1）n=a1+a2+ak ；（2）a1=a2=ak (避免重复计算)；现 假 设 己 求 得 的 拆 分 数 为 a1,a2,ai,且 都 满 足 以 上 两 个 条 件,设sum=n-a1-a2-ai,我们根据不同的情形进行处理：（1）如

22、果 i=k,则得到一个解，则计数器 t 加 1，并回溯到上一步，改变 ai-1的值；（2）如果 i=ai,则添加下一个元素ai+1；（3）如果 ik 且 sumai,则说明达不到目标，回溯到上一步，改变ai-1的值；算法实现步骤如下：第一步：输入自然数n,k 并初始化；t:=0;i:=1;ai:=1;sum:=n-1;nk:=n div k;第二步：如果 a1=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;回溯

23、 end;until a1nk;writeln(t);end.回溯法是通过尝试和纠正错误来寻找答案，是一种通用解题法，在 NOIP 中有许多涉及搜索问题的题目都可以用回溯法来求解。信息学奥赛中的基本算法(递归算法)递归算法的定义：如果一个对象的描述中包含它本身，我们就称这个对象是递归的，这种用递归来描述的算法称为递归算法。我们先来看看大家熟知的一个的故事：从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说 上面的故事本身是递归的，用递归算法描述：procedure bonze-tell-story；begin if 讲话被打

24、断 then 故事结束 else begin 从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事；bonze-tell-story；end end;从上面的递归事例不难看出，递归算法存在的两个必要条件：（1）必须有递归的终止条件；（2）过程的描述中包含它本身；在设计递归算法中，如何将一个问题转化为递归的问题，是初学者面临的难题，下面我们通过分析汉诺塔问题，看看如何用递归算法来求解问题；递归算法应用 例 1：汉诺塔问题，如下图，有 A、B、C 三根柱子。A 柱子上按从小到大的顺序堆放了 N 个盘子，现在要把全部盘子从 A 柱移动到 C 柱，移动过程中可以借助 B柱。移动时有如下要求：（1）一

25、次只能移动一个盘子；（2）不允许把大盘放在小盘上边；（3）盘子只能放在三根柱子上；算法分析：当盘子比较多的时，问题比较复杂，所以我们先分析简单的情况：如果只有一个盘子，只需一步，直接把它从 A 柱移动到 C 柱；如果是二个盘子，共需要移动 3 步:（1）把 A 柱上的小盘子移动到 B 柱;（2）把 A 柱上的大盘子移动到 C 柱；（3）把 B 柱上的大盘子移动到 C 柱；如果 N 比较大时，需要很多步才能完成，我们先考虑是否能把复杂的移动过程转化为简单的移动过程，如果要把 A 柱上最大的盘子移动到 C 柱上去，必须先把上面的 N-1 个盘子从 A 柱移动到 B 柱上暂存，按这种思路，就可以把

26、N 个盘子的移动过程分作 3 大步：（1）把 A 柱上面的 N-1 个盘子移动到 B 柱；（2）把 A 柱上剩下的一个盘子移动到 C 柱；（3）把 B 柱上面的 N-1 个盘子移动到 C 柱；其中 N-1 个盘子的移动过程又可按同样的方法分为三大步，这样就把移动过程转化为一个递归的过程，直到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归结束。递归过程：procedure Hanoi(N,A,B,C:integer;)；以 B 柱为中转柱将 N 个盘子从 A 柱移动到 C 柱 begin if N=1 then write(A,-,C)把盘子直接从 A 移动到 C else begin H

27、anoi(N-1,A,C,B)；以 C 柱为中转柱将 N-1 个盘子从 A 柱移动到 B 柱 write(A,-,C)；把剩下的一个盘子从 A 移动到 C Hanoi(N-1,B,A,C)；以 A 柱为中转柱将 N-1 个盘子从 B 柱移动到 C 柱 end;end;从上面的例子我们可以看出，在使用递归算法时，首先弄清楚简单情况下的解法，然后弄清楚如何把复杂情况归纳为更简单的情况。在信息学奥赛中有的问题的结构或所处理的数据本身是递归定义的，这样的问题非常适合用递归算法来求解，对于这类问题，我们把它分解为具有相同性质的若干个子问题，如果子问题解决了，原问题也就解决了。例 2 求先序排列(NOIP

28、2001pj)问题描述给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度8)。样例 输入：BADC BDCA 输出：ABCD 算法分析：我们先看看三种遍历的定义：先序遍历是先访问根结点，再遍历左子树，最后遍历右子树；中序遍历是先遍历左子树，再访问根结点，最后遍历右子树；后序遍历是先遍历左子树，再遍历右子树，最后访问根结点；从遍历的定义可知，后序排列的最后一个字符即为这棵树的根节点；在中序排列中，根结点前面的为其左子树，根结点后面的为其右子树；我们可以由后序排列求得根结点，再由根结点在中序排列的位置确定左子树和右子树，把左子树和右子树各看作一个单独的树。这样

29、，就把一棵树分解为具有相同性质的二棵子树，一直递归下去，当分解的子树为空时，递归结束，在递归过程中，按先序遍历的规则输出求得的各个根结点，输出的结果即为原问题的解。源程序 program noip2001_3;var z,h:string;procedure make(z,h:string);z为中序排列,h 为后序排列 var s,m:integer;begin m:=length(h);m为树的长度 write(hm);输出根节点 s:=pos(hm,z);求根节点在中序排列中的位置 if s1 then make(copy(z,1,s-1),copy(h,1,s-1);处理左子树 if

30、ms then make(copy(z,s+1,m-s),copy(h,s,m-s);处理右子树 end;begin readln(z);readln(h);make(z,h);end.递归算法不仅仅是用于求解递归描述的问题，在其它很多问题中也可以用到递归思想，如回溯法、分治法、动态规划法等算法中都可以使用递归思想来实现，从而使编写的程序更加简洁。比如上期回溯法所讲的例 2数的划分问题，若用递归来求解，程序非常短小且效率很高，源程序如下 var n,k:integer;tol:longint;procedure make(sum,t,d:integer);var i:integer;begin

31、 if d=k then inc(tol)else for i:=t to sum div 2 do make(sum-i,i,d+1);end;begin readln(n,k);tol:=0;make(n,1,1);writeln(tol);end.有些问题本身是递归定义的，但它并不适合用递归算法来求解，如斐波那契(Fibonacci)数列，它的递归定义为：F(n)=1 (n=1,2)F(n)=F(n-2)+F(n-1)(n2)用递归过程描述为：Funtion fb(n:integer):integer;Begin if n3 then fb:=1 else fb:=fb(n-1)+fb(

32、n-2);End;上面的递归过程，调用一次产生二个新的调用，递归次数呈指数增长，时间复杂度为 O（2n）,把它改为非递归：x:=1;y:=1;for i:=3 to n do begin z:=y;y:=x+y;x:=z;end;修改后的程序，它的时间复杂度为O（n）。我们在编写程序时是否使用递归算法，关键是看问题是否适合用递归算法来求解。由于递归算法编写的程序逻辑性强，结构清晰，正确性易于证明，程序调试也十分方便，在 NOIP 中，数据的规模一般也不大，只要问题适合用递归算法求解，我们还是可以大胆地使用递归算法。算法在信息学奥赛中的应用(递推法)所谓递推，是指从已知的初始条件出发，依据某种递

33、推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。可用递推算法求解的题目一般有以下二个特点：（1）问题可以划分成多个状态；（2）除初始状态外，其它各个状态都可以用固定的递推关系式来表示。在我们实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。递推法应用 例 1 骑士游历:（noip1997tg）设有一个 n*m 的棋盘(2=n=50,2=m(2,3)-(4,4)若不存在路径,则输出no 任务 2:当 N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目。例如:(N=

34、10,M=10),(1,5)(起点),(3,5)(终点)输出:2(即由(1,5)到(3,5)共有 2 条路径)输入格式:n,m,x1,y1,x2,y2(分别表示 n,m,起点坐标,终点坐标)输出格式:路径数目(若不存在从起点到终点的路径,输出 0)算法分析：为了研究的方便，我们先将棋盘的横坐标规定为 i，纵坐标规定为 j，对于一个 nm 的棋盘，i 的值从 1 到 n，j 的值从 1 到 m。棋盘上的任意点都可以用坐标(i,j)表示。对于马的移动方法，我们用 K 来表示四种移动方向(1,2,3,4)；而每种移动方法用偏移值来表示，并将这些偏移值分别保存在数组 dx 和 dy 中，如下表 K D

35、xk Dyk 1 2 1 2 2-1 3 1 2 4 1-2 根据马走的规则，马可以由（i-dxk,j-dyk）走到(i,j)。只要马能从（1，1）走到（i-dxk,j-dyk），就一定能走到（i,j）,马走的坐标必须保证在棋盘上。我们以（n,m）为起点向左递推，当递推到（i-dxk,j-dyk）的位置是（1，1）时，就找到了一条从（1，1）到（n,m）的路径。我们用一个二维数组 a 表示棋盘，对于任务一，使用倒推法，从终点(n,m)往左递推，设初始值 an,m为（-1，-1），如果从(i,j)一步能走到(n,m)，就将(n,m)存放在 ai,j中。如下表，a3,2和 a2,3的值是（4，4）

36、，表示从这两个点都可以到达坐标（4,4）。从（1,1）可到达（2，3）、（3，2）两个点，所以 a1,1存放两个点中的任意一个即可。递推结束以后，如果 a1,1值为(0,0)说明不存在路径，否则a1,1值就是马走下一步的坐标，以此递推输出路径。-1,-1 4,4 4,4 2,3 任务一的源程序：const dx:array1.4of integer=(2,2,1,1);dy:array1.4of integer=(1,-1,2,-2);type map=record x,y:integer;end;var i,j,n,m,k:integer;a:array0.50,0.50of map;beg

37、in read(n,m);fillchar(a,sizeof(a),0);an,m.x:=-1;an,m.y:=-1;标记为终点 for i:=n downto 2 do 倒推 for j:=1 to m do if ai,j.x0 then for k:=1 to 4 do begin ai-dxk,j-dyk.x:=i;ai-dxk,j-dyk.y:=j;end;if a1,1.x=0 then writeln(no)else begin存在路径 i:=1;j:=1;write(,i,j,);while ai,j.x-1 do begin k:=i;i:=ai,j.x;j:=ak,j.y;

38、write(-(,i,j,);end;end;end.对于任务二，也可以使用递推法，用数组 Ai,j存放从起点(x1,y1)到（i,j）的路径总数，按同样的方法从左向右递推，一直递推到（x2,y2），ax2,y2即为所求的解。源程序（略）在上面的例题中，递推过程中的某个状态只与前面的一个状态有关，递推关系并不复杂，如果在递推中的某个状态与前面的所有状态都有关，就不容易找出递推关系式，这就需要我们对实际问题进行分析与归纳，从中找到突破口，总结出递推关系式。我们可以按以下四个步骤去分析：（1）细心的观察；（2）丰富的联想；（3）不断地尝试；（4）总结出递推关系式。下面我们再看一个复杂点的例子。例

39、2、栈（noip2003pj）题目大意：求 n 个数通过栈后的排列总数。（1n18）如输入 3 输出 5 算法分析：先模拟入栈、出栈操作，看看能否找出规律，我们用 f(n)表示 n个数通过栈操作后的排列总数，当n 很小时，很容易模拟出 f(1)=1；f(2)=2；f(3)=5,通过观察，看不出它们之间的递推关系，我们再分析 N=4 的情况，假设入栈前的排列为“4321”，按第一个数“4”在出栈后的位置进行分情况讨论：（1）若“4”最先输出，刚好与 N=3 相同，总数为 f(3);（2）若“4”第二个输出，则在“4”的前只能是“1”，“23”在“4”的后面，这时可以分别看作是 N=1 和 N=2

40、 时的二种情况，排列数分别为 f(1)和f(2),所以此时的总数为 f(1)*f(2);（3）若“4”第三个输出，则“4”的前面二个数为“12”,后面一个数为“3”，组成的排列总数为 f(2)*f(1);（4）若“4”第四个输出，与情况（1）相同，总数为 f(3);所以有：f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3);若设 0 个数通过栈后的排列总数为：f(0)=1；上式可变为：f(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0);再进一步推导，不难推出递推式：f(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(n-1)*f

41、(0);即 f(n)=10)1(*)(niinfif (n=1)初始值：f(0)=1;有了以上递推式，就很容易用递推法写出程序。var a:array0.18of longint;n,i,j:integer;begin readln(n);fillchar(a,sizeof(a),0);a0:=1;for i:=1 to n do for j:=0 to i-1 do ai:=ai+aj*ai-j-1;writeln(an);end.递推算法最主要的优点是算法结构简单，程序易于实现，难点是从问题的分析中找出解决问题的递推关系式。对于以上两个例子，如果在比赛中找不出递推关系式，也可以用回溯法求解

42、。算法在信息学奥赛中的应用(分治法)分治算法的基本思想是将一个规模为N 的问题分解为 K 个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。分治法应用 例1、比赛安排(noip1996)设有2n(n=6)个球队进行单循环比赛,计划在2n-1天内完成,每个队每天进行一场比赛。设计一个比赛的安排,使在 2n-1 天内每个队都与不同的对手比赛。例如 n=2 时的

43、比赛安排为:队 1 2 3 4 比赛 1-2 3-4 第一天 1-3 2-4 第二天 1-4 2-3 第三天 算法分析：此题很难直接给出结果，我们先将问题进行分解，设 m=2n，将规模减半，如果 n=3(即 m=8),8个球队的比赛，减半后变成 4个球队的比赛（m=4），4个球队的比赛的安排方式还不是很明显，再减半到两个球队的比赛(m=2)，两个球队的比赛安排方式很简单，只要让两个球队直接进行一场比赛即可：1 2 2 1 分析两个球队的比赛的情况不难发现，这是一个对称的方阵，我们把这个方阵分成 4 部分（即左上，右上，左下，右下），右上部分可由左上部分加 1（即加 m/2）得到，而右上与左下部

44、分、左上与右下部分别相等。因此我们也可以把这个方阵看作是由 M=1 的方阵所成生的，同理可得M=4 的方阵：1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 同理可由 M=4 方阵生成 M=8 的方阵：1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 这样就构成了整个比赛的安排表。在算法设计中，用数组 a 记录 2n个球队的循环比赛表，整个循环比赛表从最初的 1*1 方阵按上述

45、规则生成 2*2 的方阵，再生成 4*4 的方阵，直到生成出整个循环比赛表为止。变量 h 表示当前方阵的大小,也就是要生成的下一个方阵的一半。源程序：var i,j,h,m,n:integer;a:array1.32,1.32of integer;begin readln(n);m:=1;a1,1:=1;h:=1;for i:=1 to n do m:=m*2;repeat for i:=1 to h do for j:=1 to h do begin ai,j+h:=ai,j+h;构造右上角方阵 ai+h,j:=ai,j+h;构造左下角方阵 ai+h,j+h:=ai,j;构造右下角方阵 en

46、d;h:=h*2;until h=m;for i:=1 to m do begin for j:=1 to m do write(ai,j:4);writeln;end;end.在分治算法中，若将原问题分解成两个较小的子问题，我们称之为二分法，由于二分法划分简单，所以使用非常广泛。使用二分法与使用枚举法求解问题相比较，时间复杂度由 O（N）降到 O（log2N），在很多实际问题中，我们可以通过使用二分法，达到提高算法效率的目的，如下面的例子。例 2 一元三次方程求解（noip2001tg）题目大意：给出一个一元三次方程 f(x)=ax3+bx2+cx+d=0 ,求它的三个根。所有的根都在区间-

47、100，100中，并保证方程有三个实根，且它们之间的差不小于 1。算法分析：在讲解枚举法时，我们讨论了如何用枚举法求解此题，但如果求解的精度进一步提高，使用枚举法就无能为力了，在此我们再一次讨论如何用二分法求解此题。由题意知（i,i+1）中若有根，则只有一个根，我们枚举根的值域中的每一个整数 x(-100 x100),设定搜索区间x1，x2，其中 x1=x，x2=x+1。若：f(x1)=0，则确定 x1为 f(x)的根；f(x1)*f(x2)0，则确定根 x 不在区间x1，x2内，设定x2，x2+1为下一个搜索区间；若确定根 x 在区间x1，x2内，采用二分法，将区间x1，x2分成左右两个子区

48、间：左子区间x1，x和右子区间x，x2（其中 x=（x1+x2）/2）。如果 f(x1)*f(x)0，则确定根在左区间x1，x内，将 x 设为该区间的右界值（x2=x），继续对左区间进行对分；否则确定根在右区间x，x2内，将 x 设为该区间的左界值（x1=x），继续对右区间进行对分；上述对分过程一直进行到区间的间距满足精度要求为止（即 x2-x10.005）。此时确定 x1为 f(x)的根。源程序：$N+var x:integer;a,b,c,d,x1,x2,xx:extended;function f(x:extended):extended;begin f:=(a*x+b)*x+c)*x+

49、d;end;begin read(a,b,c,d);for x:=-100 to 100 do begin x1:=x;x2:=x+1;if f(x1)=0 then write(x1:0:2,)else if f(x1)*f(x2)=0.005 do begin xx:=(x1+x2)/2;if f(x1)*f(xx)从 取 3 张牌放到（9 11 10 10）-从 取 1 张牌放到（10 10 10 10）。输 入：键盘输入文件名。文件格式：N（N 堆纸牌，1=N=100）A1 A2 An（N 堆纸牌，每堆纸牌初始数，l=Ai=10000）输 出：输出至屏幕。格式为：所有堆均达到相等时的最

50、少移动次数。输入输出样例 a.in：4 9 8 17 6 屏慕显示：3 算法分析：设 ai为第 i 堆纸牌的张数（0=i=n），v 为均分后每堆纸牌的张数，s为最小移到次数。我们用贪心法，按照从左到右的顺序移动纸牌。如第 i 堆(0iv，则将 ai-v 张纸牌从第 I 堆移动到第 I+1 堆；（2）若 aiv，则将 v-ai张纸牌从第 I+1 堆移动到第 I 堆；为了设计的方便，我们把这两种情况统一看作是将 aI-v 张牌从第 I 堆移动到第 I+1 堆；移动后有：aI:=v；aI+1:=aI+1+aI-v；在从第 i+1 堆中取出纸牌补充第 i 堆的过程中，可能会出现第 i+1 堆的纸牌数小