nbhkdz.com冰点文库

2014 NOIP信息学奥赛——算法快速入门教程(中国计算机学会出版)

时间:2014-03-05


中国计算机学会 2014

2014 NOIP 全国青少年信息学奥林匹 克联赛(中国计算机学会出版)

算法
算法基础篇 .................................................................................................................................. 2 算法具有五个特征: .......................................................................................................... 2 信息学奥赛中的基本算法(枚举法) .......................................................................................... 4 采用枚举算法解题的基本思路: ...................................................................................... 4 枚举算法应用 ...................................................................................................................... 4 信息学奥赛中的基本算法(回溯法) .......................................................................................... 7 回溯基本思想 ...................................................................................................................... 8 信息学奥赛中的基本算法(递归算法) .................................................................................... 10 递归算法的定义: ............................................................................................................ 10 递归算法应用 .................................................................................................................... 11 算法在信息学奥赛中的应用 (递推法) .................................................................................. 14 递推法应用 ........................................................................................................................ 14 算法在信息学奥赛中的应用 (分治法) .................................................................................. 18 分治法应用 ........................................................................................................................ 18 信息学奥赛中的基本算法(贪心法) ........................................................................................ 21 贪心法应用 ........................................................................................................................ 21 算法在信息学奥赛中的应用(搜索法一) ............................................................................ 24 搜索算法应用 .................................................................................................................... 25 算法在信息学奥赛中的应用(搜索法二) ............................................................................ 28 广度优先算法应用 ............................................................................................................ 29 算法在信息学奥赛中的应用(动态规划法) ........................................................................ 32 动态规划算法应用 ............................................................................................................ 33

中国计算机学会 2014

算法基础篇
学习过程序设计的人对算法这个词并不陌生,从广义上讲,算法是指为解决 一个问题而采用的方法和步骤;从程序计设的角度上讲,算法是指利用程序设计 语言的各种语句,为解决特定的问题而构成的各种逻辑组合。我们在编写程序的 过程就是在实施某种算法,因此程序设计的实质就是用计算机语言构造解决问题 的算法。算法是程序设计的灵魂,一个好的程序必须有一个好的算法,一个没有 有效算法的程序就像一个没有灵魂的躯体。 算法具有五个特征: 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 则这三个 程序段的时间复杂度分别为 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),很显然,指数阶的算法不是一个好的算法。

中国计算机学会 2014

二是看算法运行时所占用的空间,既空间复杂度。由于当今计算机硬件技术 发展很快,程序所能支配的自由空间一般比较充分,所以空间复杂度就不如时间 复杂度那么重要了,有许多问题人们主要是研究其算法的时间复杂度,而很少讨 论它的空间耗费。 时间复杂性和空间复杂性在一定条件下是可以相互转化的。在中学生信息学 奥赛中,对程序的运行时间作出了严格的限制,如果运行时间超出了限定就会判 错,因此在设计算法时首先要考虑的是时间因素,必要时可以以牺牲空间来换取 时间,动态规划法就是一种以牺牲空间换取时间的有效算法。对于空间因素,视 题目的要求而定,一般可以不作太多的考虑。 我们通过一个简单的数值计算问题,来比较两个不同算法的效率(在这里只 比较时间复杂度) 。 例:求 N!所产生的数后面有多少个 0(中间的 0 不计) 。 算法一:从 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; writeln(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 n<5;

中国计算机学会 2014

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

信息学奥赛中的基本算法(枚举法)

枚举法,常常称之为穷举法,是指从可能的集合中一一枚举各个元素,用题 目给定的约束条件判定哪些是无用的,哪些是有用的。能使命题成立者,即为问 题的解。 采用枚举算法解题的基本思路: (1) 确定枚举对象、枚举范围和判定条件; (2) 一一枚举可能的解,验证是否是问题的解 下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定,这 三个方面来探讨如何用枚举法解题。

枚举算法应用
例 1: 百钱买百鸡问题: 有一个人有一百块钱,打算买一百只鸡。到市场一看, 大鸡三块钱一只,小鸡一块钱三只,不大不小的鸡两块钱一只。现在,请你编一 程序,帮他计划一下,怎么样买法,才能刚好用一百块钱买一百只鸡? 算法分析:此题很显然是用枚举法,我们以三种鸡的个数为枚举对象(分别 设为 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. 上面的条件还有优化的空间,三种鸡的和是固定的,我们只要枚举二种鸡

中国计算机学会 2014

(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)。从上面的对比可以看出,对于枚举算 法,加强约束条件,缩小枚举的范围,是程序优化的主要考虑方向。 在枚举算法中,枚举对象的选择也是非常重要的,它直接影响着算法的时间 复杂度,选择适当的枚举对象可以获得更高的效率。如下例: 例 2、 将 1,2...9 共 9 个数分成三组,分别组成三个三位数,且使这三个三位数 构成 1:2:3 的比例,试求出所有满足条件的三个三位数. 例如:三个三位数 192,384,576 满足以上条件.(NOIP1998pj) 算法分析: 这是 1998 年全国分区联赛普及组试题 (简称 NOIP1998pj, 以下同) 。 此题数据规模不大,可以进行枚举,如果我们不加思地以每一个数位为枚举对象, 一位一位地去枚举: for a:=1 to 9 do for b:=1 to 9 do ??? for i:=1 to 9 do 这样下去,枚举次数就有 99次,如果我们分别设三个数为 x,2x,3x,以 x 为 枚举对象,穷举的范围就减少为93,在细节上再进一步优化,枚举范围就更少 了。程序如下: var t,x:integer; s,st:string; c:char; begin for x:=123 to 321 do{枚举所有可能的解} begin t:=0;

中国计算机学会 2014

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 中} if pos(c,st)<>0 then inc(t) else break;{如果不在 st 中,则退出循环} if t=9 then writeln(x,' ',x*2,' ',x*3); end; end. 在枚举法解题中,判定条件的确定也是很重要的,如果约束条件不对或者不 全面,就穷举不出正确的结果, 我们再看看下面的例子。 例3 一元三次方程求解(noip2001tg) 问题描述 有形如:ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程 中各项的系数(a,b,c,d 均为实数),并约定该方程存在三个不同实根(根的范围 在-100 至 100 之间),且根与根之差的绝对值>=1。 要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到 小数点后 2 位。 提示:记方程 f(x)=0,若存在 2 个数 x1 和 x2,且 x1<x2,f(x1)*(x2)<0,则在 (x1,x2)之间一定有一个根。 样例 输入:1 -5 -4 20 输出:-2.00 2.00 5.00 算法分析:由题目的提示很符合二分法求解的原理,所以此题可以用二分法。 用二分法解题相对于枚举法来说很要复杂很多。此题是否能用枚举法求解呢?再 分析一下题目,根的范围在-100 到 100 之间,结果只要保留两位小数,我们不妨 将根的值域扩大 100 倍(-10000<=x<=10000) ,再以根为枚举对象,枚举范围是 -10000 到 10000,用原方程式进行一一验证,找出方程的解。 有的同学在比赛中是这样做 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. 用这种方法,很快就可以把程序编出来,再将样例数据代入测试也是对的,等 成绩下来才发现这题没有全对,只得了一半的分。

中国计算机学会 2014

这种解法为什么是错的呢?错在哪里?前面的分析好象也没错啊, 难道这题不 能用枚举法做吗? 看到这里大家可能有点迷惑了。 在上面的解法中,枚举范围和枚举对象都没有错,而是在验证枚举结果时,判 定条件用错了。因为要保留二位小数,所以求出来的解不一定是方程的精确根, 再 代 入 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.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)<0) or (f(x-0.005)=0) then write(x:0:2,' '); {若 x 两端的 函数值异号或 x-0.005 刚好是方程的根,则确定 x 为方程的根} end; end. 用枚举法解题的最大的缺点是运算量比较大,解题效率不高,如果枚举范围 太大(一般以不超过两百万次为限) ,在时间上就难以承受。但枚举算法的思路简 单,程序编写和调试方便,比赛时也容易想到,在竞赛中,时间是有限的,我们 竞赛的最终目标就是求出问题解,因此,如果题目的规模不是很大,在规定的时 间与空间限制内能够求出解,那么我们最好是采用枚举法,而不需太在意是否还 有更快的算法,这样可以使你有更多的时间去解答其他难题。

