当前位置:首页 >> 学科竞赛 >>

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


中国计算机学会 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 都至少有一道 题目需要用动态规划法求解。而应用动态规划法解题是富于技巧性和创造性的, 虽然在前面的求解过程中给出了一个解题的基本模式,但由于动态规划题目出现 的形式多种多样,并且大部分题目表面上看不出与动态规划的直接联系,只有在 充分把握其思想精髓的前提下大胆联想,多做多练才能达到得心应手,灵活运用 的境界。


相关文章:
2014 NOIP信息学奥赛——算法快速入门教程(中国计算机学会出版)
2014 NOIP信息学奥赛——算法快速入门教程(中国计算机学会出版)_学科竞赛_高中教育...33 中国计算机学会 2014 算法基础篇学习过程序设计的人对算法这个词并不陌生,从...
2014_NOIP算法快速入门教程(中国计算机学会编)
2014_NOIP算法快速入门教程(中国计算机学会编)_计算机软件及应用_IT/计算机_专业...'); {若 x 两端的函数值异号或 x-0.005 刚好 3 2 信息学奥赛中的基本...
2014 NOIP 实用算法(中国计算机学会编)
2014 NOIP 实用算法(中国计算机学会编)_学科竞赛_高中教育_教育专区。权威机构编写...专题推荐 2014 NOIP信息学奥赛——... 2014 NOIP算法快速入门教......
信息学奥赛——算法入门教程
信息学奥赛——算法入门教程_其它语言学习_外语学习_...由于当今计算机硬件技术 发展很快,程序所能支配的自由...2014NOIP信息学奥赛——... 35页 1下载券 2014...
2014NOIP(pascal)典型算法设计题集(中国计算机学会出版)
2014NOIP(pascal)典型算法设计题集(中国计算机学会出版)_IT认证_资格考试/认证_...信息学奥赛——算法入门... 35页 免费©2014 Baidu 使用百度前必读 | 文库...
2014 noip 计算机 it
2014 NOIP 算法 快速入门 中国计算机学会中国计算机学会 2014 2014 2014 算法...下面,我们根据全国分区联赛大纲的要求,一起来探讨信息学奥赛中的基本 算法。 ...
信息学奥赛(NOIP)必看经典书目汇总
信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中...《全国信息学奥林匹克联赛培训教程(一) 》 (推荐...6、 《算法竞赛入门经典》 (推荐指数:5 颗星) ...
信息学奥赛基础知识习题NOIP(答案版)
信息学奥赛——算法入门教... 35页 免费 信息学奥赛辅导教程 230页 免费 信息...请将你认为是正确的答案填在相应的 横线上) 1. 我们把计算机硬件系统和软件...
edu_ecologychuanke1477647171
本课程是针对NOI竞赛的C++速成课,是为NOIP初学零基础学生提供的一个快速入门课。...学习目标 信息学奥赛基础语言及竞赛训练。 讲师信息 王凯伦 王老师:计算机专业硕...
更多相关标签:
信息学奥赛noip官网 | 象棋入门 金盾出版社 | 金盾出版社 围棋入门 | 中国计算机学会 | 计算机学会 | 福建省计算机学会 | 计算机学会推荐期刊 | 广东省计算机学会 |