信息学奥赛中的基本算法(回溯法)

中国计算机学会 2014

如果上期的“百钱买百鸡”中鸡的种类数是变化的,用枚举法就无能为力了, 这里介绍另一种算法——回溯法。

回溯基本思想
回溯法是一种既带有系统性又带有跳跃性的搜索法,它的基本思想是:在搜 索过程中,当探索到某一步时,发现原先的选择达不到目标,就退回到上一步重 新选择。它主要用来解决一些要经过许多步骤才能完成的,而每个步骤都有若干 种可能的分支,为了完成这一过程,需要遵守某些规则,但这些规则又无法用数 学公式来描述的一类问题。下面通过实例来了解回溯法的思想及其在计算机上实 现的基本方法。 例 1、从 N 个自然数(1,2,…,n)中选出 r 个数的所有组合。 算法分析:设这 r 个数为 a1,a2,?ar,把它们从大到小排列,则满足: (1) a1>a2>?>ar; (2) 其中第 i 位数(1<=i<=r)满足 ai>r-i; 我们按以上原则先确定第一个数,再逐位生成所有的 r 个数,如果当前数符 合要求,则添加下一个数;否则返回到上一个数,改变上一个数的值再判断是否符 合要求,如果符合要求,则继续添加下一个数,否则返回到上一个数,改变上一 个数的值??按此规则不断循环搜索,直到找出 r 个数的组合,这种求解方法就 是回溯法。 如果按以上方法生成了第 i 位数 ai,下一步的的处理为: (1) 若 ai>r-i 且 i=r,则输出这 r 个数并改变 ai 的值:ai=ai-1; (2) 若 ai>r-i 且 i≠r,则继续生成下一位 ai+1=ai-1; (3) 若 ai<=r-i,则回溯到上一位,改变上一位数的值:ai-1=ai-1-1; 算法实现步骤: 第一步:输入 n,r 的值,并初始化; i:=1;a[1]:=n; 第二步:若 a[1]>r-1 则重复: 若 a[i]>r-i,①若 i=r,则输出解,并且 a[i]:=a[i]-1; ②若 i<>r,则继续生成下一位:a[i+1]:=a[i]-1; i:=i+1; 若 a[i]<=r-i,则回溯:i:=i-1; a[i]:=a[i]-1; 第三步:结束; 程序实现 var n,r,i,j:integer; a:array[1..10] of integer; begin readln(n,r);i:=1;a[1]:=n; repeat if a[i]>r-i then {符合条件 } if i=r then {输出} begin for j:=1 to r do write(a[j]:3); writeln; a[i]:=a[i]-1; end else {继续搜索}

中国计算机学会 2014

begin a[i+1]:=a[i]-1; i:=i+1;end else{回溯} begin i:=i-1; a[i]:=a[i]-1;end; until a[1]=r-1; end. 下面我们再通过另一个例子看看回溯在信息学奥赛中的应用。 例 2 数的划分(noip2001tg) 问题描述 整数 n 分成 k 份,且每份不能为空,任意两份不能相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 输入:n,k (6<n<=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) 如果 i=k,则得到一个解, 则计数器 t 加 1, 并回溯到上一步, 改变 ai-1 的值; (2) 如果 i<k 且 sum>=ai,则添加下一个元素 ai+1; (3) 如果 i<k 且 sum<ai,则说明达不到目标,回溯到上一步,改变 ai-1 的值; 算法实现步骤如下: 第一步:输入自然数 n,k 并初始化;t:=0; i:=1;a[i]:=1; sum:=n-1; nk:=n div k; 第二步:如果 a[1]<=nk 重复: 若 i=k,搜索到一个解,计数器 t=t+1;并回溯; 否则:①若 sum>=a[i]则继续搜索; ②若 sum<a[i]则回溯; 搜索时,inc(i);a[i]:=a[i-1];sum:=sum-a[i]; 回溯时,dec(i); inc(a[i]); sum:=sum+a[i+1]-1; 第三步:输出。 程序如下: var

中国计算机学会 2014

n,nk,sum,i,k:integer; t:longint; a:array[1..6]of integer; begin readln(n,k); nk:=n div k; t:=0; i:=1;a[i]:=1; sum:=n-1;{初始化} repeat if i=k then{判断是否搜索到底} begin inc(t); dec(i);inc(a[i]); sum:=sum+a[i+1]-1; end {回溯} else begin if sum>=a[i] then {判断是否回溯} begin inc(i);a[i]:=a[i-1];sum:=sum-a[i];end{继续搜} else begin dec(i); inc(a[i]); sum:=sum+a[i+1]-1; end;{回溯} end; until a[1]>nk; writeln(t); end. 回溯法是通过尝试和纠正错误来寻找答案,是一种通用解题法,在 NOIP 中有 许多涉及搜索问题的题目都可以用回溯法来求解。

信息学奥赛中的基本算法(递归算法)
递归算法的定义: 如果一个对象的描述中包含它本身,我们就称这个对象是递归的,这种用递 归来描述的算法称为递归算法。 我们先来看看大家熟知的一个的故事: 从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说从前有 座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说?? 上面的故事本身是递归的,用递归算法描述: procedure bonze-tell-story; begin if 讲话被打断 then 故事结束 else begin 从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事; bonze-tell-story; end end;

中国计算机学会 2014

从上面的递归事例不难看出,递归算法存在的两个必要条件: (1) 必须有递归的终止条件; (2) 过程的描述中包含它本身; 在设计递归算法中,如何将一个问题转化为递归的问题,是初学者面临的难 题,下面我们通过分析汉诺塔问题,看看如何用递归算法来求解问题; 递归算法应用 例 1:汉诺塔问题,如下图,有 A、B、C 三根柱子。A 柱子上按从小到大的顺 序堆放了 N 个盘子,现在要把全部盘子从 A 柱移动到 C 柱,移动过程中可以借助 B 柱。移动时有如下要求: (1) 一次只能移动一个盘子; (2) 不允许把大盘放在小盘上边; (3) 盘子只能放在三根柱子上;

算法分析:当盘子比较多的时,问题比较复杂,所以我们先分析简单的情况: 如果只有一个盘子,只需一步,直接把它从 A 柱移动到 C 柱; 如果是二个盘子,共需要移动 3 步: (1) 把 A 柱上的小盘子移动到 B 柱; (2) 把 A 柱上的大盘子移动到 C 柱; (3) 把 B 柱上的大盘子移动到 C 柱; 如果 N 比较大时,需要很多步才能完成,我们先考虑是否能把复杂的移动过 程转化为简单的移动过程,如果要把 A 柱上最大的盘子移动到 C 柱上去,必须先 把上面的 N-1 个盘子从 A 柱移动到 B 柱上暂存,按这种思路,就可以把 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 Hanoi(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 柱}

中国计算机学会 2014

end; end; 从上面的例子我们可以看出,在使用递归算法时,首先弄清楚简单情况下的 解法,然后弄清楚如何把复杂情况归纳为更简单的情况。 在信息学奥赛中有的问题的结构或所处理的数据本身是递归定义的,这样的 问题非常适合用递归算法来求解,对于这类问题,我们把它分解为具有相同性质 的若干个子问题,如果子问题解决了,原问题也就解决了。 例 2 求先序排列 (NOIP2001pj) [问题描述]给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树 结点用不同的大写字母表示,长度≤8)。 [样例] 输入:BADC BDCA 输出:ABCD 算法分析:我们先看看三种遍历的定义: 先序遍历是先访问根结点,再遍历左子树,最后遍历右子树; 中序遍历是先遍历左子树,再访问根结点,最后遍历右子树; 后序遍历是先遍历左子树,再遍历右子树,最后访问根结点; 从遍历的定义可知,后序排列的最后一个字符即为这棵树的根节点;在中序 排列中,根结点前面的为其左子树,根结点后面的为其右子树;我们可以由后序 排列求得根结点,再由根结点在中序排列的位置确定左子树和右子树,把左子树 和右子树各看作一个单独的树。这样,就把一棵树分解为具有相同性质的二棵子 树,一直递归下去,当分解的子树为空时,递归结束,在递归过程中,按先序遍 历的规则输出求得的各个根结点,输出的结果即为原问题的解。 源程序 program noip2001_3; var z,h : string; procedure make(z,h:string); {z 为中序排列,h 为后序排列} var s,m : integer; begin m:=length(h);{m 为树的长度} write(h[m]); {输出根节点} s:=pos(h[m],z); {求根节点在中序排列中的位置} if s>1 then make(copy(z,1,s-1),copy(h,1,s-1)); {处理左子树} if m>s then make(copy(z,s+1,m-s),copy(h,s,m-s)); {处理右子树} end; begin readln(z); readln(h); make(z,h); end. 递归算法不仅仅是用于求解递归描述的问题,在其它很多问题中也可以用到 递归思想,如回溯法、分治法、动态规划法等算法中都可以使用递归思想来实现, 从而使编写的程序更加简洁。

中国计算机学会 2014

比如上期回溯法所讲的例 2《数的划分问题》 ,若用递归来求解,程序非常短 小且效率很高,源程序如下 var n,k:integer; tol:longint; procedure make(sum,t,d:integer); var i:integer; begin 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) (n>2) 用递归过程描述为: Funtion fb(n:integer):integer; Begin if n<3 then fb:=1 else fb:=fb(n-1)+fb(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 中,数据的规模一般也不大,只要问题适合用递归算法求 解,我们还是可以大胆地使用递归算法。

中国计算机学会 2014

算法在信息学奥赛中的应用 (递推法)
所谓递推,是指从已知的初始条件出发,依据某种递推关系,逐次推出所要 求的各中间结果及最后结果。其中初始条件或是问题本身已经给定,或是通过对 问题的分析与化简后确定。 可用递推算法求解的题目一般有以下二个特点: (1) 问题可以划分成多个状态; (2) 除初始状态外,其它各个状态都可以用固定的递推关系式来表示。 在我们实际解题中,题目不会直接给出递推关系式,而是需要通过分析各种 状态,找出递推关系式。

递推法应用
例 1 骑士游历:(noip1997tg) 设有一个 n*m 的棋盘(2<=n<=50,2<=m<=50),如下图,在棋盘上任一点有一个中国象 棋马,

马走的规则为:1.马走日字

2.马只能向右走,即如下图所示:

任务 1:当 N,M 输入之后,找出一条从左下角到右上角的路径。 例如:输入 N=4,M=4

输出:路径的格式:(1,1)->(2,3)->(4,4) 若不存在路径,则输出"no" 任务 2:当 N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终 点的所有路径的数目。 例如:(N=10,M=10),(1,5)(起点),(3,5)(终点)

中国计算机学会 2014

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

根据马走的规则,马可以由(i-dx[k],j-dy[k])走到(i,j)。只要马能从(1, 1)走到(i-dx[k],j-dy[k]) ,就一定能走到(i,j),马走的坐标必须保证在棋盘 上。我们以(n,m)为起点向左递推,当递推到(i-dx[k],j-dy[k])的位置是(1, 1)时,就找到了一条从(1,1)到(n,m)的路径。 我们用一个二维数组 a 表示棋盘,对于任务一,使用倒推法,从终点(n,m)往 左递推, 设初始值 a[n,m]为 (-1, -1) , 如果从(i,j)一步能走到(n,m), 就将(n,m) 存放在 a[i,j]中。如下表,a[3,2]和 a[2,3]的值是(4,4) ,表示从这两个点都 可以到达坐标(4,4) 。从(1,1)可到达(2,3) 、 (3,2)两个点,所以 a[1,1] 存放两个点中的任意一个即可。递推结束以后,如果 a[1,1]值为(0,0)说明不存在 路径,否则 a[1,1]值就是马走下一步的坐标,以此递推输出路径。 -1,-1 4,4 4,4 2,3 任务一的源程序: const dx:array[1..4]of integer=(2,2,1,1);

中国计算机学会 2014

dy:array[1..4]of integer=(1,-1,2,-2); type map=record x,y:integer; end; var i,j,n,m,k:integer; a:array[0..50,0..50]of map; begin read(n,m); fillchar(a,sizeof(a),0); a[n,m].x:=-1;a[n,m].y:=-1;{标记为终点} for i:=n downto 2 do {倒推} for j:=1 to m do if a[i,j].x<>0 then for k:=1 to 4 do begin a[i-dx[k],j-dy[k]].x:=i; a[i-dx[k],j-dy[k]].y:=j; end; if a[1,1].x=0 then writeln('no') else begin{存在路径} i:=1;j:=1; write('(',i,',',j,')'); while a[i,j].x<>-1 do begin k:=i; i:=a[i,j].x;j:=a[k,j].y; write('->(',i,',',j,')'); end; end; end. 对于任务二,也可以使用递推法,用数组 A[i,j]存放从起点(x1,y1)到(i,j) 的路径总数,按同样的方法从左向右递推,一直递推到(x2,y2),a[x2,y2]即为 所求的解。源程序(略) 在上面的例题中,递推过程中的某个状态只与前面的一个状态有关,递推关 系并不复杂,如果在递推中的某个状态与前面的所有状态都有关,就不容易找出 递推关系式,这就需要我们对实际问题进行分析与归纳,从中找到突破口,总结 出递推关系式。我们可以按以下四个步骤去分析: ( 1)细心的观察; (2)丰富的

中国计算机学会 2014

联想; (3)不断地尝试; (4)总结出递推关系式。 下面我们再看一个复杂点的例子。 例 2、栈(noip2003pj) 题目大意:求 n 个数通过栈后的排列总数。 (1≤n≤18) 如输入 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 时的二种情况,排列数分别为 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(0); 即 f(n)=
0?i ?n ?1

? f (i) * f (n ? i ? 1)

(n>=1)

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

中国计算机学会 2014

算法在信息学奥赛中的应用 (分治法)

分治算法的基本思想是将一个规模为 N 的问题分解为 K 个规模较小的子问题, 这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的 解。 分治法解题的一般步骤: (1)分解,将要解决的问题划分成若干规模较小的同类问题; (2)求解,当子问题划分得足够小时,用较简单的方法解决; (3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。

分治法应用
例1、 比赛安排(noip1996) 设有 2^n(n<=6)个球队进行单循环比赛,计划在 2^n-1 天内完成,每个队每天进 行一场比赛。设计一个比赛的安排,使在 2^n-1 天内每个队都与不同的对手比赛。 例如 n=2 时的比赛安排为: 队 1 2 3 4 比赛 1-2 3-4 第一天 1-3 2-4 第二天 1-4 2-3 第三天 算法分析:此题很难直接给出结果,我们先将问题进行分解,设 m=2^n,将规 模减半,如果 n=3(即 m=8),8 个球队的比赛,减半后变成 4 个球队的比赛(m=4) ,4 个球队的比赛的安排方式还不是很明显,再减半到两 个球队的比赛(m=2),两个球队 的比赛安排方式很简单,只要让两个球队直接进行一场比赛即可: 1 2 2 1 分析两个球队的比赛的情况不难发现,这是一个对称的方阵,我们把这个方阵 分成 4 部分(即左上,右上,左下,右下) ,右上部分可由左上部分加 1(即加 m/2) 得到,而右上与左下部分、左上与右下部分别相等。因此我们也可以把这个方阵 看作是由 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

中国计算机学会 2014

5 6 7 8

6 7 8 1 2 3 4 5 8 7 2 1 4 3 8 5 6 3 4 1 2 7 6 5 4 3 2 1 这样就构成了整个比赛的安排表。 在算法设计中,用数组 a 记录 2^n 个球队的循环比赛表,整个循环比赛表从最 初的 1*1 方阵按上述规则生成 2*2 的方阵,再生成 4*4 的方阵,??直到生成出 整个循环比赛表为止。变量 h 表示当前方阵的大小,也就是要生成的下一个方阵的 一半。 源程序: var i,j,h,m,n:integer; a:array[1..32,1..32]of integer; begin readln(n); m:=1;a[1,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 a[i,j+h]:=a[i,j]+h;{构造右上角方阵} a[i+h,j]:=a[i,j+h];{构造左下角方阵} a[i+h,j+h]:=a[i,j];{构造右下角方阵} end; h:=h*2; until h=m; for i:=1 to m do begin for j:=1 to m do write(a[i,j]:4); writeln; end; end. 在分治算法中,若将原问题分解成两个较小的子问题,我们称之为二分法,由 于二分法划分简单,所以使用非常广泛。使用二分法与使用枚举法求解问题相比 较,时间复杂度由 O(N)降到 O(log2N) ,在很多实际问题中,我们可以通过使用 二分法,达到提高算法效率的目的,如下面的例子。 例 2 一元三次方程求解(noip2001tg) 题目大意:给出一个一元三次方程 f(x)=ax3+bx2+cx+d=0 ,求它的三个根。所有的 根都在区间[-100,100]中,并保证方程有三个实根,且它们之间的差不小于 1。

中国计算机学会 2014

算法分析:在讲解枚举法时,我们讨论了如何用枚举法求解此题,但如果求解 的精度进一步提高,使用枚举法就无能为力了,在此我们再一次讨论如何用二分 法求解此题。 由题意知(i,i+1)中若有根,则只有一个根,我们枚举根的值域中的每一个 整数 x(-100≤x≤100),设定搜索区间[x1,x2],其中 x1=x,x2=x+1。若: ⑴f(x1)=0,则确定 x1 为 f(x)的根; ⑵f(x1)*f(x2)<0,则确定根 x 在区间[x1,x2]内。 ⑶f(x1)*f(x2)>0,则确定根 x 不在区间[x1,x2]内,设定[x2,x2+1]为下一个搜索 区间; 若确定根 x 在区间[x1,x2]内,采用二分法,将区间[x1,x2]分成左右两个子 区间: 左子区间[x1, x]和右子区间[x, x2] (其中 x= (x1+x2) /2) 。 如果 f(x1)*f(x)≤0, 则确定根在左区间[x1,x]内,将 x 设为该区间的右界值(x2=x),继续对左区间 进行对分;否则确定根在右区间[x,x2]内,将 x 设为该区间的左界值(x1=x), 继续对右区间进行对分; 上述对分过程一直进行到区间的间距满足精度要求为止(即 x2-x1<0.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+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 then begin while x2-x1>=0.005 do begin xx:=(x1+x2)/2; if f(x1)*f(xx)<=0 then x2:=xx else x1:=xx; end;{while} write(x1:0:2,' '); end; {then}

中国计算机学会 2014

end;{for} end.

信息学奥赛中的基本算法(贪心法)
在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直 接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解, 这种求解方法就是贪心算法。 从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的 选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心 算法可以得到最优解。 我们看看下面的例子

贪心法应用
例 1 均分纸牌(NOIP2002tg) [问题描述] 有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌 总数必为 N 的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在 编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸 牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边 的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样 多。例如 N=4,4 堆纸牌数分别为: ① 9 ② 8 ③ 17 ④ 6 移动 3 次可达到目的: 从 ③ 取 4 张牌放到 ④ (9 8 13 10) -> 从 ③ 取 3 张牌放到 ②(9 11 10 10)-> 从 ② 取 1 张牌放到①(10 10 10 10) 。 [输 入]:键盘输入文件名。 文件格式:N(N 堆纸牌,1 <= N <= 100) A1 A2 … An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) [输 出]:输出至屏幕。格式为:所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in: 4

中国计算机学会 2014

9 8 17 6 屏慕显示:3 算法分析:设 a[i]为第 i 堆纸牌的张数(0<=i<=n) ,v 为均分后每堆纸牌的张数,s 为最小移到次数。 我们用贪心法,按照从左到右的顺序移动纸牌。如第 i 堆(0<i<n)的纸牌数 a[i] 不等于平均值,则移动一次(即 s 加 1),分两种情况移动: (1) 若 a[i]>v,则将 a[i]-v 张纸牌从第 I 堆移动到第 I+1 堆; (2) 若 a[i]<v,则将 v -a[i]张纸牌从第 I+1 堆移动到第 I 堆; 为了设计的方便,我们把这两种情况统一看作是将 a[I]-v 张牌从第 I 堆移动到 第 I+1 堆;移动后有:a[I]:=v;a[I+1]:=a[I+1]+a[I]-v; 在从第 i+1 堆中取出纸牌补充第 i 堆的过程中,可能会出现第 i+1 堆的纸牌数 小于零(a[i+1]+a[i]-v<0 )的情况。 如 n=3,三堆纸牌数为(1,2,27)这时 v=10,为了使第一堆数为 10,要从 第二堆移 9 张纸牌到第一堆,而第二堆只有 2 张纸牌可移,这是不是意味着刚才 使用的贪心法是错误的呢? 我们继续按规则分析移牌过程,从第二堆移出 9 张到第一堆后,第一堆有 10 张纸牌,第二堆剩下-7 张纸牌,再从第三堆移动 17 张到第二堆,刚好三堆纸牌数 都是 10,最后结果是对的,从第二堆移出的牌都可以从第三堆得到。我们在移动 过程中,只是改变了移动的顺序,而移动的次数不变,因此此题使用贪心法是可 行的。 源程序: var i,n,s:integer;v:longint; a:array[1..100]of longint; f:text;fil:string; begin readln(fil); assign(f,fil);reset(f); readln(f,n);v:=0; for i:=1 to n do begin read(f,a[i]); inc(v,a[i]); end; v:=v div n; {每堆牌的平均数} for i:=1 to n-1 do if a[i]<>v then {贪心选择} begin inc(s);{移牌步数计数} a[i+1]:=a[i+1]+a[i]-v;{使第 i 堆牌数为 v} end;{then} writeln(s); end.

中国计算机学会 2014

利用贪心算法解题,需要解决两个问题: 一是问题是否适合用贪心法求解。我们看一个找币的例子,如果一个货币系统 有 3 种币值,面值分别为一角、五分和一分,求最小找币数时,可以用贪心法求解; 如果将这三种币值改为一角一分、五分和一分,就不能使用贪心法求解。用贪心 法解题很方便,但它的适用范围很小,判断一个问题是否适合用贪心法求解,目 前还没有一个通用的方法,在信息学竞赛中,需要凭个人的经验来判断何时该使 用贪心算法。 二是确定了可以用贪心算法之后,如何选择一个贪心标准,才能保证得到问 题的最优解。在选择贪心标准时,我们要对所选的贪心标准进行验证才能使用, 不要被表面上看似正确的贪心标准所迷惑,如下面的列子。 例 2 (NOIP1998tg)设有 n 个正整数,将他们连接成一排,组成一个最大的 多位整数。例如:n=3 时,3 个整数 13,312,343,连成的最大整数为:34331213 又如:n=4 时,4 个整数 7,13,4,246 连接成的最大整数为 7424613 输入:N N 个数 输出:连接成的多位数 算法分析:此题很容易想到使用贪心法,在考试时有很多同学把整数按从大 到小的顺序连接起来,测试题目的例子也都符合,但最后测试的结果却不全对。 按这种贪心标准,我们很容易找到反例:12,121 应该组成 12121 而非 12112,那 么是不是相互包含的时候就从小到大呢?也不一定,如:12,123 就是 12312 而 非 12112,这样情况就有很多种了。是不是此题不能用贪心法呢? 其实此题是可以用贪心法来求解,只是刚才的贪心标准不对,正确的贪心标 准是:先把整数化成字符串,然后再比较 a+b 和 b+a,如果 a+b>b+a,就把 a 排在 b 的前面,反之则把 a 排在 b 的后面。 源程序: var s:array[1..20] of string; t:string;i,j,k,n:longint; begin readln(n); for i:=1 to n do begin read(k); str(k,s[i]); end; for i:=1 to n-1 do for j:=i+1 to n do if s[i]+s[j]<s[j]+s[i] then begin{交换} t:=s[i]; s[i]:=s[j]; s[j]:=t;

中国计算机学会 2014

end; for i:=1 to n do write(s[i]); end. 贪心算法所作的选择可以依赖于以往所作过的选择,但决不依赖于将来的选 择,也不依赖于子问题的解,因此贪心算法与其它算法相比具有一定的速度优势。 如果一个问题可以同时用几种方法解决,贪心算法应该是最好的选择之一。

算法在信息学奥赛中的应用(搜索法一)
在这里介绍两种基本的搜索算法:深度优先搜索和广度优先搜索法,以树的 搜索为例,深度优先搜索法是优先扩展尚未扩展的且具有最大深度的结点;广度 优先搜索法是在扩展完第 K 层的结点以后才扩展 K+1 层的结点。 深度优先搜索法与前面讲的回溯法差不多,主要的区别是回溯法在求解过程 中不保留完整的树结构,而深度优先搜索则记下完整的搜索树,搜索树起记录解 路径和状态判重的作用。为了减少存储空间,在深度优先搜索中,用标志的方法 记录访问过的状态,这种处理方法使得深度优先搜索法与回溯法没什么区别了。 在回溯法中,我们己分析了非递归的实现过程,在这里就只讨论深度优先的递归 实现方法。 深度优先搜索的递归实现过程: procedure dfs(i); for i:=1 to r do if 子结点 mr 符合条件 then 产生的子结点 mr 入栈; if 子结点 mr 是目标结点 then 输出 else dfs(i+1); 栈顶元素出栈(即删去 mr); endif; endfor; 在讲解递推法时,我们讨论了用递推法解骑土游历问题,在这里我们再看看 如何用深度优先搜索法求解此题。

中国计算机学会 2014

搜索算法应用 例 1 骑士游历:设有一个 n*m 的棋盘,在棋盘上任一点有一个中国象棋马,马 走的规则为:1.马走日字 2.马只能向右走。当 N,M 输入之后,找出一条从左下角 到右上角的路径。例如:输入 N=4,M=4,输出:路径的格式:(1,1)->(2,3)->(4,4), 若不存在路径,则输出"no" 算法分析: 我们以 4×4 的棋盘为例进行分析, 用树形结构表示马走的所有过程 (如 下图),求从起点到终点的路径,实际上就是从根结点开始深度优先搜索这棵树。

马从(1,1)开始,按深度优先搜索法,走一步到达(2,3),判断是否到 达终点,若没有,则继续往前走,再走一步到达(4,4),然后判断是否到达终 点,若到达则退出,搜索过程结束。为了减少搜索次数,在马走的过程中,判断 下一步所走的位置是否在棋盘上,如果不在棋盘上,则另选一条路径再走。 程序如下: const dx:array[1..4]of integer=(2,2,1,1); dy:array[1..4]of integer=(1,-1,2,-2); type map=record x,y:integer; end; var i,n,m:integer; a:array[0..50]of map; procedure dfs(i:integer); var j:integer; begin for j:=1 to 4 do if (a[i-1].x+dx[j]>0)and(a[i-1].x+dx[j]<=n) and(a[i-1].y+dy[j]>0)and(a[i-1].y+dy[j]<=n) then{判断是否在棋盘上} begin

中国计算机学会 2014

a[i].x:=a[i-1].x+dx[j]; a[i].y:=a[i-1].y+dy[j];{入栈} if (a[i].x=n)and(a[i].y=m)then begin write('(',1,',',1,')'); for j:=2 to i do write('->(',a[j].x,',',a[j].y,')'); halt;{输出结果并退出程序} end; dfs(i+1);{搜索下一步} a[i].x:=0;a[i].y:=0;{出栈} end; end; begin a[1].x:=1;a[1].y:=1; readln(n,m); dfs(2); writeln('no'); end. 从上面的例子我们可以看出,深度优先搜索算法有两个特点: 1、己产生的结点按深度排序,深度大的结点先得到扩展,即先产生它的子结 点。 2、深度大的结点是后产生的,但先得到扩展,即“后产生先扩展”,与栈的 工作原理相同, 因此用堆栈作为该算法的主要数据结构, 存储产生的结点。 对于不同的问题,深度优先搜索算法基本上是一样的,但在具体处理方法和 编程技巧上又都不相同,甚至会有很大的差别。我们再看看另一个例子。 题二 选数(存盘名:NOIP2002pj) [问题描述]:已知 n 个整数 x1,x2,?,xn,以及一个整数 k(k<n)。从 n 个整数 中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分 别为 3,7,12,19 时,可得全部的组合与它们的和为:3+7+12=22 3+7+ 19=29 7+12+19=38 3+12+19=34。现在,要求你计算出和为素数共 有多少种。例如上例,只有一种的和为素数:3+7+19=29。 [输入]:键盘输入,格式为: n , k (1<=n<=20,k<n)

中国计算机学会 2014

x1,x2,?,xn (1<=xi<=5000000) [输出]:屏幕输出,格式为: 一个整数(满足条件的种数)。 [输入输出样例]: 输入:4 3 3 7 12 19 输出:1 算法分析:本题是求从 n 个数中选 k 个数的组合,并使其和为素数。求解此题时, 先用深度优先搜索法生成 k 个数的组合,再判断 k 个数的和是否为素数,若为素 数则总数加 1。 在程序实现过程中,用数组 a 存放输入的 n 个数,用 s 表示 k 个数的和,ans 表示和为素数的个数。为了避免不必要的搜索,程序对搜索过程进行了优化,限 制搜索范围,在搜索过程 dfs(i,m)中,参数 m 为第 i 个数的上限,下限为 n-k+i。 源程序: var n,k,i: byte; ans,s:longint; a: array[1 .. 20] of Longint; procedure prime(s:longint);{判断 K 个数的和是否为素数} var i:integer; begin i:=2; while (sqr(i)<=s)and(s mod i<>0) do inc(i); if sqr(i)>s then end; inc(ans){若为素数则总数加 1}

procedure dfs(i,m:byte);{搜索第 i 个数, } var j:byte;{j 表示第 i 个数的位置 begin for j:=m to n-k+i do{枚举第 i 个数} begin inc(s,a[j]);{入栈} if i=k then prime(s)

中国计算机学会 2014

else dfs(i+1,j+1);{继续搜第 i+1 个数} dec(s,a[j]){出栈} end end; begin readln(n,k); for i:=1 to n do read(a[i]); ans:=0; s:=0; dfs(1,1); writeln(ans); end. 从上面的两个例子我们可以看出,用递归实现深度优先搜索比非递归更加方 便。 在使用深度搜索法解题时,搜索的效率并不高,所以要重视对算法的优化, 尽可能的减少搜索范围,提高程序的速度。 在下一篇中将继续介绍另一种搜索方法——广度优先搜索法。

算法在信息学奥赛中的应用(搜索法二)
在深度优先搜索算法中,深度越大的结点越先得到扩展,若把它改为深度越 小的结点越先得到扩展,就是广度优先搜索法。 广度优先搜索基本算法: program bfs; 初始化;建立队列 data; 设队列首指针 closed:=0;队列尾指针 open:=1; repeat closed 增 1,取出 closed 所指结点进行扩展; for i:=1 to r do begin

if 子结点符合条件 then begin open 增 1,并把新结点存入数据库队尾; if 新结点与原有结点有重复 then 删于该结点(open 减 1) else if 新结点即目标 then 输出并退出 ; end{if};

中国计算机学会 2014

end{for}; until closed>=open;{队列为空} 使用广度优先搜索时,离根结点最近的结点先扩展,所以广度优先搜索法比 较适合求步数最少的解,由于深度优先使用了标志法,使得存储空间大大减少, 而广度优先要保留所有搜索过的节点,随着搜索程度的加深,所需的存储空间成 指数增加。因此在必要时我们采用双向搜索来减少搜索空间和存储空间,如下面 的例子。 广度优先算法应用 例 字串变换(NOIP2002tg) [问题描述]:已知有两个字串 A$, B$ 及一组字串变换的规则(至多 6 个规则): A1$ -> B1$ A2$ -> B2$ 规则的含义为:在 A$中的子串 A1$ 可以变换为 B1$、 A2$ 可以变换为 B2$ ?。 例如: A$='abcd' B$='xyz' 变换规则为: ‘abc’-> ‘xu’ ‘ud’->‘y’ ‘y’->‘yz’ 则此时,A$ 可以经过一系列的变换变为 B$,其变换的 过程为: ‘abcd’->‘xud’->‘xy’->‘xyz’ 共进行了三次变换,使得 A$ 变换为 B$。 [输入]:键盘输人文件名。文件格式如下: A$ B$ A1$ B1$ \ A2$ B2$ |-> 变换规则 ... ... / 所有字符串长度的上限为 20。 [输出]:输出至屏幕。格式如下: 若在 10 步 (包含 10 步) 以内能将 A$ 变换为 B$ , 则输出最少的变换步数; 否则输出"NO ANSWER!" [输入输出样例] b.in: abcd xyz abc xu ud y y yz 屏幕显示:3 算法分析:此题是求变换的最少步数,很显然可以使用广度优先搜索法,如果直 接从初状态搜到目标状态,最坏情况下存储的结点数超过 6 的 10 次方幂,搜索空 间过大,因此我们考虑使双向搜索,同时从初始状态和目标状态向中间状态搜索, 当相遇时搜索结束。采用双向搜索,存储的结点数还有可能超限,我们在前向搜 索队列中存储 5 步内变换的结点,在后向搜索队列中,由于第 5 步产生的结点只

中国计算机学会 2014

是用来与前向队列中的结点比较,所以可以不存储在队列中,后向搜索队列只需 存储 4 步内的结点,这样就解决了存储空间问题。 为了使用方便,在程序设计中用一个数组 a[1..max]存储两个队列,前向搜索 队列为 a[1..mid],后向搜索队列为 a[mid..max],用 st 存储搜索方向,st=0 表 示前向搜索,st=1 表示后向搜索,用 op[st]和 cl[st]分别表示队列尾指针和首指 针,用 be 表示队列起始位置,循环产生每一个结点,若在 10 内无解退出循环, 若在 10 内找到解则输出解并退出程序。 源程序: const mid=12000;max=16000; type node=record s:string;x:byte;end; var i,mark:integer; a:array [1..max]of ^node; x:array[0..6,0..1]of string[20]; d,fil:string; op,cl:array [0..1] of integer; procedure Init;{读取数据,初始化} var f:text;t:string; begin readln(fil); assign(f,fil);reset(f);i:=0; while not eof(f) do begin readln(f,t); x[i,0]:=copy(t,1,pos(' ',t)-1); x[i,1]:=copy(t,pos(' ',t)+1,length(t)); inc(i); end;{while} mark:=i-1;close(f); end; {判断是否到达目标状态} procedure bool(be,st:integer); begin for i:=mid-be+1 to cl[1-st] do if a[cl[st]]^.s=a[i]^.s then begin writeln(a[cl[st]]^.x+a[i]^.x); halt; end;{if} end; {判断节点是否与前面的结点重复} procedure check(be,st:integer);

中国计算机学会 2014

begin for i:=be+1 to cl[st]-1 do if a[i]^.s=a[cl[st]]^.s then begin dec(cl[st]);exit; end; bool(be,st); end; {扩展产生新节点} procedure expand(be,st:integer); var i,j,k,lx,ld:integer; begin inc(op[st]);d:=a[op[st]]^.s; k:=a[op[st]]^.x;ld:=length(d); for i:=1 to mark do begin lx:=length(x[i,st]); for j:=1 to ld do begin if (copy(d,j,lx)=x[i,st]) then begin if (st<>1)or(k<>4)then begin inc(cl[st]); new(a[cl[st]]); end;{if} a[cl[st]]^.s:= copy(d,1,j-1)+ x[i,1-st]+ copy(d,j+lx,ld); a[cl[st]]^.x:=k+1; check(be,st);{检查是否重复} end;{if} end;{for} end;{for} end; procedure bfs; var be,k,st:integer; Begin for st:=0 to 1 do begin if st=0 then be:=0 else be:=mid; op[st]:=be+0;cl[st]:=be+1; new(a[cl[st]]); a[cl[st]]^.s:=x[0,st]; a[cl[st]]^.x:=0; end;{for} repeat if (op[0]<cl[0])and(a[cl[0]]^.x<=5)then expand(0,0); if (op[1]<cl[1])and(a[cl[1]]^.x<=5)then expand(mid,1); until(op[0]>=cl[0])or(a[cl[0]]^.x>5)or(op[1]>=cl[1])or

中国计算机学会 2014

(a[cl[1]]^.x>5); End; BEGIN init;bfs;writeln('NO ANSWER!') END. 两种搜索算法的比较: 搜索方式 扩展方式 深度优先 后产生先扩展 广度优先 先产生先扩展 数据结构 栈 队列 适合求解的问题 可行解或所有解 最优解

在选择搜索方式时,并不是完全遵循以上原则,具体还是要根据题目的要求 而定。在求最优解时,如果搜索的深度不大,我们也可以考虑使用深度优先搜索; 在求解可行解时,如果搜索的深度没有限制,或者搜索的代价与搜索的深度成正 比,我们也应该使用广度优先搜索。

算法在信息学奥赛中的应用(动态规划法)
在学习动态规划法之前,我们先来了解动态规划的几个概念 1、 阶段:把问题分成几个相互联系的有顺序的几个环节,这些环节即称为阶段。 2、 状态:某一阶段的出发位置称为状态。 3、 决策:从某阶段的一个状态演变到下一个阶段某状态的选择。 4、 状态转移方程:前一阶段的终点就是后一阶段的起点,前一阶段的决策选择导 出了后一阶段的状态,这种关系描述了由 k 阶段到 k+1 阶段状态的演变规律, 称为状态转移方程。 动态规划法的定义:在求解问题中,对于每一步决策,列出各种可能的局部解,
再依据某种判定条件,舍弃那些肯定不能得到最优解的局部解,在每一步都经过筛选,以每一 步都是最优解来保证全局是最优解,这种求解方法称为动态规划法。

一般来说,适合于用动态规划法求解的问题具有以下特点: 1、可以划分成若干个阶段,问题的求解过程就是对若干个阶段的一系列决策过 程。 2、每个阶段有若干个可能状态 3、一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。 4、在任一个阶段,最佳的决策序列和该阶段以前的决策无关。 5、各阶段状态之间的转换有明确定义的费用,而且在选择最佳决策时有递推关系 (即动态转移方程) 。 动态规划法所处理的问题是一个多阶段最优化决策问题,一般由初始状态开 始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,

中国计算机学会 2014

同时确定了完成整个过程的一条活动路线。如下图:

动态规划设计都有着一定的模式,一般要经历以下几个步骤: 1、划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。 2、确定状态:将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出 来。 3、确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转 移就是根据上一阶段的状态和决策来导出本阶段的状态,所以如果确定了决策, 状态转移方程也就可以写出。 4、寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件 或边界条件。 5、程序设计实现:动态规划的主要难点在于理论上的设计,一旦设计完成,实现 部分就会非常简单。 根据以上的步骤设计,可以得到动态规划设计的一般模式: for k:=阶段最小值 to 阶段最大值 do {顺推每一个阶段} for I:=状态最小值 to 状态最大值 do {枚举阶段 k 的每一个状态} for j:=决策最小值 to 决策最大值 do {枚举阶段 k 中状态 i 可选择的每一种 决策} f[ik]:=min(max){f[ik-1]+a[ik-1,jk-1]|ik-1 通过决策 jk-1 可达 ik} 有了以上的设计模式,对于简单的动态规划问题,就可以按部就班地进行动态规 划设计。 动态规划算法应用 例 1:合唱队形(noip2004tg) 【问题描述】N 位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩 下的 K 位同学排成合唱队形。合唱队形是指这样的一种队形:设 K 位同学从左到 右依次编号为 1, 2, …, K, 他们的身高分别为 T1, T2, …, TK, 则他们的身高满足 T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。你的任务是,已知所有 N 位同学的 身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。 【输入文件】输入文件 chorus.in 的第一行是一个整数 N(2 <= N <= 100) ,表示同 学的总数。第一行有 n 个整数,用空格分隔,第 i 个整数 Ti(130 <= Ti <= 230)是 第 i 位同学的身高(厘米) 。 【输出文件】输出文件 chorus.out 包括一行,这一行只包含一个整数,就是最少 需要几位同学出列。 【样例输入】8 186 186 150 200 160 130 197 220

中国计算机学会 2014

【样例输出】 4 算法分析:此题采用动态规划法求解。先分别从左到右求最大上升子序列,从右 到左求最大下降子序列,再枚举中间最高的一个人。算法实现起来也很简单,时 间复杂度 O(N^2)。 我们先考虑如何求最大上升子序列的长度, 设 f1(i)为前 i 个同学的最大上升子 序列长度。若要求 f1(i),必须先求得 f1(1),f1(2),…,f1(i-1),再选择一个最大的 f1(j) (j<i) ,在前 j 个数中的最大上升序后添加 Ti,就可得到前 i 个数的最大上升子序 列 f1(i)。这样就得到状态转移方程: f1(i)=max{f1(j)+1} (j<i,Tj<Ti) 边界条件:f1(1)=1; 设 f2(i)为后面 N-i+1 位排列的最大下降子序列长度, 用同样的方法可以得到状 态转移方程:f2(i)=max{f2(j)+1} (i<j,Tj<Ti);边界值为 f2(N)=1; 有了状态转移方程,程序实现就非常容易了。 源程序: var t,f1,f2:array[1..100]of byte; i,j,n,max:integer; begin assign(input,'chorus.in'); reset(input); readln(n); for i:=1 to n do begin read(t[i]);f1[i]:=1;f2[i]:=1; end;{for} close(input); max:=0; for i:=2 to n do for j:=1 to i-1 do begin if (t[i]>t[j])and(f1[j]>=f1[i]) then f1[i]:=f1[j]+1; {从左到右求最大上升子序 列} if (t[n-i+1]>t[n-j+1])and(f2[n-j+1]>=f2[n-i+1]) then f2[n-i+1]:=f2[n-j+1]+1; {从 右到左求最大下降子序列} end;{for} for i:=1 to n do if max<f1[i]+f2[i] then max:=f1[i]+f2[i]; {枚举中间最高的} assign(output,'chorus.ans'); rewrite(output); writeln(n-max+1); close(output); end. 运用动态规划法求解问题的关键是找出状态转移方程,只要找出了状态转移 方程,问题就解决了一半,剩下的事情就是解决如何把状态转移方程用程序实现。

中国计算机学会 2014

例 2、乘积最大(noip2000tg) 题目大意:在一个长度为 N 的数字串中插入 r 个乘号,将它分成 r+1 个部分, 找出一种分法,使得这 r+1 个部分的乘积最大。 算法分析:此题满足动态规划法的求解标准,我们把它按插入的乘号数来划 分阶段,若插入 K 个乘号,可把问题看做是 K 个阶段的决策问题。设 f[i,k]表示 在前 i 位数中插入 K 个乘号所得的最大值,a[i,j]表示从第 i 位到第 j 位所组成 的自然数。用 f[i,k]存储阶段 K 的每一个状态,可以得状态转移方程: f[i,k]=max{f[j,k-1]*a[j+1,i]}(k<=j<=i) 边界值:f[j,0]=a[1,j] (1<j<=i) 根据状态转移方程,我们就很容易写出动态规划程序: for k:=1 to r do for i:=k+1 to n do for j:=k to I do if f[i,k]<f[j,k-1]*a[j+1,I] then f[i,k]:=f[j,k-1]*a[j+1,i] 源程序(略)。 近年来,涉及动态规划的各种竞赛题越来越多,每一年的 NOIP 都至少有一道 题目需要用动态规划法求解。而应用动态规划法解题是富于技巧性和创造性的, 虽然在前面的求解过程中给出了一个解题的基本模式,但由于动态规划题目出现 的形式多种多样,并且大部分题目表面上看不出与动态规划的直接联系,只有在 充分把握其思想精髓的前提下大胆联想,多做多练才能达到得心应手,灵活运用 的境界。


赞助商链接

2014NOIP(pascal)典型算法设计题集(中国计算机学会出版)

2014 NOIP(pascal)典型算法设计题集 (中国计算机学会出版)第一章第一节 算法的...2014 NOIP 实用算法(中国... 49页 5下载券 2014NOIP信息学奥赛——... 35...

2014 noip 计算机 it

2014 NOIP 算法 快速入门 中国计算机学会中国计算机学会 2014 2014 2014 算法...下面,我们根据全国分区联赛大纲的要求,一起来探讨信息学奥赛中的基本 算法。 ...

信息学奥赛(NOIP)必看经典书目汇总

信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中...《全国信息学奥林匹克联赛培训教程(一) 》 (推荐...6、 《算法竞赛入门经典》 (推荐指数:5 颗星) ...

信息学奥赛(NOIP)必看经典书目汇总

信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中...《全国信息学奥林匹克联赛 培训教程(一)》(推荐...6、《算法竞赛入门经典》(推荐指数:5 颗星) 刘汝佳...

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

中国计算机学会负责组织的全国青少年信息学奥林匹克...简称 NOIP)是全国信息学奥林匹克 竞赛(NOI)系列活动...排序算法(冒泡法、插入排序、合并排序、快速排序) 3...

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

的全国青少年信息学奥林匹克联赛(NOIP)是全国信息学奥林匹克竞赛 (NOI)整个系列...动态规划的思想及基本算法 注:本大纲由中国计算机学会 NOI 科学委员会制定和修订...

信息学奥赛基础知识习题NOIP(答案版)

信息学奥赛——算法入门教... 35页 免费 信息学奥赛辅导教程 230页 免费 信息...请将你认为是正确的答案填在相应的 横线上) 1. 我们把计算机硬件系统和软件...

全国青少年信息学奥林匹克联赛(NOIP)大纲

(NOIP)大纲 )一、总则 由中国计算机学会负责组织的...计算机学会科学委员会全权处理,包括使用、修改和出版...信息学奥赛——算法入门... 35页 免费 信息学奥林...

中国计算机学会关于 NOIP2011复赛报名的流程说明

2011NOIP复赛注意事项 2页 2财富值 NOIP实用算法 33...“中国计算机学会关于 NOIP2011 复赛报名的流程说明”...江苏省青少年信息学奥林匹克竞赛委员会 2011 年 9 ...

信息技术奥赛考试大纲

简称 NOIP)是全国信息学奥林匹克竞赛(NOI)系列活动中的一个 重要组成部分, 旨在...经提交,即表明同意授权中国计算机学会科学委员会全权处理,包括使用、修改 和出版...

更多相关标签