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

信息学奥赛


信息学奥赛辅导教程
第3章 算法与程序设计模块
3.1 算 法

算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。 常用的算法:列举了穷举搜索、递归、回溯、递推、模拟、分治、贪心、深度优先搜索、广度优先搜索等 、 几种较为常用的算法,没有做过多的描述,一旦给出具体描述,容易使内容加深,产生严重学科取

向的引导, 符合教育部普通高中课程方案的特点,对于这些必需的方法和思想,关键不在于学生能不能,而在于教师是否 想到,是否有过关注,引发学生对系统方法和思想的思考,重视建立编程思想,强化编程习惯的培养。

3.1.1 算法的 5 个重要特性
1.有穷性 有穷性:一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束,且每一步都可在有穷时 有穷性 间内完成。 2.确定性 确定性:算法中每一条指令必须有确切的含义,不会产生二义性。并且在任何条件下,算法只有唯一 确定性 的一条执行路径。 3.可行性 可行性:一个算法是能行的。即算法中描述的操作是执行有限次运算来实现的。 可行性 4.输入 输入:一个算法有零个或多个输入。 输入 5.输出 输出:一个算法有一个或多个输出。 输出

3.1.2 算法设计的要求
通常设计一个“好”的算法,应考虑达到以下目标。 1.正确性 正确性:算法应当满足具体问题的需求。 正确性 2.可读性 可读性:算法主要是为了人的阅读与交流,其次才是机器执行。可读性好有助于人对算法的理解。 可读性 3.健壮性 健壮性:当输入数据非法时,算法也能适当地做出反应或进行处理,而不会产生莫明其妙的输出结果。 健壮性 4.效率与低存储量需求。 效率与低存储量需求。 效率与低存储量需求 效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决,执行时间短的算法效率高。低存储 量需求指算法执行过程中所需要的最大存储空间。

第3章

算法与程序设计模块

3.1.3 算法分析
算法分析的任务是对设计出的每一个具体的算法,利用数学工具,讨论各种复杂度,以探讨某种具体算法 适用于哪类问题,或某类问题宜采用哪种算法。 算法的复杂度分时间复杂度和空间复杂度。 时间复杂度是在运行算法时所耗费的时间为 f(n) (即 n 的函数) 。 空间复杂度是实现算法所占用的空间为 g(n)(也为 n 的函数)。称 O(f(n))和 O(g(n))为该算法的复杂度。

3.1.4 程序设计
1.程序 程序是对所要解决的问题的各个对象和处理规则的描述,或者说是数据结构和算法的描述,因此有人说, 数据结构+算法=程序。 2.程序设计 程序设计就是设计、编制和调试程序的过程。程序设计是一门技术,需要相应的理论、技术、方法和工具 来支持。就程序设计方法和技术的发展而言,主要经过了结构化程序设计和面向对象的程序设计两个阶段。 除了好的程序设计方法和技术之外,程序设计风格也很重要。因为程序设计风格会深刻影响软件的质量和 可维护性,良好的程序设计风格可以使程序结构清晰合理,使程序代码便于维护。因此,程序设计风格对保证 程序的质量很重要。 一般来讲,程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路 程序设计风格是指编写程序时所表现出的特点、 程序设计风格是指编写程序时所表现出的特点 习惯和逻辑思路。程序是由人来编写的,为了 测试和维护程序,往往还要阅读和跟踪程序,因此程序设计的风格总体而言应该强调简单和清晰,必须可以理 解。可以认为,著名的“清晰第一,效率第二”的论点已成为当今主导的程序设计风格。要形成良好的程序设 计风格,主要应注重源程序文档化。 (1)符号名的命名:符号名的命名应具有一定的实际含义,以便于对程序的功能进行理解。 (2)程序注释:正确的注释能够帮助读者理解程序。 3.结构化程序设计 结构化程序设计方法是程序设计的先进方法和工具。采用结构化程序设计方法编写程序,可使程序结构良 好、易读、易理解、易维护。结构化程序语言仅使用顺序、选择和循环 3 种基本控制结构就足以表达出各种其 他形式结构的程序设计方法。 总之,遵循结构化程序的设计原则,按结构化程序设计方法设计出的程序具有明显的优点。其一,程序结 构良好、易读、易理解和易维护;其二,可以提高编程工作的效率,降低软件开发成本。

练习题
(1)算法的时间复杂度是指( )。 A.执行算法程序所需要的时间 B.算法程序的长度 C.算法执行过程中所需要的基本运算次数 D.算法程序中的指令条数 【解析】所谓算法的时间复杂度,是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本 运算次数来度量。 【答案】C (2)算法的空间复杂度是指( )。 A.算法程序的长度 B.算法程序中的指令条数 C.算法程序所占的存储空间 D.算法执行过程中所需要的存储空间 【解析】空间复杂度是指执行算法所需要的存储空间。算法所占用的存储空间包括算法程序所占的空间、 输入初始数据所占的存储空间以及算法执行过程中所需要的额外空间。 【答案】D
·101·

信息技术与信息学竞赛

(3)算法指的是( )。 A.计算机程序 B.解决问题的计算方法 C.排序算法 D.解决问题的有限运算序列 【解析】所谓算法是指解题方案的准确而完整的描述。对于一个问题,如果可以通过一个计算机程序在有 限的存储空间内运行有限长的时间而得到正确的结果,则称这个问题是算法可解的。但算法不等于程序,也不 等于计算方法。 【答案】D (4)算法能正确地实现预定功能的特性称为算法的( )。 A.正确性 B.易读性 C.健壮性 D.高效率 【解析】针对实际问题设计的算法,人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的 计算工具上执行的,因此算法在执行过程中往往要受到计算工具的限制,使执行结果产生偏差。算法与计算公 式是有差别的,在设计一个算法时,必须要考虑它的可行性,否则将得不到满意的结果。 【答案】A (5)递归算法一般需要利用( )来实现。 A.栈 B.队列 C.循环链表 D.双向链表 【答案】A

3.2

穷举搜索法

有一些问题一时难以找到规律或者公式,或者根本没有规律、公式。这时可以利用计算机高速运算的特点, 使用穷举来解决。穷举搜索法是穷举所有可能情形,并从中找出符合要求的解决。穷举搜索法所有可能情形, 最直观的是联系循环的算法。 例 1 找出 n 个自然数(1,2,3,…,n)中 r 个数的组合。例如,当 n=5,r=3 时,所有组 合为: 5 5 3 5 4 2 5 4 1 5 3 2 5 3 1 5 2 1 4 3 2 4 3 1 4 2 1 3 2 1 total=10 {组合的总数} [程序]
program zuhe11; const n=5; var i,j,k,t:integer; begin t:=0; for i:=n downto 1 do for j:=n downto 1 do for k:=n downto 1 do if (i<>j) and (i<>k) and (i>j) and (j>k) then begin t:=t+1;writeln(i:3,j:3,k:3); end; writeln('total=',t); end.

·102·

第3章

算法与程序设计模块

这个程序,穷举了所有可能情形,从中选出符合条件的解,很多情况下穷举搜索法还是常用的。 例 2 算 24 点(poi24.pas)。 【题目描述】 几十年前全世界就流行一种数字游戏,至今仍有人乐此不疲。在中国我们把这种游戏称为“算 24 点”。 您作为游戏者将得到 4 个 1~9 之间的自然数作为操作数,而您的任务是对这 4 个操作数进行适当的算术运算, 要求运算结果等于 24。 您可以使用的运算只有:+,-,×,/,您还可以使用()来改变运算顺序。注意:所有的中间结果须是整 数,所以一些除法运算是不允许的(例如,(2×2)/4 是合法的,2×(2/4)是不合法的)。下面我们给出一个游戏 的具体例子:若给出的 4 个操作数是:1、2、3、7,则一种可能的解答是 1+2+3×7=24。 【输入】 只有一行,四个 1~9 之间的自然数。 【输出】 如果有解的话,只要输出一个解,输出的是 3 行数据,分别表示运算的步骤。其中第一行是输入的两个数 和一个运算符和运算后的结果,第二行是第一行的结果和一个输入的数据、运算符、运算后的结果;第三行是 第二行的结果和输入的一个数、运算符和“=24”。如果两个操作数有大小的话则先输出大的。如果没有解, 则输出“no answer!” 【样例】
poi24.in 1 2 3 7 poi24.out 2+1=3 7×3=21 21+3=24

【算法分析】 计算 24 点主要应用四种运算。开始状态有四个操作数,一个运算符对应两个操作数,所以一开始选择两 个操作数分别对四个操作符进行循环检测,每一次运算后产生了新的数,两个数运算变成一个数,整体是少了 一个操作数,所以四个数最终是三次运算。由于操作的层数比较少(只有三层),所以可以用回溯的算法来进 行检测,当找到一个解时便结束查找。如果所有的情况都找过后仍然没有,则输出无解的信息。 [程序]
program poi24; {point24} type arr=array [1..4] of integer; var i,result,n,len:integer; d:arr; r:array [1..3,1..4] of integer; infile,outfile:text; procedure print; var i,j:integer; begin assign(outfile,'poi24.out'); rewrite(outfile); for i:=1 to 3 do begin for j:=1 to 3 do if j<>2 then write(outfile,r[i,j]) else case r[i,j] of 1:write(outfile,'+'); 2:write(outfile,'-'); 3:write(outfile,'*'); 4:write(outfile,'/') end; writeln(outfile,'=',r[i,4]) end;

·103·

信息技术与信息学竞赛 close(outfile); end; procedure try(k:integer;d:arr); var a,b,i,j,l,t:integer; e:arr; begin if k=1 then if d[1]=24 then begin print;halt end else else begin for i:=1 to k-1 do for j:=i+1 to k do begin a:=d[i]; b:=d[j]; if a<b then begin t:=a;a:=b;b:=t end; t:=0; for l:=1 to k do if (l<>i) and (l<>j) then begin t:=t+1;e[t]:=d[l] end; r[5-k,1]:=a; r[5-k,3]:=b; r[5-k,4]:=-1; for l:=1 to 4 do begin case l of 1:r[5-k,4]:=a+b; 2:r[5-k,4]:=a-b; 3:r[5-k,4]:=a*b; 4:if b<>0 then if a mod b=0 then r[5-k,4]:=a div b end; r[5-k,2]:=l; if r[5-k,4]<>-1 then begin e[t+1]:=r[5-k,4]; try(k-1,e) end end end end; end; begin assign(infile,'poi24.in'); reset(infile); for i:=1 to 4 do read(infile,d[i]); close(infile); try(4,d); assign(outfile,'poi24.out'); rewrite(outfile); writeln(outfile,'no answer!'); close(outfile); end.

练习题
彩虹 7 号(rainbow.pas) X 市是一个重要的军事基地,在这个基地中有一支名为“彩虹 7 号”的特别部队。每个队员都有一个固定 独立的编号 X(1≤X≤215),他们的职责就是完成部队交给他们的任务,每个任务同样都有固定独立的编号 N(1 ≤N≤10)。在执行任务的过程中,为了保证任务的保密性和队员的安全,队员和队员之间的联系将必须由特别 部队所提供的一种保密频段交互设备进行。
·104·

第3章

算法与程序设计模块

每个队员都需要一个身份验证口令进入系统,由于队员所执行的任务都是涉及国家安全或者极高机密的活 动,如果队员使用的口令出现错误,他们将付出无法估计的代价。特别部队的队员都是层层筛选的精英人才, 所以不希望发生这样的事情。因此队员必须牢记口令的设置方法。 口令 S 的内容满足:SN=X。显然,S 有可能也很有可能是一个无理数,所以限定 S 为一个实数,它包含整 数部分和小数部分,不包含小数点(即 0.1 将视作 01)。口令的长度 M(10≤M≤50),将根据任务的难度 而有所不同。 编程任务:给定 X,N,M。计算口令的内容 S。 输入(rainbow .in):文件输入,文件有且仅有一行包含 3 个整型数 X,N,M,每个数之间以一个空格符 隔开。 输出(rainbow.out):文件输出,文件有且仅有一行,为 S 的结果。 样例输入:2 2 10 样例输出:1414213652 注意:口令的最后一位请使用去尾法保留, 不要使用四舍五入法保留。文件请不要包含多余的空格和换行。 注意

3.3



归 法

递归作为一种强有力的数学和算法描述工具在 Pascal 语言中被广泛使用。一个函数、过程、概念或数学结 构,如果在其定义或说明内部又直接或间接地出现有定义本身的引用(在过程或自定义函数中,又包含自己调 用自己),则称它们是递归的或者是递归定义的。 一个递归算法仅使用少量的程序编码就可描述出解题所需要的多次重复计算而不需要设计循环结构。使用 递归求解问题,通常可以将一个比较大的问题层层转化为一个与原问题相类似的规模较小的问题来求解,进而 最终导致原问题的解决。 例如:n!的定义,我们知道,在数学中 n!一般定义为: 1 若 n=0 n!= n×(n-1)! 若 n>0 在 n>0 的公式中,又包含了(n-1)!,这就是递归定义。 利用递归方法,可以用有限的语句来定义对象的无限集合。但在递归定义中,应该至少有一条是 非递归的,即初始定义。如上面例子中的第一条,否则就变成了循环定义,产生逻辑性错误。 n !的递归定义的程序:
program find_n; var n:integer; t:longint; procedure find(n:integer); begin if n=0 then t:=1 else begin find(n-1); t:=t*n end; end; begin write('n='); readln(n); find(n); writeln(n,'!=',t) end.

递归调用(n 进栈)达到结束条件时(n=0,t 赋初值 1)就停止调用开始返回,再把保存的值取

·105·

信息技术与信息学竞赛

出(n 出栈),使 n 恢复原来的值,并计算 t,返回主程序,输出结果 t。 3!递归是如何实现的? (1)设 n=3,开始调用过程 find,称为第零层调用。 (2)由于公式 3!=3 × 2!,必须先求 2!,即程序中的 f(n-1),此时系统自动先保存 n 的原值 3,再 设 n=2,进入第一层递归调用。 (3)因为 2!=2 × 1!,所以系统又保存 2,并设 n=1,进入第 2 层调用。 (4)因为 1!=1 × 0!,所以保存 1,并设 n=0,进入第 3 层调用。 (5)因为 n=0,终止调用,t 赋值 1,返回 4 的入口点。 (6)取出执行 4 时保存的 1,求出 t=1 × t=1,返回 3 的入口点。 (7)取出执行 3 时保存的 2,求出 t=2 × t=2,返回 2 的入口点。 (8)取出执行 2 时保存的 3,求出 t=3 × t=6,返回 1 的入口点。 (9)返回主程序,输出结果:t=6。 从上面分析的过程看到,由于递归调用,需用同一变量名 n,但值不同,所以在调用前必须先把 n 的原值保存,再赋以新值,然后进入调用。调用结束后,再把保存的值取出,使 n 恢复原来的值。 在过程中 find 中又包含 find(n-1),即又调用了它自己,这就是递归调用。包含有递归调用的算法,就 叫做递归算法。 递归调用会产生无终止运算的可能性,因此必须在适当时候终止递归调用,即在程序中必须要有 终止条件。上面程序中,过程 find 的第一条语句就是终止条件。一般地,根据递归定义设计的递归算 法中,非递归的初始定义,就用作程序中的终止 条件。 实践证明,不是所有问题都可以用递归的方法处理,用递归算法编写的程序也不一定是好程序。 可以看出,执行递归的过程既浪费时间又费存储空间,因此有的语言系统,禁止使用递归,由于计算 机存储容量的限制,编译系统也不允许递归。但因递归特别符合人们的思维习惯,递归算法的设计也 要比非递归算法设计容易,所以当问题是递归定义,尤其是当涉及的数据结构是递归定义的时候,使 用递归算法特别合适。 应用递归算法能够求解的问题一般具有两个特点: ①存在某个特定条件,在此条件下,可得到指定的解,即递归在终止状态。 ②对任意给定的条件,有明确的定义规则,可以产生新的状态并将最终导出终止状态,即存在导 致问题求解的递归步骤。 递归是用栈来实现的。不过,递归恐怕不像想象得这么简单。首先,它体现了一个数学思想:化归,即把 一个问题转化成另一个的方法。递归比较特殊,它是转化成性质相似,但规模更小的问题。 例 3 阅读程序 NOIp2001_G。
program gao7_1; function ack(m,n:integer):integer; begin if m=0 then ack:=n+1 else if n=0 then ack:=ack(m-1,1)else ack:=ack(m-1,ack(m,n-1)) end; begin writeln(ack(3,4)); readln; end.

分析: 这个程序我们可以用下面的函数表示。在解题时,一般都是用递归的方法去实现的,而递归方法将会计算 五千多步,在竞赛时这种方法是不可用的,而递归往往可以用递推去实现,因此,我们在教学过程中就讲解了 该函数的递推过程,现将推导过程表示如下: (1)我们在递归过程中发现该函数总是要调用到 M=0,M=1 及 M=2 的情况,因此,我们就考虑要推导 ACK(3,N)必须首先推导 ACK(0,N),ACK(1,N)以及 ACK(2,N)的情况。 (2)ACK(0,N)可以由函数直接得到,公式为 ACK(0,N)=N+1

·106·

第3章

算法与程序设计模块

(3)ACK(1,0)=ACK(0,1)=1+1=0+2 ACK(1,1)=ACK(0,ACK(1,0))=ACK(0,1+1)=1+1+1=1+2 ACK(1,2)=ACK(0,ACK(1,1))=ACK(0,1+2)=1+1+2=2+2 …… 因此,我们可以联想到 ACK(1,N)=N+2。这个公式可以用数学归纳法证明之。(略) 根据上面的方法,我们可以方便地推导出下面一些公式: (4)ACK(2,0)=ACK(1,1)=1+2=3(利用 M=1 的公式) ACK(2,1)=ACK(1,ACK(2,0))=ACK(1,1+2)=3+2=5 (利用 M=1 的公式及 ACK(2,0)) ACK(2,2)=ACK(1,ACK(2,1))=ACK(1,5)=5+2=(2+1)*2+1 …… 因此,我们可以联想到 ACK(2,N)=(N+1)*2+1。同样,这个公式可以用数学归纳法证明之。(略) (5)ACK(3,0)=ACK(2,1)=(1+1)*2+1=5(利用 M=2 的公式) ACK(3,1)=ACK(2,ACK(3,0))=ACK(2,5)=((1+1)*2+1+1)*2+1=2^3+2^2+1 ACK(3,2)=ACK(2,ACK(3,1))=ACK(2,13)=(2^3+2^2+1+1)*2+1=2^4+2^3+2^2+1=2^5-3 …… 因此,我们可以联想到 ACK(3,N)=2^(N+3)-3。 例 4 仍以例 1 为例,找 n 个数的 r 个数的组合。 输入:n,r =5,3 输出:5 4 3 5 4 2 5 4 1 5 3 2 5 3 1 5 2 1 4 3 2 4 3 1 4 2 1 3 2 1 total=10 {组合的总数} 分析:所提示的 10 组数。首先固定第一位数(如 5),其后是在另 4 个数中再“组合”2 个数。这就将“5 个数中 3 个数的组合”推到了“4 个数中 2 个数的组合”上去了。第一位数可以是 n,r (如 5,3),n 个数中 r 个数组合递推到 n-1 个数中 r-1 个数有组合,这是一个递归的算法。即:
var i:integer; begin for i:=n downto r begin comb(i-1,r-1); end; end; do {固定 i 的输出位置} {原过程递推到 i-1 个数的 r-1 个数组合}

再考虑打印输出格式。

[程序]
var k,n,r:integer; Produrce comb(n,r:integer); var i,temp:integer; begin for i:=n downto r do if (i<>n)and(k<>r) then

{k 为过程外定义的}

·107·

信息技术与信息学竞赛 begin for temp:=1 to (k-r)*3 do write(' '); {确定 i 的输出位置} end; write(i:3); if i>1 then comb(i-1,r-1); {递推到下一情形} else writeln; end; begin {main} write('n,r=');readln(n,r); if r>n then begin writeln('Input n,r error!'); halt; end; comb(n,r); {调用递归过程} end;

练习题
1.邮票面值设计(postag.pas) 【题目描述】 给定一个信封,最多只允许粘贴 N 张邮票,计算在给定 K(N+k≤40) 种邮票的情况下(假定所有的邮票 数量都足够),如何设计邮票的面值,能得到最大 max ,使得 1-max 之间的每一个邮资值都能得到。 例如,N=3,K=2,如果面值分别为 1 分、4 分,则在 l~6 分之间的每一个邮资值都能得到(当然还有 8 分、9 分和 12 分):如果面值分别为 1 分、3 分,则在 1~7 分之间的每一个邮资值都能得到。可以验证当 N=3, K=2 时,7 分就是可以得到连续的邮资最大值,所以 max=7,面值分别为 l 分、3 分。 【样例输入】 3 2 {输入第一个数 N,第二个数 K,中间用空格间隔} 【样例输出】 13 {输出的第一行面值分别为 l 分、3 分} max=7 {输出的第二连续的邮资最大值} 2.聪明的学生(guess.pas) 【题目描述】 一位教授逻辑学的教授有三名非常善于推理且精于心算的学生 A,B 和 C。有一天,教授给他们 3 人出了一 道题:教授在每个人脑门上贴了一张纸条并告诉他们,每个人的纸条上都写了一个正整数,且某两个数的和等 于第三个。于是,每个学生都能看见贴在另外两个同学头上的整数,但却看不见自己的数。 这时,教授先对学生 A 发问了:“你能猜出自己的数吗?”A 回答:“不能。” 教授又转身问学生 B:“你能猜出自己的数吗?”B 想了想,也回答:“不能。” 教授再问学生 C 同样的问题,C 思考了片刻后,摇了摇头:“不能。” 接着,教授又重新问 A 同样的问题,再问 B 和 C,……,经过若干轮的提问之后,当教授再次询问某人时, 此人突然露出了得意的笑容,把贴在自己头上的那个数准确无误地报了出来。 现在,如果告诉你:教授在第 N 次提问时,轮到回答问题的那个人猜出了贴在自己头上的数是 M,你能推 断出另外两个学生的头上贴的是什么数吗? 【提示】 在没有人猜出自己头上的数之前,大家对教授提问的回答始终都是“不能”;而且除此之外在 A,B,C 之间是没有进行任何信息交流的。也就是说,每个人推断的依据仅仅是另外两个人的头上数,以及大家对教授 的提问所做出的否定回答。 教授总是从学生 A 开始提问的。 你可以假定,这 3 个聪明的学生能够根据已知的条件在最早的轮次猜出自己的数,并且永远都不会猜错。 稍经分析和推理,你将得出以下结论:总是头上贴着最大的那个数的人最先猜出自己头上的数。 【输入文件】

·108·

第3章

算法与程序设计模块

输入文件为 guess.in。 该文件包括若干组测试数据,其中的每一行代表一组测试数据,由两个整数 N 和 M 组成(即在教授第 N 次提问时,轮到回答问题的那个人猜出了贴在自己头上的数是 M)。两个数之间用空格分隔开。最后,由-1 -1 组成的一行标志着输入的数据结束。同时要求,0<N<500; 0<M<30000。 【输出文件】 输出文件为 guess.out。按照输入文件中的顺序依次给出各组数据的结果。 文件中对应每组数据输出的第一行是一个整数 p,是可能情况的总数。接下来的 p 行,每一行包括 3 个数, 分别为贴在 A、B、C 头上的 3 个数。输出时,所有解按照 A 头上的数增序排列;在 A 头上的数相同的情况下, 按照 B 头上的数增序排列。 【样例输入】 5 8 3 2 2 3 -1 -1 【样例输出】 3 2 5 6 1 1 1 2 8 6 8 3 8 2 1 2 3 1

3.4



溯 法

回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标但当探索到某一步时,发现原先选择并不优 或达不到目标,就退回一步重新选择。这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的 点称为“回溯点”。回溯算法是所有搜索算法中最为基本的一种算法,其采用了一种“走不通就掉头”思想作 为其控制结构 例 5 再以例 1 说明,找 n 个数中 r 个数的组合。 分析:将自然数排列在数组 A 中。 A[1] 5 5 … 3 2 1 排数时从 A[1]到 A[2]再到 A[3],后一个至少比前一个数小 1,并且应满足 ri+A[ri]>r。若 ri+A[ri]≤r 就要 回溯,该关系就是回溯条件。为直观起见,当输出一组组合数后,若最后一位为 1,也应作一次回溯(若不回, 便由上述回溯条件处理)。 [程序]
program zuhe3; type tp=array[1..100] of integer; var n,r:integer; procedure comb2(n,r:integer;a:tp); var i,ri:integer;

A[2] 4 4

A[3] 3 2

·109·

信息技术与信息学竞赛 begin ri:=1;a[1]:=n; repeat if ri<>r then {没有搜索到底} if ri+a[ri]>r then {判断是否回溯} begin a[ri+1]:=a[ri]-1; ri:=ri+1; {向前搜索} end; else begin ri:=ri-1; a[ri]:=a[ri]-1; end; {回溯} else begin for j:=1 to r do write(a[j]:3); writeln; {输出组合数} if a[r]=1 then {是否回溯} begin ri:=ri-1; a[ri]:=a[ri]-1; end; {回溯} else a[ri]:=a[ri]-1; {递推到下一个数} end; until a[1]<>r-1; end; begin write('n,r='); readln(n,r); if r>n then begin writeln('Input n,r error!'); halt; end; comb2(n,r); end.

练习题
1.马拦过河卒(knight.pas) 【题目描述】 棋盘上 A 点有一个过河卒,需要走到目标 B 点。卒行走的规则:可以向下、或者向右。同时,在棋盘上 C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示,A 点(0, 0)、B 点(n, m)(n, m 为不超过 15 的整数),同样马的位置坐标是需要给 出的。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步 马走一步。 【输入】 一行四个数据,分别表示 B 点坐标和马的坐标。 【输出】 一个数据,表示所有的路径条数。 【样例】 knight.in 6633 2.走迷宫(maze.pas) 【题目描述】 有一个 m×n 格的迷宫(表示有 m 行、n 列),其中有可走的也有不可走的,如果用 1 表示可以走,0 表示 不可以走,文件读入这 m×n 个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的,分别表示
·110·

knight.out 6

第3章

算法与程序设计模块

这个点的行号和列号)。现在要你编程找出所有可行的道路,要求所走的路中没有重复的点,走时只能是上下 左右四个方向。如果一条路都不可行,则输出相应信息(用-l 表示无路)。 【输入】 第一行是两个数 m,n(1<m,n<15),接下来是 m 行 n 列由 1 和 0 组成的数据,最后两行是起始点和结束 点。 【输出】 所有可行的路径,描述一个点时用(x,y)的形式,除开始点外,其他的都要用“→”表示方向。如果没有 一条可行的路则输出-1。 【样例输入】 56 100101 111111 001110 111110 111011 11 56 【样例输出】 (1,2)→(2,1)→(2,2)→(2,3)→(2,4)→(2,5)→(3,5)→(3,4)→(3,3)→(4,3)→(4,4)→(4,5)→(5,5) →(5,6) (1,1)→(2,1)→(2,2)→(2,3)→(2,4)→(2,5)→(3,5)→(3,4)→(4,4)→(4,5)→(5,5)→(5,6) (1,1)→(2,1)→(2,2)→(2,3)→(2,4)→(2,5)→(3,5)→(4,5)→(5,5)→(5,6) (1,1)→(2,1)→(2,2)→(2,3)→(2,4)→(3,4)→(3,3)→(4,3)→(4,4)→(4,5)→(5,5)→(5,6) (1,1)→(2,1)→(2,2)→(2,3)→(2,4)→(3,4)→(3,5)→(4,5)→(5,5)→(5,6) (1,1)→(2,1)→(2,2)→(2,3)→(2,4)→(3,4)→(4,4)→(4,5)→(5,5)→(5,6) (1,1)→(2,1)→(2,2)→(2,3)→(3,3)→(3,4)→(2,4)→(2,5)→(3,5)→(4,5)→(5,5)→(5,6) (1,1)→(2,1)→(2,2)→(2,3)→(3,3)→(3,4)→(3,5)→(4,5)→(5,5)→(5,6) (1,1)→(2,1)→(2,2)→(2,3)→(3,3)→(3,4)→(4,4)→(4,5)→(5,5)→(5,6) (1,1)→(2,1)→(2,2)→(2,3)→(3,3)→(4,3)→(4,4)→(3,4)→(2,4)→(2,5)→(3,5)→(4,5)→(5,5)→(5,6) (1,1)→(2,1)→(2,2)→(2,3)→(3,3)→(4,3)→(4,4)→(3,4)→(3,5)→(4,5)→(5,5)→(5,6) (1,1)→(2,1)→(2,2)→(2,3)→(3,3)→(4,3)→(4,4)→(4,5)→(5,5)→(5,6) 3.组合的输出(track.pas) 【题目描述】 排列与组合是常用的数学方法,其中组合就是从 n 个元素中抽出 r 个元素(不分顺序且 r≤n),我们可以 简单地将 n 个元素理解为自然数 1,2,…,n,从中任取 r 个数。现要求你不用递归的方法输出所有组合。 例如:n=5,r=3,所有组合为: l 2 3;l 2 4;1 2 5;l 3 4;l 3 5;1 4 5;2 3 4;2 3 5;2 4 5;3 4 5。 【输入】 一行两个自然数 n、r(1<n<21,1≤r≤n)。 【输出】 所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列,每个元素占 3 个字符的位置,所有 的组合也按字典顺序。 【样例输入】 53 【样例输出】 1 1 2 3 2 4
·111·

信息技术与信息学竞赛

1 1 1 1 2 2 2 3

2 3 3 4 3 3 4 4

5 4 5 5 4 5 5 5

3.5





递推是迭代算法中一种用若干步可重复的简单运算来描述复杂数学问题的方法,以便于计算机进行处理。 它与递推关系的思想完全一致,由边界条件开始往后逐个推算,在一般情况下,效率较高,编程也非常的方便。 但是,我们一般只需要求递推关系的第 n 项,而边界条件与第 n 项前面之间的若干项的信息是我们不需要的, 如果采用递推的方法来求解的话,第 n 项之前的每一项都必须计算出来,最后才能得到所需要的第 n 项的值。 这是递推无法避免的,从而在一定程度上影响了程序的效率。当然在大多数情况下,采用递推的方法还是可行 的,在竞赛中,使用递推的方法编程,通常会在时限内出解。当然,更好的求解方法还有母函数法、迭代归纳 法等。 例 1 青蛙过河(frog.pas)。 【题目描述】 有一条河,左边一个石墩(A 区)上有编号为 1,2,3,4,…,n 的 n 只青蛙,河中有 k 个荷叶(C 区), 还有 h 个石墩(D 区),右边有一个石墩(B 区),如图 3-1 所示。n 只青蛙要过河(从左岸石墩 A 到右岸石 墩 B),规则为:
荷叶 C 左岸石礅 A k 个荷叶

右岸石礅 B

河心石礅 D h 个石礅

图 3-1

青蛙过河示意图

(1)石墩上可以承受任意多只青蛙,荷叶只能承受一只青蛙(不论大小)。 (2)青蛙可以:A→B(表示可以从 A 跳到 B,下同),A→C,A→D,C→B,D→B,D→C,C→D。 (3)当一个石墩上有多只青蛙时,则上面的青蛙只能跳到比它大 1 号的青蛙上面。 你的任务是对于给出的 h、k,计算并输出最多能有多少只青蛙可以根据以上规则顺利 过河? 【样例输入】 】 23 {河中间有 2 个石礅,3 个荷叶} 【样例输出】 】

·112·

第3章

算法与程序设计模块

16 {最多有 16 只青蛙可以按照规则过河} 【算法分析】 从具体到一般,推导过程如下: f(0,0)=1; f(0,k)=k+1; {如 k=3 时,有 4 只青蛙可以过河} f(1,k)=2(k+1); ` {递推思想} …… 以此类推:f(2,k)=(2×(k+1))×2=22(k+1); …… 结论为:f(h,k)=2h(k+1) [程序]
program frog(input,output); var h,k,i,s:integer; begin assign(input,'frog.in'); assign(output,'frog.out'); reset(input); rewrite(output); readln(h,k); s:=k+1; for i:=1 to h do s:=s*2; writeln(s); close(input);close(output) end.

例 2 排序集合(sort.pas)。 【题目描述】 对于集合 N={1,2,…,n}的子集,定义一个称之为“小于”的关系:设 S1={X1,X2,…,Xi},(X1<X2<…< (Y (0≤k≤min(i,j)),使得 X1=Y1,…,Xk=Yk, Xi),S2={Y1, Y2, …,Yj}, 1<Y2<…<Yj),如果存在一个 k, 且 k=i 或 X(k+1) <Y(k+1),则称 S1“小于”S2。 你的任务是,对于任意的 n(n≤31)及 k(k<2n),求出第 k 小的子集。 【输入】 输入文件仅一行,包含两个用空格隔开的自然数,n 和 k。 【输出】 输出文件仅一行,使该子集的元素,由小到大排列。空集输出 0。 【样例输入】 34 【样例输出】 123 【算法分析】 我们知道,n 个元素构成的集合有 2n 种情况。本题的意思是:把这些集合按照某种规则排序,然后输入 k, 输出第 k 个集合。所以排序的规则是本题的关键,其实很简单,当 n=3 时,8 个集合排序如下:{ }<{1}<{l,2} <{l,2,3}<{1,3}<{2}<{2,3}<{3},你发现规律了吗?具体算法为:先推出第 k 小的一个子集的第一个数宇是 多少,第一个数字确定了之后,再推出第二个数字,从第一个数字加 1 一直计算累加集合个数,直到得到不超 过 k 的最大的那个数字,就是第二位数字,这样一直递推,推到最后一个。注意:终止条件是有了 n 个数字或 者第 i 个数字为空,这时递推终止,输出最后的结果。 [程序]
program sort(input,output); type arr=array[0..31] of longint;

·113·

信息技术与信息学竞赛 var a:arr; n,i,j,k:longint; begin assign(input,'sort.in'); assign(output,'sort.out'); reset(input); rewrite(output); readln(n,k); fillchar(a,sizeof(a),0); a[n]:=1; a[0]:=1; for i:=n-1 downto 1 do {a[i]=2i-n} a[i]:=a[i+1]*2; i:=0; j:=1; while k>1 do {以下为一位一位推出数字} begin while (i<=n) and (k>a[i]) do begin dec(k,a[i]); inc(i) end; if j<>1 then write(' '); inc(j); write(i); a[i]:=1 end; if i=0 then writeln(0);{判空集} close(input);close(output) end.

例 3 诸侯安置(empire.pas)。 【题目描述】 很久以前,有一个强大的帝国,它的国土成正方形状,如图 3-2 所示。

图 3-2

诸侯安置示意图(原图)

这个国家有若干诸侯。 由于这些诸侯都曾立下赫赫战功, 国王准备给他们每人一块封地 (正方形中的一格) 。 但是,这些诸侯又非常好战,当两个诸侯位于同一行或同一列时,他们就会开战。如图 3-3 为 n=3 时的国土, 阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击,第三幅则不可以。

(1) 图 3-3

(2) 诸侯安置示意图

(3)

致使国家动荡不安国王也不愿意看到他的诸侯们互相开战, 因此, 他希望通过合理地安排诸侯所处的位置, 使他们两两之间都不能攻击。

·114·

第3章

算法与程序设计模块

现在,给出正方形的边长 n,以及需要封地的诸侯数量 k,要求你求出所有可能的安置方案数。(n≤l00,k ≤2n2-2n+1)。由于方案数可能很多,你只需要输出方案数除以 504 的余数即可。 【输入】 仅一行,两个整数 n 和 k,中间用一空格隔开。 【输出】 一个整数,表示方案数除以 504 的余数。 【样例输入】 22 【样例输出】 4 【样例说明】 四种安置方案如图 3-4 所示。 注意:镜面和旋转的情况属于不同的方案。 注意

(1)

(2)

(3) 图 3-4 安置方案

(4)

【算法分析】 重新描述一下问题,其实就是在一个边长为 2n-1 的正菱形(如图 3-2 为 n=3 的情形)上摆放 k 个棋子,使 得任意两个棋子都不在同一行、同一列。试问:这样的摆法共有多少种? 看到这道题目,我们就会立即想起一道经典的老题目:n 皇后问题。这道题目与 n 皇后问题非常相似。但 有两个不同点:一是 n 皇后问题可以斜着攻击对方棋子,而本题不能;二是 n 皇后问题是在 n,n 的正方形棋盘 上面放置 k 个皇后,而本题却是在一个正菱形上摆放。我们试着先将 n 皇后变为不可斜攻的,再作思考,如果 不能够斜着攻击,n 皇后的公式是:(C(k,n))2×k!。但是本题不是一个正方形,所以这个公式对本题好像没有任 何帮助。看来只能够从另外一个角度思考问题了。 首先,想到在 2n-1 列中任意取出 k 列进行具体分析,这样一来问题就转化成:有一个长为 k 的数列(无 重复元素),每一个数在一个不定的区间[a,b]当中,第 i 个数一定在区间[ai,bi]之间,求这样的数列有多少种? 如果就是这个问题,那么比较难解决,但若把这个数列放在本题中,就比较简单。因为题目中任意两个区间都 是一种包含关系。可以先把区间按照长度排一下序,就可以看出来,再用乘法原理进行求解即可。但是,n 最 多可到 100,k 最多可到 50,穷举要进行 C(50,100)种方案!显然无法在规定的时间内出解!那么怎么办呢?再 继续分析一下问题发现,里面有重叠子问题。如果一个列作为最后一列,且这一列以及前面所有列共放置 p 个 诸侯,设有 q 种情况,那么这一列后面的所有列共放置 p+1 个棋子的方案数都要用到 q,从而引用乘法原理。 而且在穷举过程中,这一个工作做了许多遍,所以干脆用 递推。递推前, 先把图形转化为类似图 3-5 的形式(即列排序)。 设 f[i,j]表示以第 i 列为最后一列, 放置 j 个棋子的总方 案数, 得出公式:

f [i, j ] = ∑ f [i ? k , j ? 1] * (i ? j + 1)
k =1

i? j

注意:当 k≥2n-1 时,问题无解。 注意 [程序]
var i,j,k,n,l,s:longint; f:array[1..200,1..200] of longint; function make(p:longint):longint; begin if odd(p) then make:=p else make:=p-1; end; begin assign(input,'empire.in');reset(input); 图 3-5 图形转化

·115·

信息技术与信息学竞赛 assign(output,'empire.out');rewrite(output); readln(n,k); if k=0 then begin writeln(1);close(output);halt end; if k>=2×n-1 then begin writeln(0); close(output);halt; end; for i:=1 to 2×n-1 do if odd(i) then f[i,1]:=i else f[i,1]:=i-1; for i:=1 to 2×n-1 do for j:=2 to i do for l:=1 to i-j+1 do f[i,j]:=(f[i,j]+f[i-l,j-1] ×(make(i)-j+1)) mod 504; i:=2×n-1; if k=1 then begin writeln((i×(i+1) div 2-i div 2) mod 504); close(output);halt end else for i:=k to 2×n-1 do inc(s,f[i,k]); writeln(s mod 504); close(input); close(output); end.

练习题
行家的预算(travel.pas) 【题目描述】 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市 之间的距离 D1、汽车油箱的容量 C(以升为单位)。每升汽油能行驶的距离 D2、出发点每升汽油价格 P 和沿 途油站数 N(N 可以为零),油站 i 离出发点的距离 Di、每升汽油价格 Pi(i=l,2,…N)(计算结果四舍五入至小 数点后两位)。如果无法到达目的地,则输出“no solution”。 【输入】 第一行,第一个数两个城市之间的距离 D2,第二个数汽车油箱的容量 C,第三个数每升汽油能行驶的距离 D2,第四个数出发点每升汽油价格 P,第五个数沿途油站数 N。 从第二行开始,每行有两个数,第一个数为油站 i 离出发点的距离 Di,第二个数为每升汽油价格 Pi,中间 用空格间隔。 【样例输入】 275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2 【样例输出】 26.95(该数据表示最小费用) 【算法分析】 看到题目后,很容易想到递推。事实上,要用的油是确定的(D1/D2),价钱最便宜的油的站 Q 的油显然 应该多买,到达 Q 这个油站时汽车剩油不为 0 的方案一定不是最优的。这是因为,如果剩下 P 升油,显然不如 当初少买 P 升,改在 Q 这里买 P 升划算!(Q 最便宜嘛!) 每次都假装装满油,用的时候先用便宜的,因为把贵的留在后面“反悔”!这样计算费用时只考虑真正使 用的。可以用优先队列(用堆来实现)来进行替换和使用油。也可以模拟但效率不高。

3.6

模拟搜索(最原始的方法)

·116·

第3章

算法与程序设计模块

模拟题。按常规思想:逐步地模拟,直至又回到初始状态时为止。但这样全部模拟基本上无法在规定的时 间内出解,必须做一些改进。模拟题并不需要太多的算法知识,主要考察选手的数据结构的应用以及编程能力。 例 1 津津的储蓄计划(save.pas)。 【题目描述】 津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 300 元钱,津津会预算这个月的花销,并且总 能做到实际花销和预算的相同。 为了让津津学习如何储蓄, 妈妈提出, 津津可以随时把整百的钱存在她那里, 到了年末她会加上 20%利息、 连本带息还给津津。因此,津津制定了一个储蓄计划:每个月的月初,在得到妈妈给的零花钱后,如果她预计 到这个月的月末手中还会有多于 100 元或恰好 100 元,她就会把整百的钱存在妈妈那里,剩余的钱留在自己手 中。 例如,11 月初津津手中还有 83 元,妈妈给了津津 300 元。津津预计 11 月的花销是 180 元,那么她就会在 妈妈那里存 200 元,自己留下 183 元。到了 11 月末,津津手中会剩下 3 元钱。 津津发现这个储蓄计划的主要风险是,存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初, 津津手中的钱加上这个月妈妈给的钱,不够这个月的原定预算。如果出现这种情况,津津将不得不在这个月省 吃俭用,压缩预算。 现在请你根据 2004 年 1 月到 12 月每个月津津的预算,判断会不会出现这种情况。如果不会,计算到 2004 年年末,妈妈将津津平常存在她那里的钱加上 20%的利息,一并还给津津之后,津津手中会有多少钱。 【输入】 输入文件 save.in 包括 12 行数据,每行包含一个小于 350 的非负整数,分别表示 1 月到 12 月津津的预算。 【输出】 输出文件 save.out 包括一行,这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情 况,输出-X,X 表示出现这种情况的第一个月;否则输出到 2004 年年末津津手中会有多少钱。 【样例输入 1】 290 230 280 200 300 170 340 50 90 80 200 60 【样例输出 1】 -7 【样例输入 2】 290 230 280 200 300 170 330 50 90
·117·

信息技术与信息学竞赛

80 200 60 【样例输出 2】 1580 【算法分析】 】 最简单、最基本的模拟加判断,连数组都不用开。只要读清题目,然后动手做就可以了。解决此类问题没 有什么技巧,最重要的是不在关键时刻出现低级错误。 [程序]
program save ; var f1,f2:text; a:array[1..12] of integer; i,tol,s:longint; begin assign(f1,'save.in'); reset(f1); assign(f2,'save.out'); rewrite(f2); tol:=0;s:=0; for i:=1 to 12 do begin readln(f1,a[i]); tol:=tol+300-a[i]; if tol<0 then begin writeln(f2,'-',i); close(f2); halt; end; s:=s+100*(tol div 100); tol:=tol mod 100; end; writeln(f2,tol+s+s div 5); close(f2); end.

例 2 小球钟(ball.pas)。 【问题描述】 】 时间是运动的一种方式。我们常常用运动来度量时间。例如,小球钟是一个通过不断在轨道上移动小球来 度量时间的简单设备。每分钟,一个转动臂将一个小球从小球队列的底部挤走,并将它上升到钟的顶部并将它 安置在一个表示分钟,5 分钟,15 分钟和小时的轨道上。这里可以显示从 1:00~24:59(这正是奇怪之处) 范围内的时间,若有 3 个球在分钟轨道,1 个球在 5 分钟轨道,2 个球在 15 分钟轨道及 15 个球在小时轨道上, 就显示时间 15:38。 当小球通过钟的机械装置被移动后,它们就会改变其初始次序。仔细研究它们次序的改变,可以发现相同 的次序会不断出现。由于小球的初始次序最后迟早会被重复,所以这段时间的长短是可以被度量的,这完全取 决于所提供的小球的总数。 小球钟的运作:每分钟,最近最少被使用的那个小球从位于球钟底部的小球队列被移走,并将上升并安置 于显示分钟的轨道上,这里可以放置 4 个小球。当第 5 个小球滚入该轨道,它们的重量使得轨道倾斜,原先在 轨道上的 4 个小球按照与它们原先滚入轨道的次序相反的次序加入到钟底部的小球队列。引起倾斜的第 5 个小 球滚入显示 5 分钟的轨道。该轨道可以放置 2 个球。当第 3 个小球滚入该轨道,它们的重量使得轨道倾斜,原 先 2 个小球同样以相反的次序加入钟底部的小球队列。 而这第 3 个小球滚入了显示 15 分钟的轨道。 这里可以放

·118·

第3章

算法与程序设计模块

置 3 个小球。当第 4 个小球滚入该轨道,它们的重量使得轨道倾斜,原先在轨道上的 3 个小球按照与它们原先 滚入轨道的次序相反的次序加入到钟底部的小球队列,而这第 4 个小球滚入了显示小时的轨道。该轨道同样可 以放置 23 个球,但这里有一个外加的固定的不能被移动的小球,这样小时的值域就变为 1~24。从 5 分钟轨道 滚入的第 24 个小球将使小时轨道倾斜, 23 个球同样以相反的次序加入钟底部的小球队列, 这 然后那第 24 个小 球同样加入钟底部的小球队列。 【输入】 】 输入定义了一序列的小球时钟。每个时钟都按照前面描述的那样运作。所有时钟的区别仅在于它们在 1: 00 时钟启动时刻小球初始个数的不同。在输入的每行上给出一个时钟的小球数,它并不包括那个在小时轨道上 的固定的小球。合法的数据应在 33~250 之间。0 表明输入的结束。 【输出】 】 输出中每一行只有一个数,表示对应的输入情形中给出的小球数量的时钟在经过多少天的运行可以回到它 的初始小球序列。 【样例输入】 】 33 55 0 【样例输出】 】 22 50 【算法分析】 】 该题是典型的模拟题。按常规思想:逐分钟地模拟小球钟的运作,直至钟底部的小球队列重又回到初始状 态时为止。这期间流逝的天数即为小球钟的运作周期。但这样全部模拟基本上无法在规定的时间内出解,必须 做一些改进。 于是,我们想到通过模拟出每个小球回到原来位置上所需的天数,然后求它们的最小公倍数。但是,如果 仍是单纯的模拟,速度仍然很慢。我们可以先模拟小球钟最先 24 小时的运行情况,得到一天后的钟底部的新小 球队列。有了这个条件后,我们可以在两次的钟底部小球队列间建立起一种置换。设初始时,钟底部的小球编 号依次是:1,2,3,…n。一天后,钟底部的小球编号依次是:p1,p2,p3,…pn。则我们可以建立这样的置换: 1 2 3 … n p1 p2 p3 … pn 注意到小球钟的运作规则保证了上述置换是不变的,就可以计算出小球钟运行 48 小时后,72 小时后……, 钟底部的小球队列情况,直至队列情况重新是 1,2,3,…,n。这样,在求得以上置换的基础上,我们可以求每一个 小球回到原位置的周期,然后求它们的最小公倍数即可。 [程序]
program ball var n, i : integer; m1, m2, m3, m4, m : string; c, c2 : char; now, long : longint; function gcd(a, b : longint) : longint; begin if b = 0 then gcd := a else if b = 1 then gcd := 1 else gcd := gcd(b, a mod b); end; function reverse(s : string) : string; var s2 : string; begin s2 := ''; while s <> '' do begin s2 := s[1] + s2; delete(s, 1, 1); end;

·119·

信息技术与信息学竞赛 reverse := s2; end; begin assign(input, 'ball.in'); reset(input); assign(output, 'ball.out'); rewrite(output); readln(n); while n > 0 do begin m := ''; for i := 1 to n do m := m + chr(i); repeat c := m[1]; delete(m, 1, 1); if length(m1) < 4 then m1 := m1 + c else begin m := m + reverse(m1); m1 := ''; if length(m2) < 2 then m2 := m2 + c else begin m := m + reverse(m2); m2 := ''; if length(m3) < 3 then m3 := m3 + c else begin m := m + reverse(m3); m3 := ''; if length(m4) < 23 then m4 := m4 + c else begin m := m + reverse(m4) + c; m4 := ''; end; end; end; end; until (m1 ='') and (m2 = '') and (m3 = '') and (m4 = ''); now := 1; for i := 1 to length(m) do if m[i] <> #0 then begin c := m[i]; m[i] := #0; long := 1; while m[ord(c)] <> #0 do begin inc(long); c2 := m[ord(c)]; m[ord(c)] := #0; c := c2; end; now := (now * long) div gcd(now, long); end; writeln(now); readln(n); end; close(output); close(input);

·120·

第3章 end.

算法与程序设计模块

例 3 奶牛(eat.pas)。 【题目描述】 】 一个农夫有 n(n≤1000)头奶牛,可由于产奶太少,他决定把当天产奶最少的牛杀掉,但他有点舍不得, 如果当天不只一头奶牛产奶,至少他便放过它们。这些奶牛产奶是周期性的,他已开始就想知道有多少奶牛可 幸免遇难(可能会被全杀),每头奶牛周期不会超过 10(每头奶牛产奶量≤250)。 【输入】 】 注:T——数据总数 N——奶牛总数 第一头奶牛周期天数,每天产奶数; 第二头奶牛周期天数,每天产奶数; …… 第 n 头奶牛周期天数,每天产奶数。 【样例输入】 】 1 4 47129 12 271 12 【样例输出】 】 26 注:2——最后剩下 2 头奶牛 6——最后一头牛是在第六天被杀的 【算法分析】 】 直述型模拟,每头奶牛产奶数 P:= p mod n +1;找最小值,最小值奶牛;用哈希表判奶牛是否死亡;注意 每个数据的初始化。 [程序]
program eat var h,p,pro:array [1..1000+10] of longint; m:array [1..1000+10,1..250] of longint; del:array [1..1000+10] of boolean; k,i,j,round,n:longint; ob,min,ans,ans2,now,change:longint; allk:boolean; begin assign(input,'eat.in');reset(input);assign(output,'eat.out'); rewrite(output); readln(k); for round:= 1 to k do begin fillchar(h,sizeof(h),0); fillchar(m,sizeof(m),0); fillchar(del,sizeof(del),0); fillchar(pro,sizeof(pro),0); ans:=0; ans2:=0; change:=0; readln(n); for i:= 1 to n do begin read(p[i]); for j:= 1 to p[i] do read(m[i,j]); readln;

·121·

信息技术与信息学竞赛 end; fillchar(h,sizeof(h),0); while true do begin inc(ans); for i:= 1 to n do if not del[i] then begin h[i]:=h[i] mod p[i] +1; pro[i]:=m[i,h[i]]; end; min:=maxlongint; for i:= 1 to n do if not del[i] then if pro[i]<min then min:=pro[i]; now:=0; for i:= 1 to n do if not del[i] then if pro[i]=min then begin inc(now); ob:=i end; if now=1 then begin del[ob]:=true; ans2:=ans; change:=0; end else inc(change); if change>500 then break; allk:=true; for i:= 1 to n do if not del[i] then allk:=false; if allk then break; end; ans:=0; for i:= 1 to n do if not del[i] then inc(ans); writeln(ans,' ',ans2); end; close(input); close(output); end.

例 4 猫和老鼠(catmou.pas)。 【题目描述】 】 猫和老鼠在 10×10 的方格中运动(如图 3-6),例如:
*...*..... ......*... ...*...*.. .......... ...*.C.... *.....*... ...*...... ..M......* ...*.*.... .*.*...... 图 3-6 猫和老鼠在 10×10 方格中的运动图

C=猫(CAT) M=老鼠(MOUSE) *=障碍物 .=空地 猫和老鼠每秒中走一格,如果在某一秒末它们在同一格中,我们称它们“相遇”。 注意:“对穿”是不算相遇的。猫和老鼠的移动方式相同:平时沿直线走,下一步如果会走到障碍物上去 注意 或者出界,就用 1 秒的时间做一个右转 90°。一开始它们都面向北方。 编程计算多少秒以后他们相遇。
·122·

第3章

算法与程序设计模块

【输入】10 行,格式如图 3-6 所示。 】 【输出】相遇时间 T。如果无解,输出-1。 】 【样例输入】 】 *...*..... ......*... ...*...*.. .......... ...*.C.... *.....*... ...*...... ..M......* ...*.*.... .*.*...... 【样例输出】 】 49 【算法分析】 】 题目没什么好的办法,只有模拟猫和老鼠。 [程序]
program catmon var ipt,opt:text; a:array[0..11,0..11] of char; i,b,cl,cw,ml,mw,aim,bim:byte; k:longint; begin assign(ipt,'catmou.in'); assign(opt,'catmou.out'); reset(ipt); rewrite(opt); for i:=1 to 10 do begin for b:=1 to 9 do read(ipt,a[b,i]); readln(ipt,a[10,i]); end; for i:=0 to 11 do begin a[i,0]:='*'; a[i,11]:='*'; a[0,i]:='*'; a[11,i]:='*'; end; for i:=1 to 10 do for b:=1 to 10 do begin if a[i,b]='C' then begin cw:=b; cl:=i; end; if a[i,b]='M' then begin mw:=b;

·123·

信息技术与信息学竞赛 ml:=i; end; end; aim:=1; bim:=1; k:=0; repeat if k>99999 then begin k:=-1; break; end; inc(k); if aim=1 then begin if a[ml,mw-1]='*' then inc(aim); if a[ml,mw-1]<>'*' then mw:=mw-1; end else begin if aim=2 then begin if a[ml+1,mw]='*' then inc(aim); if a[ml+1,mw]<>'*' then ml:=ml+1; end else begin if aim=3 then begin if a[ml,mw+1]='*' then inc(aim); if a[ml,mw+1]<>'*' then mw:=mw+1; end else begin if aim=4 then begin if a[ml-1,mw]='*' then aim:=1; if a[ml-1,mw]<>'*' then ml:=ml-1; end; end; end; end; if bim=1 then begin if a[cl,cw-1]='*' then inc(bim); if a[cl,cw-1]<>'*' then cw:=cw-1; end else begin if bim=2 then begin if a[cl+1,cw]='*' then inc(bim); if a[cl+1,cw]<>'*' then cl:=cl+1; end else begin if bim=3 then begin if a[cl,cw+1]='*' then inc(bim); if a[cl,cw+1]<>'*' then cw:=cw+1; end else begin if bim=4 then begin if a[cl-1,cw]='*' then bim:=1; ·124·

第3章 if a[cl-1,cw]<>'*' then cl:=cl-1; end; end; end; end; until (cl=ml) and (cw=mw); write(opt,k); close(ipt); close(opt); end.

算法与程序设计模块

例 5 字母运算(cowcul.pas)。 【题目描述】 】 有 4 个字母:U、C、D、V,它们可以相加,也能产生进位,如图 3-7 所示:V+V=V,U+D=V,但他要进 U 位现有 2 个由上述字母构成的“数”(五位),只对第 2 个数进行操作,有 3 种操作。

图 3-7

字母运算示意图

A:把第 2 个数变成两数之和; L:在数后加一个 V(对 UVUV 进行操作后为 UVUVV,相当于字符串相加); R:在数前加一个 V(同上),去掉末位。 现给你两个数以及 3 个操作,再给你一个数(8 位),把两数最前面连续的 V 去掉(VVVUV 变成 UV), 判断是否相等,相等输出 YES,不等则输出 NO。 【样例输入】 】 5 VVVVU VVVVU A A A VVVVVVUV VVCCV VVDCC L R A VVVVUCVC VVCCV VVDCC R L A VVVVUCVV VVUUU VVVVU A N

·125·

信息技术与信息学竞赛

N VVVVVUCU DDDDD VVVVU A L L UVVVVVVV 【样例输出】 】 COWCULATIONS OUTPUT YES YES YES NO YES END OF OUTPUT 【算法分析】 】 此题为模拟题。做法:题目转换。题目中的 U、V、C、D,其实都是忽悠你的,说白了就是对应了四进制 的加法、进位、让位等操作;这样题目就转换成了读入两个四进制数然后按操作与第三个数对比大小即可。时 间:O(1)。 [程序]
program cowcul; type num=array [0..100] of longint; var a,b,x: num; tests,round,i,j: longint; c: char; function magic(c:char):integer; begin case c of 'V': exit(0); 'U': exit(1); 'C': exit(2); 'D': exit(3); end; exit(0); end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure dd(var a:num; n:longint); var l,r,t:longint; begin l:=1; r:=n; while l<r do begin t:=a[l]; a[l]:=a[r]; a[r]:=t; inc(l); dec(r); end; while a[n]=0 do dec(n); a[0]:=n; end;

·126·

第3章

算法与程序设计模块

procedure sum(a:num; var b:num); var l,r,t,i:longint; begin l:=max(a[0],b[0]); for i:= 1 to l do begin inc(b[i+1],(a[i]+b[i]) div 4); b[i]:=(a[i]+b[i]) mod 4; end; if b[l+1]<>0 then b[0]:=l+1 else b[0]:=l; end; procedure add(var b:num); var i:longint; begin for i:= b[0] downto 1 do b[i+1]:=b[i]; b[1]:=0; inc(b[0]); end; procedure dda(var b:num); var i:longint; begin for i:= 2 to b[0] do b[i-1]:=b[i]; b[b[0]]:=0; dec(b[0]); end; function Compare(a,b:num):boolean; var l:longint; begin l:=max(b[0],a[0]); for i:= 1 to l do if b[i]<>a[i] then exit(false); exit(true); end; begin assign(input,'cowcul.in'); reset(input); assign(output,'cowcul.out'); rewrite(output); writeln('COWCULATIONS OUTPUT'); readln(tests); for round:= 1 to tests do begin fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); fillchar(x,sizeof(x),0); for i:= 1 to 5 do begin read(c); a[i]:=magic(c) end; readln; dd(a,5); for i:= 1 to 5 do begin read(c); b[i]:=magic(c) end; readln; dd(b,5); for i:= 1 to 3 do begin readln(c); case c of 'A': sum(a,b); 'L': add(b); 'R': dda(b); end; end; for i:= 1 to 8 do begin read(c); x[i]:=magic(c) end; readln; dd(x,8); if compare(b,x) then writeln('YES') else writeln('NO'); end; writeln('END OF OUTPUT'); ·127·

信息技术与信息学竞赛 close(input); close(output); end.

例 6 内存分配(memory.pas)。 【题目描述】 】 内存是计算机重要的资源之一,程序运行的过程中必须对内存进行分配。经典的内存分配过程是这样进行 的: (1)内存以内存单元为基本单位,每个内存单元用一个固定的整数作为标识,称为地址。地址从 0 开始 连续排列,地址相邻的内存单元被认为是逻辑上连续的。我们把从地址 i 开始的 s 个连续的内存单元称为首地 址为 i 长度为 s 的地址片。 (2)运行过程中有若干进程需要占用内存,对于每个进程有一个申请时刻 T,需要内存单元数 M 及运行 时间 P。在运行时间 P 内(即 T 时刻开始,T+P 时刻结束),这 M 个被占用的内存单元不能再被其他进程使用。 (3)假设在 T 时刻有一个进程申请 M 个单元,且运行时间为 P,则: ①若 T 时刻内存中存在长度为 M 的空闲地址片,则系统将这 M 个空闲单元分配给该进程。若存在多个长度 为 M 个空闲地址片,则系统将首地址最小的那个空闲地址片分配给该进程。 ②如果 T 时刻不存在长度为 M 的空闲地址片,则该进程被放入一个等待队列。对于处于等待队列队头的 进程,只要在任一时刻,存在长度为 M 的空闲地址片,系统马上将该进程取出队列,并为它分配内存单元。 注意:在进行内存分配处理过程中,处于等待队列队头的进程的处理优先级最高,队列中的其他进程不能 注意 先于队头进程被处理。 现在给出一系列描述进程的数据,请编写一程序模拟系统分配内存的过程。 【输入】 】 第一行是一个数 N,表示总内存单元数(即地址范围从 0~N-1)。从第二行开始每行描述一个进程的 3 个整数 T、M、P(M≤N)。最后一行用 3 个 0 表示结束。数据已按 T 从小到大排序。输入文件最多 10000 行, 且所有数据都小于 109。输入文件中同一行相邻两项之间用一个或多个空格隔开。 【输出】 】 每组数据输出 2 行。第一行是全部进程都运行完毕的时刻。第二行是被放入过等待队列的进程总数。 【样例输入】 】 10 1 3 10 243 344 414 534 000 【样例输出】 】 12 2 【算法分析】 本题虽然数据规模比较大,但输入是比较随机的,也就是说,单纯的模拟就可以了。 具体的方法是,用一个堆存储每个进程的结束时间,以便及时释放内存;同时用一个双向链表按每个进程 在内存中的顺序存储其地址, 这样在有新进程申请时就可以通过遍历链表而找到合适的地址运行它 (所说的 “输 入比较随机”,就是指输入没有故意使得每次插入进程时都要遍历整个链表)。当然,还要有一个等待队列。 为了让堆和链表同时更新,需要在堆和链表的对应元素间建立互链。这样处理每个进程的流程就可以描述为: ①读入一个进程的信息; ②将在新进程开始前或开始时结束的进程删除, 检查等待队列首的进程是否可以运行; ③判断新进程是可以运行还是需放进等待队列。为了在所有进程都放进堆后可以清空堆,可以在最后假设读入 了一个在无穷大时间结束的进程。 上述流程中的第②步的实现要注意: 第一种做法, 不能先把在新进程开始前或开始时结束的进程统统删除, 再检查等待队列;第二种做法,也不能删除一个进程就检查一次队列。正确的做法是 正确的做法是:把与堆顶进程同时结束 正确的做法是

·128·

第3章

算法与程序设计模块

的进程全部删除,检查等待队列,重复进行直至堆顶进程的结束时间晚于新进程的开始时间。为什么不能采用 第二种做法呢?因为堆中元素仅仅按结束时间排序,若删除一个就检查一次等待队列,则可能造成在同时结束 的进程中,地址大的先被删除,等待队列首的进程就正好被放在大地址了,而实际上它应该放在小地址,这样 就造成了以后的混乱。 [程序]
program memory; const maxprogs=10001; var heap:array[0..maxprogs]of record fin:longint;pchain:word;end; chain:array[0..maxprogs]of record left,right:longint; pheap,pre, ext:word; end; wait:array[1..maxprogs]of record mem,time:longint;end; h,n,a,b,c,f,r,now,p:longint; function where(mem:longint):word; begin where:=0; while (chain[where].next>0) and (chain[chain[where].next].left-chain[where].right<mem) do where:=chain[where].next; end; procedure ins(where,fintime,mem:longint); var p,q:word; begin inc(n); with chain[n] do begin left:=chain[where].right;right:=left+mem; pre:=where;next:=chain[where].next; end; chain[where].next:=n;chain[chain[n].next].pre:=n; inc(h);p:=h;q:=p shr 1; while (p>1) and (fintime<heap[q].fin) do begin heap[p]:=heap[q]; chain[heap[p].pchain].pheap:=p; p:=q;q:=p shr 1; end; with heap[p] do begin fin:=fintime;pchain:=n;end; chain[n].pheap:=p; end; function pop:longint; var p,l,r:word; begin pop:=heap[1].fin; p:=heap[1].pchain;chain[chain[p].pre].next:=chain[p].next;chain[chain[p].next].pre:=ch ain[p].pre; p:=1;l:=2;r:=3; repeat if (r<h) and (heap[h].fin>heap[r].fin) and (heap[r].fin<heap[l].fin) then begin heap[p]:=heap[r]; chain[heap[p].pchain].pheap:=p; p:=r; end else if (l<h) and (heap[h].fin>heap[l].fin) then begin heap[p]:=heap[l]; chain[heap[p].pchain].pheap:=p;

·129·

信息技术与信息学竞赛 p:=l; end else break; l:=p*2;r:=l+1; until false; heap[p]:=heap[h];chain[heap[p].pchain].pheap:=p; dec(h); end; begin repeat assign(input,'memory.in');reset(input); assign(output,'memory.out');rewrite(output); h:=1; with heap[1] do begin fin:=maxlongint;pchain:=1;end; n:=1; with chain[0] do begin right:=0;next:=1;end; with chain[1] do begin read(left);pheap:=1;pre:=0;next:=0;end; f:=1;r:=0; repeat read(a,b,c); if b=0 then a:=maxlongint-1; while heap[1].fin<=a do begin repeat now:=pop;until heap[1].fin>now; while f<=r do begin p:=where(wait[f].mem); if chain[p].next=0 then break; ins(p,now+wait[f].time,wait[f].mem); inc(f); end; end; if b=0 then break; p:=where(b); if chain[p].next>0 then ins(p,a+c,b) else begin inc(r);wait[r].mem:=b;wait[r].time:=c; end; until false; writeln(now);writeln(r); close(input);close(output); until seekeof; end.

练习题
1.购物(money.pas)。 【题目描述】 Dino 同学喜欢去购物,但是他不想花很多钱,所以他总是挑那些打折的东西买,现在给出他买的所有东西 的一个购物清单,以及每个物品打几折,问:他这次购物一共花了多少钱? 【输入】 第一行一个 n(1≤n≤100)表示 Dino 一共买了多少个东西。后面紧接 n 行,每行描述购买的一种物品:每行 2 个整数 ai,bi(1≤ai≤10000,1≤bi≤10)。 【输出】 一行,一个实数为 Dino 一共花了多少钱,答案保留 2 位小数。

·130·

第3章

算法与程序设计模块

【样例输入】 2 10000 10 11 【样例输出】 10000.10 2.棋局(hiq.pas)。 【题目描述】 如图 3-8 所示。
1 4 7 14 21 8 15 22 9 16 23 28 31 2 5 10 17 24 29 32 图 3-8 3 6 11 18 25 30 33 棋局示意图 12 19 26 13 20 27

数字相当于格子的编号,在它们上面有棋子,移动规则是:每次移动一个棋子,这个棋子必须跨越与其相 邻的一个棋子到达一个空格子上(和跳棋类似),且只能横竖走,不能斜着走,移动完后,中间那个棋子就会 被吃掉。 在一个棋局中,有很多棋子可以移动,那么移动哪一个呢?若把每个棋子移动后会到达的格子称为目标格 子,则在这些目标格子中选择编号最大的一个,再在能达到此格子的棋子中选择编号最大的一个来移动。经过 若干次移动后,就会出现不能移动的情况。此时,输出所有棋子所在编号的和。输入会告诉你哪些格子上有棋 子,以 0 结束(不一定一行一组数据)。 【样例输入】 4 10 12 17 19 25 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 0

·131·

信息技术与信息学竞赛

【样例输出】 HI Q OUTPUT 51 0 561 98 END OF OUTPUT 猜想 “猜想”是一种重要的思维方法,对于确定证明方向,发现新定理,都有重大意义。

3.7
1.算法思想

贪 心 算 法

从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一 步不能再继续前进时,算法停止。该算法存在的问题: (1)不能保证求得的最后解是最佳的。 (2)不能用来求最大或最小解问题。 (3)只能求满足某些约束条件的可行解的范围。 实现该算法的过程: (1)从问题的某一初始解出发。 (2)while 能朝给定总目标前进一步 do 求出可行解的一个解元素。 (3)由所有解元素组合成问题的一个可行解。 (4)贪心:找出所有度为 1 的结点,把与它们相连的结点上都放上士兵,然后把这些度为 1 的结点及已 放上士兵的结点都去掉。重复上述过程直至数空为止。 2.特点及使用范围 贪心算法的优点在于时间复杂度极低。贪心算法与其他最优化算法的区别在于:它具有不可后撤性,可以 有后效性,一般情况下不满足最优化原理。贪心算法的特点就决定了它的适用范围,他一般不适用于解决可行 性问题,仅适用于较容易得到可行解的最优性问题。这里较容易得到可行解的概念是:当前的策略选择后,不 会或极少使后面出现无解的情况。另外,对于近年来出现的交互性题目,贪心算法是一个较好的选择。这是因 为在题目中,一个策略的结果是随题目的进行而逐渐给出的,我们无法预先知道所选策略的结果,这与贪心算 法不考虑策略的结果和其具有后效性的特点是不谋而合的。当然,贪心算法还可以为搜索算法提供较优的初始 界值。 3.使用贪心算法的技巧(贪心与最优化算法的结合) 尽管贪心算法有一定的优越性,但它毕竟在一般情况下得不到最优解。因此,为了尽量减小贪心算法带来 的副作用, 使得最后得到的解更接近最优解, 应该在算法尽可能多的地方使用有效的最优化算法 (如动态规划) 。 4.贪心算法的改进 贪心算法的缺点在于解的效果比较差,而最大优势在于极低的时间复杂度,而且往往时间复杂度远远低于 题目的限制。那么,我们为什么不再花一部分时间来提高目标解的效果呢?这就是对贪心算法改进的必要性。 例 1 智力大冲浪(riddle.pas)。 【题目描述】 小伟报名参加中央电视台的智力大冲浪节目。 本次挑战赛吸引了众多参赛者, 主持人为了表彰大家的勇气, 先奖励每个参赛者 m 元。先不要太高兴!因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则:

·132·

第3章

算法与程序设计模块

首先,比赛时间分为 n 个时段(n≤500),它又给出了很多小游戏,每个小游戏都必须在规定期限 ti 前完成 (1≤ti≤n)。如果一个游戏没能在规定期限前完成,则要从奖励费 m 元中扣去一部分钱 wi,wi 为自然数,不同 的游戏扣去的钱是不一样的。当然,每个游戏本身都很简单,保证每个参赛者都能在一个时段内完成,而且都 必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者,小伟很想赢 得冠军,当然更想赢取最多的钱! 注意:比赛绝对不会让参赛者赔钱! 注意 【输入】 输入文件 riddle.in,共 4 行。 第一行为 m,表示一开始奖励给每位参赛者的钱; 第二行为 n,表示有 n 个小游戏; 第三行有 n 个数,分别表示游戏 1~n 的规定完成期限; 第四行有 n 个数,分别表示游戏 1~n 不能在规定期限前完成的扣款数。 【输出】 输出文件 riddle.out,仅 1 行。表示小伟能赢取最多的钱。 【样例输入】 10000 7 4243146 70 60 50 40 30 20 10 【样例输出】 9950 【算法分析】 因为不同的小游戏不能准时完成时具有不同的扣款权数,而且是最优解问题,所以本题很容易就想到了贪 心法。 贪心的主要思想是要让扣款数值大的尽量准时完成。 这样我们就先把这些任务按照扣款的数目进行排序, 把大的排在前面,先进行放置。假如罚款最多的一个任务的完成期限是 k,我们应该把它安排在哪个时段完成 呢?应该放在第 k 个时段,因为放在 1~k 任意一个位置,效果都是一样的。一旦出现一个不可能在规定时限前 完成的任务,则把其扔到最大的一个空时间段,这样必然是最优的,因为不能完成的任务,在任意一个时间段 中罚款数目都是一样的,具体实现请参考下面的[程序 1]。 本题也可以有另外一种贪心算法,即先把所有的数据按照结束时间的先后排序,然后从前向后扫描。当扫 描到第 n 个时段,发现里面所分配任务的结束时间等于 n-1,那么就说明在前面这些任务中必须舍弃一个,于 是再扫描第 1~n 这 n 个时段,挑出一个最小的去掉并累加扣款值,然后再去调整排列顺序,让后面的元素填补 前面的空缺,具体实现参考下面 的[程序 2]。 [程序 1]
program riddle1 (input, output); var i,j,k,n,s,m:longint; boo:boolean; a,b:array[1..100] of longint; hash:array[1..100] of boolean; procedure sort; var p,q:longint; begin for i:=1 to n-1 do for j:=i+1 to n do if b[i]<b[j] then begin p:=b[i];b[i]:=b[j];b[j]:=p; p:=a[i];a[i]:=a[j];a[j]:=p;end; end; begin fillchar(hash,sizeof(hash),true);

·133·

信息技术与信息学竞赛 assign(input,'riddle.in'); reset(input); assign(output,'riddle.out'); rewrite(output); readln(m); readln(n); for i:=1 to n do read(a[i]); for i:=1 to n do read(b[i]); sort; for i:=1 to n do begin boo:=true; for j:=a[i] downto 1 do if hash[j] then begin boo:=false;hash[j]:=false;break;end; if boo then begin for k:=n downto 1 do if hash[k] then begin hash[k]:=false;break;end; inc(s,b[i]); end; end; writeln(m-s); close(input); close(output); end.

[程序 2]
program riddle2(input,output); var m,n,p,min,minx,total:longint; w,t:array[1..100] of longint; i,j:longint; begin assign(input,'riddle.in'); assign(output,'riddle.out'); reset(input); rewrite(output); readln(m); readln(n); for i:=1 to n do read(t[i]); for i:=1 to n do read(w[i]); for i:=1 to n-1 do for j:=i+1 to n do if (t[i]>t[j]) or (t[i]=t[j]) and (w[i]>w[j]) then begin p:=t[i]; t[i]:=t[j]; t[j]:=p; p:=w[i]; w[i]:=w[j]; w[j]:=p; end; for i:=1 to n do

·134·

第3章 if (t[i]<i) and (i<=n) then begin min:=maxlongint; for j:=1 to i do if w[j]<min then begin min:=w[j]; minx:=j; end; total:=total+min; for j:=minx to n-1 do begin w[j]:=w[j+1]; t[j]:=t[j+1]; end; dec(n); dec(i); end; writeln(m-total); close(input); close(output); end.

算法与程序设计模块

例 2 合并果子(fruit.pas)。 【题目描述】 在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所 有的果子合成一堆。每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可 以看出,所有的果子经过 n-1 次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并 所耗体力之和。 因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都 为 1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少, 并输出这个最小的体力耗费值。 例如,有 3 种果子,数目依次为 1、2、9。可以先将 1、2 堆合并,新堆数目为 3,耗费体力为 3。接着, 将新堆与原先的第三堆合并,又得到新的堆,数目为 12,耗费体力为 12。所以多多总共耗费体力 15=3+12。可 以证明 15 为最小的体力耗费值。 【输入】 输入文件 fruit.in 包括两行。第一行是一个整数 n(1≤n≤10000),表示果子的种类数。第二行包含 n 个整数, 用空格分隔,第 i 个整数 ai(1≤ai≤20000)是第 i 种果子的数目。 【输出】 输出文件 fruit.out 包括一行,这一行只包含一个整数,也就是最小的体力耗费值。输入数据保证这个值小 于 231。 【样例输入】 3 129 【样例输出】 15 【数据规模】 对于 30%的数据,保证有 n≤1000; 对于 50%的数据,保证有 n≤5000; 对于全部的数据,保证有 n≤10000。 【算法分析】

·135·

信息技术与信息学竞赛

此题用贪心法。先将果子数排序,取其中最小的两堆合并,得到一个新堆;再排序,再取其中最小的两堆 合并……直到只剩一堆。为尽快出解,排序的速度显得格外重要,可用快速排序算法。 [程序]
program pruit var n,i,em:word; heap:array[1..10001]of dword; sum:dword; w,a,b:dword; procedure add (w:dword); var i:word; sw:dword; begin i:=em; heap[i]:=w; while (i>1) and (heap[i div 2]>heap[i]) do begin sw:=heap[i div 2]; heap[i div 2]:=heap[i]; heap[i]:=sw; i:=i div 2; end; while heap[em]<>0 do inc(em); end; procedure swap (s:word); var a,b:word; begin a:=s*2; b:=s*2+1; if (b>10001) or (heap[a]=0) and (heap[b]=0) then begin heap[s]:=0; if s<em then em:=s; exit; end; if heap[a]=0 then begin heap[s]:=heap[b]; swap(b); exit; end; if heap[b]=0 then begin heap[s]:=heap[a]; swap(a); exit; end; if heap[a]>heap[b] then begin heap[s]:=heap[b]; swap(b); end else begin

·136·

第3章 heap[s]:=heap[a]; swap(a); end; end; function pop:dword; begin pop:=heap[1]; swap(1); end; begin assign(input,'fruit.in'); assign(output,'fruit.out'); reset(input); rewrite(output); readln(n); em:=1; sum:=0; fillchar(heap,sizeof(heap),0); for i:=1 to n do begin read(w); add(w); end; readln; for i:=1 to n-1 do begin a:=pop; b:=pop; inc(sum,a+b); add(a+b); end; writeln(sum); close(input);close(output); end.

算法与程序设计模块

·137·

信息技术与信息学竞赛

例 3 建筑抢修(repair.pas)。 【题目描述】 小刚在玩 JSOI 提供的一个称之为“建筑抢修”的电脑游戏。经过了一场激烈的战斗,T 部落消灭了所有 Z 部落的入侵者。但是 T 部落的基地里已经有 N 个建筑设施受到了严重的损伤,如果不尽快修复的话,这些建筑 设施将会完全毁坏。 现在的情况是:T 部落基地里只有一个修理工人。虽然他能瞬间到达任何一个建筑,但是修复每个建筑都需 要一定的时间。同时,修理工人修理完一个建筑才能修理下一个建筑,不能同时修理多个建筑。如果某个建筑在 一段时间之内没有完全修理完毕,这个建筑就报废了。 你的任务是帮小刚合理制定一个修理顺序,以抢修尽可能多的建筑。 【输入】 输入文件第一行是一个整数 N,N 行每行两个整数 T1、T2 描述一个建筑:修理这个建筑需要 T1 秒,如果 在 T2 秒之内还没有修理完成,这个建筑就报废了。 【输出】 输出文件只有一行,是一个整数 S,表示最多可以抢修 S 个建筑。 N<150000; T1<T2<maxlongint 【样例输入】 4 100 200 200 1300 1000 1250 2000 3200 【样例输出】 3 【算法分析】 贪心 O(N Log N) + 高级数据结构。很容易想到动态规划。按截止时间排序,维护队列 q,如果能插入就 插入,如不能插入,就把一个花费时间最大的替换下来。 [程序]
program repair; const inf='repair.in'; ouf='repair.out';maxn=150000+10; type PIT=^Pnode; Pnode=record l,r:PIT; s,k:longint; end; var f,g,a,b: array [0..maxn] of longint; i,j,n,ans,now,x,e: longint; p,t: PIT; procedure Swap(var a,b:longint); var c:longint; begin c:=a; a:=b; b:=c; end; procedure Qsort(l,r:longint); var i,j,p:longint; begin i:=l; j:=r; p:=b[(i+j)>>1]; repeat while b[i]<p do inc(i); while b[j]>p do dec(j); if i<=j then begin swap(b[i],b[j]); swap(a[i],a[j]); inc(i); dec(j);

·138·

第3章

算法与程序设计模块

end; until i>j; if l<j then Qsort(l,j); if i<r then Qsort(i,r); end; procedure Make(var p:PIT); begin p^.l:=nil; p^.r:=nil; p^.s:=0; p^.k:=0; end; procedure Ins(t:PIT; l,r,k:longint); begin inc(t^.s); if l=r then begin if t^.k=0 then t^.k:=k; exit; end; if k<=(l+r)>>1 then begin if t^.l=nil then begin new(p); make(p); t^.l:=p; end; ins(t^.l,l,(l+r)>>1,k); end else begin if t^.r=nil then begin new(p); make(p); t^.r:=p; end; ins(t^.r,(l+r)>>1+1,r,k); end; end; procedure Del(t:PIT; l,r,k:longint); begin if t=nil then exit; dec(t^.s); if l=r then exit; if k<=(l+r)>>1 then del(t^.l,l,(l+r)>>1,k) else del(t^.r,(l+r)>>1+1,r,k); end; function RFS(t:PIT; l,r,k:longint):longint; var d:longint; begin if t=nil then exit(-1); if l=r then exit(t^.k); if t^.l=nil then d:=0 else d:=t^.l^.s; if k<=d then exit(RFS(t^.l,l,(l+r)>>1,k)) else exit(RFS(t^.r,(l+r)>>1+1,r,k-d)); end; begin assign(input,inf); reset(input); assign(output,ouf); rewrite(output); readln(n); for i:= 1 to n do readln(a[i],b[i]); qsort(1,n);new(t); make(t); e:=maxlongint; for i:= 1 to n do begin if now+a[i]<b[i] then begin inc(now,a[i]);inc(ans); ins(t,0,e,a[i]); end else begin x:=rfs(t,0,e,t^.s); if x>a[i] then begin dec(now,x); inc(now,a[i]); del(t,0,e,x); ins(t,0,e,a[i]); end;

·139·

信息技术与信息学竞赛 end; end; writeln(ans); close(input); close(output); end.

练习题
木梳(comb.pas) 艾艺从小酷爱艺术,他梦想成为一名伟大的艺术家。最近他获得了一块材质不错的木板,其下侧为直线段, 长为 L,平均分为 L 段,从左到右编号为 1,2,…,L。木板的上侧为锯齿形,高度为整数,第 i 段的高度为 Ai, Ai≥2(如图 3-8 所示)。 这么好的一段材料浪费了怪可惜的,艾艺决定好好加工一番做成一件艺术品。但他不是纯艺术家,他觉得 每件艺术品都应有实用价值(否则只是华而不实),具有实用性的艺术品是他设计的理念。 根据这块木板的锯齿状,艾艺想到了每天起床后都要用到的一件日用品,便想把它做成梳子!他的设想是: 用刻刀将某些上端的格子挖掉(如果把某个格子挖掉,那么这个格子上方的格子也必须被挖掉,但不能把一列 中的格子全都挖掉),使得剩下的木板构成“规则锯齿形”(这样才好梳头)。 如图 3-9 所示,挖掉第 3、7、8 列最上面的 1 个格子和第 5 列最上面的 2 个格子后,剩下的区域就构成“规 则锯齿形”(如图 3-10 所示)。一个锯齿形称为“规则锯齿形”当且仅当它的上边界(图 3-10 中红色曲线所 示)的拐点序列不包含“010”或者“101”。图 3-9 中红色曲线的拐点序列为:“011001”,(其中 0 代表左 拐,1 代表右拐),沿着曲线的最左端往右走,先左拐,再右拐,接着右拐,然后左拐,继续左拐,最后右拐。 为了最大限度地减少浪费,艾艺希望做出来的梳子面积最大。
L=9 A=(4,4,6,5,4,2,3,3,5)

1
图 3-9

2 3

4

5

6 7

8 9
图 3-10 木梳题示意图(2)

木梳题示意图(1)

【输入】 从文件 input.txt 中读入数据,文件第一行为整数 L,其中 4≤L≤100000,且有 50%的数据满足 L≤104, 表示木板下侧直线段的长。第二行为 L 个正整数 A1,A2,…,AL,其中 1<Ai≤108,表示第 i 段的高度。 【输出】 输出文件 output.txt 中仅包含一个整数 D,表示为使梳子面积最大,需要从木板上挖掉的格子数。 【样例输入】 9 4 4 6 5 4 2 3 3 5(方案如图 3-11 所示)

图 3-11

木梳题示意图(3)

【样例输出】

·140·

第3章

算法与程序设计模块

3

3.8

深度优先搜索

编程学到现在才真正到了高深部分,从这里往下学,你才知道什么叫做博大精深。今天我们要啃的这块硬 骨头叫做深度优先搜索法。 首先我们来想象一只老鼠,在一座不见天日的迷宫内,老鼠在入口处进去,要从出口出来。那老鼠会怎么 走?当然是这样的:老鼠如果遇到直路,就一直往前走;如果遇到分叉路口,就任意选择其中的一个继续往下 走;如果遇到死胡同,就退回到最近的一个分叉路口,选择另一条道路再走下去;如果遇到了出口,老鼠的旅 途就算结束了。深度优先搜索法的基本原则就是这样:按照某种条件往前试探搜索,如果前进中遭到失败(正 如老鼠遇到死胡同)则退回头另选通路继续搜索,直到找到条件的目标为止。 实现这一算法,我们要用到编程的另一大利器——递归。递归是一个很抽象的概念,但是在日常生活中, 我们还是能够看到的。拿两面镜子来,把他们面对着面,你会看到什么?你会看到镜子中有无数个镜子?怎么 回事?A 镜子中有 B 镜子的像,B 镜子中有 A 镜子的像,A 镜子的像就是 A 镜子本身的真实写照,也就是说 A 镜子的像包括了 A 镜子,还有 B 镜子在 A 镜子中的像……好累啊,又烦又绕口,还不好理解。换成计算机语 言就是 A 调用 B,而 B 又调用 A,这样间接的,A 就调用了 A 本身,这实现了一个重复的功能。 他再举一个例子:从前有座山,山里有座庙,庙里有个老和尚,老和尚在讲故事,讲什么呢?讲:从前有 座山,山里有座庙,庙里有个老和尚,老和尚在讲故事,讲什么呢?他讲:从前有座山,山里有座庙,庙里有 个老和尚,老和尚在讲故事,讲什么呢?他讲:……。好家伙!这样讲到世界末日还讲不完,老和尚讲的故事 实际上就是前面的故事情节,这样不断地调用程序本身,就形成了递归。 万一这个故事中的某一个老和尚看这个故事不顺眼,就把他要讲的故事换成:“你有完没完啊!”,这样, 整个故事也就嘎然而止了。我们编程就要注意这一点,在适当的时候,就必须要有一个这样的和尚挺身而出, 把整个故事给停下来,或者使他不再往深一层次搜索。要不,我们的递归就会因计算机存储容量的限制而被迫 溢出。切记!切记!! 我们把递归思想运用到上面的迷宫中,记老鼠现在所在的位置是(x,y),那它现在有前后左右四个方向可以 走,分别是(x+1,y),(x-1,y),(x,y+1),(x,y-1),其中一个方向是它来时的路,先不考虑,我们就分别尝试其他 3 个方向,如果某个方向是路而不是墙的话,老鼠就向那个方向迈出一步。在新的位置上,我们又可以重复前面 的步骤。老鼠走到了死胡同又是怎么回事?就是除了来时的路,其他 3 个方向都是墙,这时这条路就走到了尽 头,无法再向深一层发展,我们就应该沿来时的路回去,尝试另外的方向。 例 1 8 皇后问题。 在标准国际象棋的棋盘上(8×8 格)准备放置 8 位皇后,我们知道,国际象棋中皇后的威力是最大的,她 既可以横走竖走,还可以斜着走,遇到挡在她前进路线上的敌人,她就可以吃掉对手。要求在棋盘上安放 8 位 皇后,使她们彼此互相都不能吃到对方,求皇后的放法。 这是一道很经典的题目了,我们先要明确一下思路,如何运用深度优先搜索法,完成这道题目。首先建立 一个 8×8 格的棋盘,在棋盘的第一行的任意位置安放一只皇后。紧接着,我们就来放第二行,第二行的安放就 要受一些限制了,因为与第一行的皇后在同一竖行或同一对角线的位置上是不能安放皇后的,接下来是第三 行,……,或许我们会遇到这种情况,在摆到某一行的时候,无论皇后摆放在什么位置,她都会被其他行的皇 后吃掉,这说明什么呢?这说明,我们前面的摆放是失败的,也就是说,按照前面的皇后的摆放方法,我们不 可能得到正确的解。那这时怎么办?改啊!我们回到上一行,把原先摆好的皇后换另外一个位置,接着再回过 头摆这一行,如果这样还不行或者上一行的皇后只有一个位置可放,那怎么办?我们回到上一行的上一行,这 和老鼠碰了壁就回头是一个意思。就这样的不断地尝试、修正,再尝试、再修正,我们最终会得到正确的结论。 [程序]
program queen; {8 皇后问题参考程序} const n=8; var a,b:array [1..n] of integer;{数组 a 存放解:a[i]表示第 i 个皇后放在第 a[i]列;}

·141·

信息技术与信息学竞赛 c:array [1-n,n-1] of integer; d:array [2..n+n] of integer; {数组 b,c,d 表示棋盘的当前情况:b[k]为 1 表示第 k 行已被占领为 0 表示 为空;c、d 表示对角线} k:integer; procedure print; {打印结果} var j:integer; begin for j:=1 to n do write(a[j]:4); writeln; end; procedrue try(i:integer); {递归搜索解} var j:integer; {每个皇后的可放置位置。注意:一定要在过程中定义;否则当递归时会覆盖掉 它的值,不能得到正确结果} begin for j:=1 to n do begin if (b[j]=0) and (c[i-j]=0) and (d[i+j]=0) then{检查位置是否合法} begin a[i]:=j; {置第 i 个皇后的位置是第 j 行} b[j]:=1; {宣布占领行、对角线} c[i-j]:=1; d[i+j]:=1; if i<n then try(i+1) else print;{如果未达目标则放置下一皇后,否则打印结果} b[j]:=0; {清空被占行、对角线,回溯} c[i-j]:=0; d[i+j]:=0; end; end; end; begin for k:=1 to n do b[k]:=0; {初始化数据} for k:=1-n to n-1 do c[k]:=0; for k:=2 to n+n do d[k]:=0; try(1); end.

在深度优先搜索中,也是从初始结点开始扩展,但是扩展顺序却不同,深度优先搜索总是先扩展最新产生 的结点。这就使得搜索沿着状态空间某条单一的路径进行下去,直到最后的结点不能产生新结点或者找到目标 结点为止。当搜索到不能产生新的结点的时候,就沿着结点产生顺序的反方向寻找可以产生新结点的结点,并 扩展它,形成另一条搜索路径。 深度优先搜索中扩展结点的原则是先产生的后扩展。因此,深度优先搜索第一个找到的解,并不一定是问 题的最优解,要搜索完整个状态空间,才能确定哪个解是最优解。 深度优先搜索的算法如下: (1)从初始结点开始,将待扩展结点依次放到 open 表中。open 表为栈结构,即遵守后进先出的规则。 (2)如果 open 表空,即所有待扩展结点已全部扩展完毕,则问题无解,退出。 (3)取 open 表中最新加入的结点,即栈顶结点出栈,并用相应的算符扩展出所有的予结点,并按顺序将 这些结点放入 open 表中。若没有子结点产生,则转(2)。 (4)如果某个子结点为目标结点,则找到问题的解(这不一定是最优解),结束。如果要求得问题的最 优解,或者所有解,则转(2),继续搜索新的目标结点。 【深度优先搜索的算法】
procedure DFS; begin open ←1; data[open] .state ←初始状态; Search Success ← false;

·142·

第3章

算法与程序设计模块

repeat currentnode ←data[open]; open ←open-l; while current {还可以扩展} do begin new ← operate (currentnode.state); if new {重复于已有的结点状态} then continue; open ← open+l; data[open].state ← new; data[open].last ← currentnode; if new {是目标状态} then begin Search Success ← true;break;end; end; until (open<l) or (Search Success); if Search Success then Output(Reslut) else 0utput(No Answer); end;

例 2 选数(select.pas)。 【题目描述】 已知 n(1≤n≤20)个整数 x1,x2,…,xn(1≤xi≤5000000),以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。现在,要求你计算出和为素数共有多少种。 例如, n=4, 当 k=3, 个整数分别为 3、 12、 时, 4 7、 19 可得全部的组合与它们的和为: 3+7+12=22; 3+7+19=29; 7+12+19=38;3+12+19=34。 现在,要求你计算出和为素数共有多少种。 例如,例 2 只有一种和为素数:3+7+19=29。 【输入】 格式为: n , k (1<=n<=20,k<n) x1,x2,…,xn (1<=xi<=5000000) 【输出】 一个整数(满足条件的种数)。 【样例输入】 43 3 7 12 19 【样例输出】 1 【算法分析】 本题无数学公式可寻,看来只能搜索(组合的生成算法),其实 1≤n≤20 这个约束条件也暗示我们本题 搜索是有希望的,组合的生成可用简单的 DFS 来实现,既搜索这 k 个整数在原数列中的位置,由于组合不同于 排列,与这 k 个数的排列顺序无关,所以,可以令 a[I]<a[I+1](a[I]表示第 I 个数在原数列中的位置),这个组 合生成算法的复杂度大约为 C(n,k),下面给出递归搜索算法的框架。 Proc Search(dep) Begin for i <- a[dep - 1] + 1 to N - (M - dep) do 1. a[dep] <- i 2. S <- S + x[i] 3. if dep < k then Search(dep + 1) else 判断素数 4. S <- S - x[i] End 接下来的问题就是判断素数,判断一个整数 P(P>1)是否为素数最简单的方法就是看是否存在一个素数 a(a

·143·

信息技术与信息学竞赛

≤sqrt(P))是 P 的约数,如果不存在,该数就为素数。由于在此题中 1≤xi≤5000000,n≤20,所以要判断的数 P 不 会超过 100000000,sqrt(p)≤10000,因此,为了加快速度,我们可以用筛选法将 2~10000 之间的素数保存到一 个数组里(共 1229 个),这样速度估计将提高 5~6 倍。 注意:本题是要求使和为素数的情况有多少种,并不是求有多少种素数,比赛时就有很多同学胡乱判重而 注意 丢了 12 分;还有 1 不是素数,在判素数时要对 1 做特殊处理。 [程序]
program select const MaxN = 20; var N, M, i: Byte; ans, s: Longint; x: array[1 .. MaxN] of Longint; f: array[1 .. 10000] of Byte; p: array[1 .. 1229] of Integer; procedure Get_Prime; var i, j, s: Integer; begin s := 0; f[1] := 0; for i := 2 to 10000 do f[i] := 1; for i := 2 to 10000 do if f[i] = 1 then begin Inc(s); p[s] := i; j := 2 * i; while j <= 10000 do begin f[j] := 0; Inc(j, i) end; end end; procedure Work(S: Longint); var i: Integer; begin if S <= 10000 then Inc(ans, f[S]) else begin i := 1; while sqr(longint(p[i])) <= S do begin if S mod p[i] = 0 then Exit; Inc(i) end; Inc(ans) end end; procedure Search(d, pre: Byte); var i: Byte; begin for i := pre + 1 to N - (M - d) do begin Inc(S, x[i]); if d = M then Work(S)

·144·

第3章

算法与程序设计模块

else Search(d + 1, i); Dec(S, x[i]) end end; begin assign(input,'select.in');reset(input); assign(output,'select.out');rewrite(output); readln(N, M); for i := 1 to N do Read(x[i]); ans := 0; S := 0; Get_Prime; Search(1, 0); Writeln(ans); close(input);close(output); end.

例 3 附加的等式(equati.pas)。 【样例输入】 3 [3 个测试数据] 3123 [共有 3 个数参加运算] 3125 6 1 2 3 5 4 6 [共有 6 个数参加运算] 【样例输出】 1+2=3[参加运算的 3 个数能构成的加法运算,打印完结果之后要输出一个空行与下面的结果隔开] Can't find any equations. [不能构成任何加法运算等式] 1+2=3 1+3=4 1+4=5 1+5=6 2+3=5 2+4=6 1+2+3=6 注意: 注意:如果能构成多个加法运算等式,那么打印时要进行一下排列。 等式左边的数字个数小的放在前面,如果个数一样多,则按数字的值进行排列,从左到右,例如,1+2=3 与 1+3=4。为什么 1+2=3 要放在前面呢?因为(1,2)与(1,3)相比,在第一个数都为 1 的情况下,前者的第二个数 要小于后者的第二个数。 【算法分析】 面对这道题要勇敢,不要想太多。直接用控制深度的 DFS 搜即可(加剪枝)。要用组合公式。 [程序]
var a,b,que:array [1..100] of longint; n,m,i,j,k,p,q,sum,rear,max:longint; done:boolean; procedure qsort(l,r:longint); var i,j,mid,t:longint; begin i:=l;j:=r;mid:=a[(l+r)shr 1]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin

·145·

信息技术与信息学竞赛 t:=a[i];a[i]:=a[j];a[j]:=t; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; procedure choose(s,e,d,i:longint); var j:longint; begin if i<d then for j:=s to e do begin if (sum+a[j])<=max then begin inc(sum,a[j]); inc(rear); que[rear]:=a[j]; choose(j+1,e+1,d,i+1); dec(sum,a[j]); dec(rear); end end else begin for j:=s to e do if j<=n then if sum=a[j] then begin done:=true; for q:=1 to d-1 do begin write(que[q]); if q<>d-1 then write('+'); end; writeln('=',a[j]); end; end; end; procedure main(d:longint); var i,j:longint; begin sum:=0; rear:=0; choose(1,n-d+1,d,1); if d<>n then main(d+1); end; begin assign(input,'equati.in'); reset(input); assign(output,'equati.out'); rewrite(output); readln(m); for i:= 1 to m do begin done:=false; read(n); for j:= 1 to n do read(a[j]); readln; qsort(1,n); max:=a[n]; ·146·

第3章

算法与程序设计模块

main(3); if not done then writeln('Can''t find any equations.'); writeln; end; close(input); close(output); end.

练习题
生日蛋糕(cake.exe) 【题目描述】 7 月 17 日是 Mr.W 的生日,ACM-THU 为此要制作一个体积为 Nπ 的 M 层生日蛋糕,每层都是一个圆柱体 (如图 3-12 所示)。 设从下往上数第 i(1≤i≤M)层蛋糕是半径为 Ri, 高度为 Hi 的圆柱。 i<M 时, 当 要求 Ri>Ri+1 且 Hi>Hi+1。 由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积 Q 最小。 (令 Q= Sπ)

图 3-12

生日蛋糕图

编程,对给出的 N 和 M,找出蛋糕的制作方案(适当的 Ri 和 Hi 的值),使 S 最小。(除 Q 外,以上所 有数据皆为正整数) 【输入】 有两行,第一行为 N(N≤10000),表示待制作的蛋糕的体积为 Nπ;第二行为 M(M≤20),表示蛋糕的层 数为 M。 【输出】 仅一行,是一个正整数 S(若无解则 S=0)。 【样例输入】 100 2 【样例输出】 68 (附圆柱公式:体积 V=πR2H;侧面积 A’=2πRH;底面积 A=πR2 )

3.9

广度优先搜索

广度优先搜索是从初始结点开始, 应用算符生成第一层结点, 同时检查目标结点是否在这些生成的结点中。 若没有,再用算符将所有第一层的结点逐一扩展,得到第二层结点,并逐一检查第二层结点中是否包含目标结 点。若没有,再用算符逐一扩展第二层的所有结点……,如此依次扩展,检查下去,直至发现目标结点为止。 如果扩展完所有的结点,都没有发现目标结点,则问题无解。 在搜索的过程中,广度优先搜索对于结点是沿着深度的断层扩展的。如果要扩展第 n+1 层的结点,必须先 全部扩展完第 n 层的结点。那么,对于同一层结点来说,对于问题求解的价值是相同的。所以,这种搜索方法

·147·

信息技术与信息学竞赛

一定能保证找到最短的解序列。也就是说,第一个找到的目标结点,一定是应用算符最少的。因此,广度优先 搜索算法比较适合求最少步骤或者最短解序列的题目。 通常,广度优先搜索需用队列来帮助实现。 (1)process(state) (2)for each possible next state from this one (3)enqueue next state (4)search() (5)enqueue initial state (6)while !empty(queue) (7)state = get state from queue (8)process(state) 广度优先搜索得名于它的实现方式:每次都先将搜索树某一层的所有节点全部访问完毕后再访问下一层, 再利用先前的那棵搜索树。广度优先搜索以如图 3-13 所示顺序遍历。 首先,访问根节点;然后是搜索树第一层的所有节点;最后第二层、第三层……依次类推。 广度优先搜索中的结点是先产生的先扩展,而深度优先搜索中扩展结点的原则是先产生的后扩展,这两种 搜索方式的本质不同。

·148·

第3章

算法与程序设计模块

图 3-13

广度优先搜索顺序示意图

例 1 游戏(ahjo.pas)。 【题目描述】 在一种“麻将”游戏中,游戏是在一个有 W×H 格子的矩形平板上进行的。每个格子可以放置一个麻将牌, 也可以不放(如图 3-14 所示)。玩家的目标是将平板上的所有可通过一条路径相连的两张相同的麻将牌,从平板 上移去。最后,如果能将所有牌移出平板,则算过关。 这个游戏中的一个关键问题是:两张牌之间是否可以被一条路径所连接,该路径满足以下两个特性: (1)它由若干条线段组成,每条线段要么是水平方向,要么是垂直方向。 (2)这条路径不能横穿任何一个麻将牌(但允许路径暂时离开平板)。

图 3-14

麻将游戏图

这是一个例子:在(1,3)的牌和在(4,4)的牌可以被连接。(2,3)和(3,4)不能被连接。 你的任务是编一个程序,检测两张牌是否能被一条符合以上规定的路径所连接。 【输入】 第一行为一整数 N 表示有 N 组测试数据。 每组测试数据的第一行有两个整数 w, h ‘X’,否则是一个空格。 平板上最左上角格子的坐标为(1,1),最右下角格子的坐标为(w,h)。接下来的若干行,每行有四个数 x1,y1,x2,y2,且满足 1≤x1,x2≤w,1≤y1,y2≤h,表示两张牌的坐标(这两张牌的坐标总是不同的)。如果出 现连续四个 0,则表示输入结束。 【输出】 输出文件中,对于每一对牌输出占一行,为连接这一对牌的路径最少包含的线段数。如果不存在路径则输 出 0。 【样例输入】 1 54 XXXXX X X XXX X XXX 2353 1344 (1≤w, h≤75) ,

表示平板的宽和高。接下来 h 行描述平板信息,每行包含 w 个字符,如果某格子有一张牌,则这个格子上有个

·149·

信息技术与信息学竞赛

2334 0000 【样例输出】 4 3 0 【算法分析】 从起点出发,每次扩展就是沿上下左右四个方向闯下去,直到碰到一张牌或者边界为止。这里的“边界” 应是原棋盘再往外的一圈,因为连线可以超出棋盘。 如果碰到的牌正好是终点,那么 BFS 成功。另外还要注意, 输出的应是路径上线段的条数,而不是拐的弯数。 [程序]
program mahjo; const maxh=75; maxw=75; var map:array[-1..maxh+2,-1..maxw+2]of char; qx,qy:array[1..(maxh+4)*(maxw+4)+1]of shortint; seg:array[-1..maxh+2,-1..maxw+2]of word; h,w,i,j,a,b:shortint; n,t,f,r,s:word; procedure add(x,y:shortint;s:word); begin if seg[x,y]=0 then begin inc(r);qx[r]:=x;qy[r]:=y;seg[x,y]:=s; end; end; begin assign(input,'mahjo.in');reset(input); assign(output,'mahjo.out');rewrite(output); read(n); for t:=1 to n do begin read(w,h); for i:=-1 to h+2 do begin map[i,-1]:='X';map[i,0]:=' ';map[i,w+1]:=' ';map[i,w+2]:='X';end; for i:=0 to w+1 do begin map[-1,i]:='X';map[0,i]:=' ';map[h+1,i]:=' ';map[h+2,i]:='X';end; for i:=1 to h do begin readln; for j:=1 to w do read(map[i,j]); end; repeat fillchar(seg,sizeof(seg),0); read(qy[1],qx[1],b,a); if qx[1]=0 then break; f:=0;r:=1; repeat inc(f);if(f>1)and(map[qx[f],qy[f]]='X')thencontinue;s:=seg[qx[f], qy[f]]+1; i:=qx[f];j:=qy[f];repeat dec(i);add(i,j,s);until map[i,j]='X'; i:=qx[f];j:=qy[f];repeat dec(j);add(i,j,s);until map[i,j]='X'; i:=qx[f];j:=qy[f];repeat inc(i);add(i,j,s);until map[i,j]='X'; i:=qx[f];j:=qy[f];repeat inc(j);add(i,j,s);until map[i,j]='X'; until (f=r) or (seg[a,b]>0);

·150·

第3章 writeln(seg[a,b]); until false; end; close(input);close(output); end.

算法与程序设计模块

例 2 冰原探险(ice.pas)。 【题目描述】 传说中,南极有一片广阔的冰原,在冰原下藏有史前文明的遗址。整个冰原被横竖划分成了很多个大小相 等的方格。在这个冰原上有 N 个大小不等的矩形冰山,这些巨大的冰山有着和南极一样古老的历史,每个矩形 冰山至少占据一个方格,且其必定完整地占据方格。冰山和冰山之间不会重叠,也不会有边或点相连。以下两 种情况均是不可能出现的(如图 3-15 所示)。

(1) 图 3-15

(2) 冰原探险示意图(1)

ACM 探险队在经过多年准备之后决定在这个冰原上寻找遗址。根据他们掌握的资料,在这个冰原上一个 大小为一格的深洞中,藏有一个由史前人类制作的开关。而唯一可以打开这个开关的是一个占据接近一格的可 移动的小冰块。显然,在南极是不可能有这样小的独立冰块的,所以这块冰块也一定是史前文明的产物。他们 在想办法把这个冰块推到洞里去,这样就可以打开一条通往冰原底部的通道,发掘史前文明的秘密。冰块的起 始位置与深洞的位置均不和任何冰山相邻。 这个冰原上的冰面和冰山都是完全光滑的,轻轻地推动冰块就可以使这个冰块向前滑行,直到撞到一座冰 山就在它的边上停下来。冰块可以穿过冰面上所有没有冰山的区域,也可以从两座冰山之间穿过(如图 3-16 所 示)。冰块只能沿网格方向推动。 请你帮助他们以最少的推动次数将冰块推入深洞中。

(3) 图 3-16

(4) 冰原探险示意图(2)

【输入】 输入文件第一行为冰山的个数 N(1≤N≤4000),第二行为冰块开始所在的方格坐标 X1,Y1,第三行为深 洞所在的方格坐标 X2,Y2,以下 N 行每行有四个数,分别是每个冰山所占的格子左上角和右下角坐标 Xi1,Yi1,Xi2,Yi2,如图 3-17 所示。 【输出】 输出文件仅包含一个整数,为最少推动冰块的次数。如果无法将冰块推入深洞中,则输出 0。 【样例输入】

·151·

信息技术与信息学竞赛

2 11 55 1333 6284 【样例输出】 3

·152·

第3章

算法与程序设计模块

(5 )
图 3-17 冰原探险示意图(3)

【算法分析】 很明显,该题应当采取的方法是广度优先搜索算法。 因为冰山没有相接的情况,所以可以不要记下具体的位置,对于同一个冰山侧面的任何位置,朝固定方向 推冰块的效果是一样的。 这样在判重的时候也十分简单,只要用这样一个数组:already : array[1..4000, 1..4]of boolean。already[i, j] 表示第 i 个冰山的第 j 个侧面是否到达过。 我们将目的地当作第 n+1 个冰山,这样在扩展的时候只要碰到第 n+1 个冰山就出解了。对冰山按两个坐标 轴的方向分别排序,可以进一步减少扩展时间。 [程序]
program ice; const filein = 'ice.in'; fileout = 'ice.out'; up = 1;left = 2;right = 3;down = 4; move : array[1..4, 1..2]of byte = ((left, right), (up, down), (up, down), (left, right)); move2 : array[1..4, 1..2]of byte = ((up, down), (left, right), (left, right), (up, down)); type ticeberg = record x1, y1, x2, y2 : integer; end; tstate = record ibid : word; bor : byte; end; var already : array[1..4000, 1..4]of boolean; iceberg : array[1..4001]of ticeberg; a1, a2 : array[1..1000]of tstate; step, n, q1, q2 : word; srcx, srcy, tarx, tary : integer; time : longint; procedure initialize; var f : text; b : boolean; i : word; begin assign(f, filein); reset(f); readln(f, n); readln(f, srcx, srcy); readln(f, tarx, tary); b := true; for i := 1 to n do with iceberg[i] do readln(f, x1, y1, x2, y2); close(f);

·153·

信息技术与信息学竞赛 with iceberg[n + 1] do begin x1 := tarx; x2 := x1; y1 := tary; y2 := y1; end; end; procedure out; var f : text; begin assign(f, fileout); rewrite(f); writeln(f, step); close(f); halt; end; procedure expandsrc(p : byte; var p1, p2 : word); var i, j : word; m1, m2 : integer; begin p1 := 0; p2 := 0; j := 0; if (p = up) or (p = down) then begin m1 := -maxint; m2 := maxint; for i := 1 to n + 1 do begin if (iceberg[i].x1 <= srcx) and (iceberg[i].x2 >= srcx) then if (iceberg[i].y2 + 1 < srcy) and (iceberg[i].y2 + 1 > m1) then begin m1 := iceberg[i].y2; p1 := i; end; if (iceberg[i].x1 <= srcx) and (iceberg[i].x2 >= srcx) then if (iceberg[i].y1 - 1 > srcy) and (iceberg[i].y1 - 1 < m2) then begin m2 := iceberg[i].y1; p2 := i; end; end; end else begin m1 := -maxint; m2 := maxint; for i := 1 to n + 1 do begin if (iceberg[i].y1 <= srcy) and (iceberg[i].y2 >= srcy) then if (iceberg[i].x2 + 1 < srcx) and (iceberg[i].x2 + 1 > m1) then begin m1 := iceberg[i].x2; p1 := i; end; if (iceberg[i].y1 <= srcy) and (iceberg[i].y2 >= srcy) then if (iceberg[i].x1 - 1 > srcx) and (iceberg[i].x1 - 1 < m2) then begin m2 := iceberg[i].x1; p2 := i; end; end; end; if (p1 = n + 1) or (p2 = n + 1) then out; end; procedure expand(id : word; q : byte; var p1, p2 : word); var i : word; x, y, m1, m2 : integer; begin p1 := 0; p2 := 0; case q of up : begin x := iceberg[id].x1; y := iceberg[id].y1 - 1; end; down : begin x := iceberg[id].x2; y := iceberg[id].y2 + 1; end; right : begin x := iceberg[id].x2 + 1; y := iceberg[id].y2; end; ·154·

第3章

算法与程序设计模块

left : begin x := iceberg[id].x1 - 1; y := iceberg[id].y1; end; end; if (q = left) or (q = right) then begin m1 := -maxint; m2 := maxint; for i := 1 to n + 1 do begin if (iceberg[i].x1 <= x) and (iceberg[i].x2 >= x) then if (iceberg[i].y2 + 1 < y) and (iceberg[i].y2 + 1 > m1) then begin m1 := iceberg[i].y2; p1 := i; end; if (iceberg[i].x1 <= x) and (iceberg[i].x2 >= x) then if (iceberg[i].y1 - 1 > y) and (iceberg[i].y1 - 1 < m2) then begin m2 := iceberg[i].y1; p2 := i; end; end; end else begin m1 := -maxint; m2 := maxint; for i := 1 to n + 1 do begin if (iceberg[i].y1 <= y) and (iceberg[i].y2 >= y) then if (iceberg[i].x2 + 1 < x) and (iceberg[i].x2 + 1 > m1) then begin m1 := iceberg[i].x2; p1 := i; end; if (iceberg[i].y1 <= y) and (iceberg[i].y2 >= y) then if (iceberg[i].x1 - 1 > x) and (iceberg[i].x1 - 1 < m2) then begin m2 := iceberg[i].x1; p2 := i; end; end; end; if (p1 = n + 1) or (p2 = n + 1) then out; end; procedure firstexpand; var i, b : byte; next1, next2 : word; begin step := 1; for i := up to left do begin expandsrc(i, next1, next2); b := 5 - move2[i, 1]; if next1 <> 0 then begin inc(q1); a1[q1].ibid := next1; a1[q1].bor := b; already[next1, b] := true end; b := 5 - move2[i, 2]; if next2 <> 0 then begin inc(q1); a1[q1].ibid := next2; a1[q1].bor := b; already[next2, b] := true end; end; end; procedure mainexpand; ·155·

信息技术与信息学竞赛 var i : word; j, b : byte; next1, next2 : word; begin repeat inc(step); for i := 1 to q1 do begin expand(a1[i].ibid, a1[i].bor, next1, next2); b := 5 - move[a1[i].bor, 1]; if next1 <> 0 then if not already[next1, b] then begin inc(q2); a2[q2].ibid := next1; a2[q2].bor := b; already[next1, b] := true end; b := 5 - move[a1[i].bor, 2]; if next2 <> 0 then if not already[next2, b] then begin inc(q2); a2[q2].ibid := next2; a2[q2].bor := b; already[next2, b] := true end end; if q2 = 0 then break; a1 := a2; q1 := q2; q2 := 0; until false; end; procedure outfailed; var f : text; begin assign(f, fileout); rewrite(f); writeln(f, 0); close(f); end; begin initialize; firstexpand; mainexpand; outfailed; end.

练习题
1.聪明的打字员(clever.pas) 【题目描述】 阿兰是某机密部门的打字员,她接到一个任务:需要在一天之内输入几百个长度固定为 6 的密码。当然, 她希望输入的过程中敲击键盘的总次数越少越好。 不幸的是,出于保密的需要,该部门用于输入密码的键盘是特殊设计的,键盘上没有数字键,而只有以下
·156·

第3章

算法与程序设计模块

6 个键:Swap0、Swap1、Up、Down、Left、Right,为了说明这 6 个键的作用,我们先定义录入区的 6 个位置 的编号,从左至右依次为 1、2、3、4、5、6。下面列出每个键的作用: Swap0 按 Swap0 键,光标位置不变,将光标所在位置的数字与录入区的 1 号位置的数字(左起第一个数 字)交换。如果光标已经处在录入区的 1 号位置,则按 Swap0 键之后,录入区的数字不变; Swap1 按 Swap1 键,光标位置不变,将光标所在位置的数字与录入区的 6 号位置的数字(左起第六个数 字)交换。如果光标已经处在录入区的 6 号位置,则按 Swap1 键之后,录入区的数字不变; Up 按 Up 键,光标位置不变,将光标所在位置的数字加 1(除非该数字是 9)。例如,如果光标所在位 置的数字为 2,按 Up 键之后,该处的数字变为 3;如果该处数字为 9,则按 Up 键之后,数字不变,光标位置 也不变; Down 按 Down 键,光标位置不变,将光标所在位置的数字减 1(除非该数字是 0),如果该处数字为 0, 则按 Down 键之后,数字不变,光标位置也不变; Left 按 Left 键,光标左移一个位置,如果光标已经在录入区的 1 号位置(左起第一个位置)上,则光标 不动; Right 按 Right 键,光标右移一个位置,如果光标已经在录入区的 6 号位置(左起第六个位置)上,则光 标不动。 当然,为了使这样的键盘发挥作用,每次录入密码之前,录入区总会随机出现一个长度为 6 的初始密码, 而且光标固定出现在 1 号位置上。当巧妙地使用上述 6 个特殊键之后,可以得到目标密码,这时光标允许停在 任何一个位置。 现在,阿兰需要你的帮助,编写一个程序,求出录入一个密码最少需要的击键次数。 【输入】 文件仅一行,含有两个长度为 6 的数,前者为初始密码,后者为目标密码,两个密码之间用一个空格隔开。 【输出】 文件仅一行,含有一个正整数,为最少需要的击键次数。 【样例输入】 123456 654321 【样例输出】 11 2.Sramoc 问题(sramoc.pas) 【题目描述】 Sramoc ( K,M ) 表示用数字 0,1,2…,K-1 组成的自然数中能被 M 整除的最小数。给定 K、M,求 Sramoc ( K,M )。例如,K=2,M=7 的时候,Sramoc(2,7) = 1001。 【输入】 从文件 SRAMOC.IN 读入数据。第一行为两个整数 K、M 满足 2≤K≤10、1≤M≤1000。 【输出】输出 Sramoc(K,M) 到 SRAMOC.OUT。 【样例输入】 2 7 【样例输出】 1001

·157·

信息技术与信息学竞赛

3.10

双向广度优先搜索

所谓双向搜索指的是搜索沿两个方向同时进行。正向搜索:从初始结点向目标结点方向搜索;逆向搜索: 从目标结点向初始结点方向搜索;当两个方向的搜索生成同一子结点时终止此搜索过程。 1.广度双向搜索算法 广度双向搜索通常有两种方法: (1)两个方向交替扩展; (2)选择结点个数较少的那个力向先扩展。方法(2)克服了两个方向结点的生成速度不平衡的状态,明 显提高了效率。 2.算法说明 设置两个队列 c:array[0..1,1..maxn] of jid, 分别表示正向和逆向的扩展队列; 设置两个头指针 head:array[0..1] of integer,分别表示正向和逆向当前将扩展结点的头指针;设置两个尾指针 tail:array[0..1] of integer,分别表示 正向和逆向的尾指针。(maxn 表示队列最大长度) 3.算法描述 (1)主程序代码
repeat {选择节点数较少且队列未空、未满的方向先扩展} if (tail[0]<=tail[1]) and not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0); if (tail[1]<=tail[0]) and not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1); {如果一方搜索终止,继续另一方的搜索,直到两个方向都终止} if not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0); if not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1); Until((head[0]>=tail[0])or(tail[0]>=maxn))And ((head[1]>=tail[1])or (tail[1]>=maxn)).

(2)expand(st:0..1)程序代码
inc(head[st]; 取出队列当前待扩展的结点 c[st,head[st]] for i:=1 to maxk do begin if tail[st]>=maxn then exit; inc(tail[st]); 产生新结点; check(st);{检查新节点是否重复} end;

(3)check(st:0..1)程序代码
for i:=1 to tail[st]-1 do if c[st,tail[st]]^.*=c[st,i]^.* then begin dec(tail[st]);exit end; bool(st);{如果节点不重复,再判断是否到达目标状态}

(4)bool(st:0..1)程序代码
for i:=1 to tail[1-st] do if c[st,tail[st]]^.*=c[1-st,i]^.* then print(st,tail[st],i); {如果双向搜索相遇(即得到同一节点),则输出结果}

(5)print(st,tail,k)程序代码
if st=0 then begin print0(tail);print1(k) end; ·158·

第3章

算法与程序设计模块

else begin print0(k);print1(tail) end;

(6)print0(m)程序代码
if m<>0 then begin print(c[0,m]^.f);输出 c[0,m]^.* end; {输出正方向上产生的结点}

(7)print1(m)程序代码
n:=c[1,m]^.f while m<>0 begin 输出 c[1,n]^.*; n:=c[1,n]^.f; end

{输出反方向上产生的结点} 例 1 字串变换(word.pas)。 【题目描述】 已知有两个字串 A$,B$及一组字串变换的规则: 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’。 共进行了 3 次变换,使得 A$变换为 B$。 【输入】 输入文件名为 word .in。

·159·

信息技术与信息学竞赛

格式: A$,B$ A1$ → B1$ A2$ → B2$ ……

变换规则

注意: 注意:所有字符串长度的上限为 255。 【输出】 输出文件名为 word .out。若在 30 步(包含 30 步)以内能将 A$变换为 B$,则向 word .out 输出最少的变换 步数;否则向 word.out 输出‘ERROR!’。 【样例输入】 abcd xyz abc xu ud y y yz 【样例输出】 3 【算法分析】 本题是典型的广度优先搜索的例子,但如果只采用正向搜索,某些情况下计算量过大,速度过慢,故采取 双向搜索且判重并适当剪枝,效果较好。 [程序]
program word const maxn=2300; type node=record {定义节点数据类型} str:string[115];dep:byte; end; {str 表示字串, 其长度不会超过 115 (长度超过 115 的字串不可能通过变换成为目标字串, 因为题目限定变换 10 次之内, 且串长不超过 20, 即起始串最多可经过 5 次变换时增长, 中间串的最大长度为 20+5×19=115, 否则经过余下的步数不可能变为长度不超过 20 的目标串),dep 表示深度} ctype=array[1..maxn]of ^node; bin=0..1; var maxk:byte;c:array [0..1]of ctype; x0:array[0..6,0..1]of string[20]; filename:string; open,closed:array [0..1] of integer; procedure Init; {读取数据,初始化} var f:text;temp:string;i,j:integer; begin for i:=0 to 1 do for j:=1 to maxn do new(c[i,j]); write('Input filename:');readln(filename); assign(f,filename);reset(f);i:=0; while not eof(f) and (i<=6) do begin readln(f,temp); x0[i,0]:=copy(temp,1,pos(' ',temp)-1); x0[i,1]:=copy(temp,pos(' ',temp)+1,length(temp)); inc(i); end; maxk:=i-1;close(f); end; procedure calc; var i,j,k:integer;st:bin; d:string;f:text; procedure bool(st:bin); {判断是否到达目标状态或双向搜索相遇}

·160·

第3章

算法与程序设计模块

var i:integer; begin if x0[0,1-st]=c[st,closed[st]]^.str then begin {如果到达目标状态,则输出结果,退出} writeln(c[st,closed[st]]^.dep); halt; end; for i:=1 to closed[1-st] do if c[st,closed[st]]^.str=c[1-st,i]^.str then begin {如果双向搜索相遇(即得到同一节点), 则输出结果(2 个方向搜索的步数之和),退出} writeln(c[st,closed[st]]^.dep+c[1-st,i]^.dep); halt; end; end; procedure checkup(st:bin); {判断节点是否与前面重复} var i:integer; begin for i:=1 to closed[st]-1 do if c[st,i]^.str=c[st,closed[st]]^.str then begin dec(closed[st]);exit; {如果节点重复,则删除本节点} end; bool(st); {如果节点不重复,再判断是否到达目标状态} end; procedure expand(st:bin); {扩展产生新节点} var i,j,k,lx,ld:integer; begin inc(open[st]);d:=c[st,open[st]]^.str;{队首节点出队} k:=c[st,open[st]]^.dep;ld:=length(d); for i:=1 to maxk do begin {从队首节点(父节点)出发产生新节点(子节点)} lx:=length(x0[i,st]); for j:=1 to ld do begin if(copy(d,j,lx)=x0[i,st])and(length(copy(d,1,j-1)+x0[i, 1-st]+copy (d,j+lx,ld))<=115)then begin {如果新节点的串长超过 115,则不扩展!即剪掉此枝} if closed[st]>=maxn then exit; {如果队列已满,只好退出} inc(closed[st]); {新节点入队} c[st,closed[st]]^.str:=copy(d,1,j-1)+x0[i,1-st]+copy(d,j+lx,ld); c[st,closed[st]]^.dep:=k+1; {子节点深度=父节点深度+1} checkup(st); {检查新节点是否重复} end; end; end; end; begin for st:=0 to 1 do begin {正向(st=0)逆向(st=1)搜索节点队列初始化} open[st]:=0;closed[st]:=1; c[st,closed[st]]^.str:=x0[0,st];c[st,closed[st]]^.dep:=0; bool(st); end; repeat {选择节点数较少且队列未空、未满、深度未达到 10 的方向先扩展} if (open[0]<=open[1]) and not ((open[0]>=closed[0]) or (closed[0]>=maxn) or (c[0,closed[0]]^.dep>10)) then expand(0); if (open[1]<=open[0]) and not ((open[1]>=closed[1]) or (closed[1]>=maxn) or (c[1,closed[1]]^.dep>10)) then expand(1); {如果一方搜索终止,继续另一方的搜索,直到两个方向都终止} if not ((open[0]>=closed[0]) or (closed[0]>=maxn) or (c[0,closed[0]]^.dep>10)) then expand(0); if not ((open[1]>=closed[1]) or (closed[1]>=maxn) or (c[1,closed[1]]^.dep>10)) then expand(1);

·161·

信息技术与信息学竞赛 until(open[0]>=closed[0])or(c[0,closed[0]]^.dep>10)or(closed[0]>=maxn) and (closed[1]>=maxn) or (open[1]>=closed[1]) or (c[1,closed[1]]^.dep>10); {终止条件:任一方队空(无解)或搜索深度超过 10(10 步内无解)或双方均溢出(可能有解也可能无解,应尽量避免, 要尽量把节点数组开大一点,采用双向搜索,采取剪枝措施等)} end; begin init; calc; writeln('NO ANSWER!') end .

【点评】 基本题(较难)考察队列、(双向)广度优先搜索算法及字符串的运算,基本上可以考察出参赛者的数据 结构和算法水平。 例 2 魔板(magic.pas)。 【题目描述】 在成功地发明了魔方之后,拉比克先生发明了它的二维版本,称作魔板。这是一张有 8 个大小相同的格子 的魔板,如图 3-18 所示。 1 8 2 7
图 3-18

3 6
魔板示意图

4 5

我们知道魔板的每一个方格都有一种颜色。这 8 种颜色用前 8 个正整数来表示。可以用颜色的序列来表示 一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次取出整数,构成一个颜色序列。对于图 3-18 的魔 板状态,我们用序列(1,2,3,4,5,6,7,8)来表示。这是基本状态。 这里提供 3 种基本操作,分别用大写字母 A、B、C 来表示(可以通过这些操作改变魔板的状态)。 A:交换上下两行; B:将最右边的一行插入最左边; C:魔板中央作顺时针旋转。 下面是对 3 种基本状态进行操作的示范,如图 3-19 所示。
8 1
(A)

7 2

6 3

5 4
(B)

4 5

1 8

2 7

3 6
(C)

1 8

7 6

2 3

4 5

图 3-19

魔板状态示意图

对于每种可能的状态,这 3 种基本操作都可以使用。 你要编程计算用最少的基本操作完成基本状态到特殊状态的转换,输出基本操作序列。 【输入】 只有一行,包括 8 个整数,用空格分开(这些整数在范围 1~8 之间),表示目标状态。 【输出】
Line 1: Line 2: 包括一个整数,表示最短操作序列的长度 在字典序中最早出现的操作序列,用字符串表示,除最后一行外,每行输出 60 个字符

【样例输入】
26845731 【样例输出】 7 BCABCCB 【算法分析】
·162·

第3章

算法与程序设计模块

双向广度优先搜索,先从目标状态向前搜索 6 层再进行从初始状态向目标状态的搜索,这样状态空间大大 减少。

练习题
九数码游戏(num9.pas) 【题目描述】 这是一个很古老的游戏了:有一个 3 × 3 的活动拼盘(如图 3-20 所示),方格上写有 0~8 这九个数字。

3 2 4
图 3-20

7 6 8

5 1 0

九数码游戏示意图

利用拼盘背后的旋钮,游戏者每次可以进行两种操作之一:将拼盘外围的 8 个方格按顺时针挪一个位置; 将中间一行向右移动一个位置,最右边的方格被移到最左边,如图 3-21 所示。 例如:
3 2 4 7 6 8 5 1 0 图 3-21 进行操作 1 2 4 8 3 6 0 7 5 1 进行操作 2 2 5 8 3 4 0 7 6 1

九数码游戏操作示意图

给你一个拼盘的初始状态,你能用最少的操作次数把拼盘变成图 3-22 所示的目标状态吗? 0 3 6
图 3-22

1 4 7

2 5 8

九数码游戏目标状态示意图

【输入】 输入文件中包含 3 行 3 列 9 个数,同行的相邻两数用空格隔开,表示初始状态每个方格上的数字。初始状 态不会是目标状态。 【输出】 如果目标状态无法达到,则输出“UNSOLVABLE”(引号不输出)。否则,第一行是一个整数 S,表示最 少的操作次数。接下来 4 × (S + 1)行,每四行表示一个状态:前 3 行每行 3 个整数,相邻两数用空格隔开,表 示每个方格上的数字,第四行是一个空行,作为分隔。第一个状态必须是初始状态,最后一个状态必须是目标 状态。

3.11

有趣的数学问题

例 1 神奇口袋(bag.pas)。 【题目描述】 Pòlya 获得了一个奇妙的口袋,上面写着人类难以理解的符号。Pòlya 看得入了迷,冥思苦想,发现了一个 神奇的模型(被后人称为 Pòlya 模型)。为了生动地讲授这个神奇的模型,他带着学生们做了一个虚拟游戏。 + a2 游戏开始时, 袋中装入 a1 个颜色为 1 的球, 个颜色为 2 的球, at 个颜色为 t 的球, …, 其中 ai∈Z (1≤i≤t)。

·163·

信息技术与信息学竞赛

游戏开始后,每次严格进行操作:从袋中随机的抽出一个小球(袋中所有小球被抽中的概率相等),Pòlya 独 自观察这个小球的颜色后将其放回,然后再把 d 个与其颜色相同的小球放到口袋中。 Pòlya 一个游戏过程将会产生一个颜色序列(c1,c2,…,cn, …)。 设 ci 表示第 i 次抽出的小球的颜色(1≤ci≤t), 把游戏开始时 t 种颜色的小球每一种的个数 a1,a2, …,at 告诉了所有学生。然后他问学生:一次游戏过程产生的 颜色序列满足下列条件的概率有多大?

cx1 = y1 , cx2 = y2 ,L, cxi = yi , L, cxn = yn
其中,0<x1<x2<…<xn,1≤yi≤t。换句话说,已知(t,n,d,a1,a2,…,at, x1,y1,x2,y2,…,xn,yn),你要回答有 多大的可能性会发生下面的事件:“对所有 k,1≤k≤n,第 xk 次抽出的球的颜色为 yk”。 【输入】 第一行有 3 个正整数 t,n,d;第二行有 t 个正整数 a1,a2, …,at,表示游戏开始时口袋里 t 种颜色的球,每 种球的个数。 以下 n 行,每行有两个正整数 xi,yi,表示第 xi 次抽出颜色为的 yi 球。 【输出】 要求用分数形式输出(显然此概率为有理数)。输出文件包含一行,格式为:分子/分母。同时,要求输出 最简形式(分子分母互质)。特别是概率为 0 应输出 0/1,概率为 1 应输出 1/1。 【样例 1】 【输入】 231 11 11 22 31 【输出】 1/12 【样例 1 说明】 初始时,两种颜色球数分别为(1, 1),取出色号为 1 的球的概率为 1/2;第二次取球之前,两种颜色球数分 别为(2, 1),取出色号为 2 的球的概率为 1/3;第三次取球之前,两种颜色球数分别为(2, 2),取出色号为 1 的球 的概率为 1/2,所以 3 次取球的总概率为 1/12。 【样例 2】 【输入】 312 111 51 【输出】 1/3 【数据规模和约定】 1≤t,n≤1000, 1≤ak ,d≤10, 1≤x1<x2<…<xn≤10000, 1≤yk≤t 【评分方法】 本题没有部分分,你的程序的输出只有和我们的答案完全一致才能获得满分,否则不 得分。 【算法分析】 】 考察的只是很简单的数学知识+高精度乘法。整个大框架就是乘法原理,对于每次取球,如果没有在 xi 中, 那么这次操作称为“自由取球”,否则将颜色 yi 的球的数量 a/此时球的总数作为乘数乘到结果中,并将颜色 yi 的球的数量+d,称作“定向取球”。 可以证明,自由取球对任意球被取到的几率 Pi 没有影响,证明很简单。可以忽略掉所有的自由取球操作, 对于最后分数化简的问题,因为分子分母最多只有 20000,所以只要建立一个 20000 以内的素数表,连高精度 除法都不需要,只要先将分子分母都化简掉再高精度乘起来输出就行了。 [程序]
·164·

第3章 type hp = array [0..1100] of longint; var ca,cb :hp; j:longint; t,n,d,i,x,y,sum,npl,pa,pb:longint; a :array [1..1000] of longint; prime :array [1..20000] of boolean; p :array [1..3000] of longint; xa,xb:array [1..1000] of longint; procedure mult(var cx:hp; mm:longint); var i,x:longint; begin x:=0; for i:= 1 to cx[0] do begin x:=cx[i]*mm+x; cx[i]:=x mod 10000; x:=x div 10000; end; while x>0 do begin

算法与程序设计模块

inc(cx[0]); cx[cx[0]]:= x mod 10000; x:=x div 10000; end; end; procedure print(var re:hp); var i,j:longint; begin write(re[re[0]]); for i:= re[0]-1 downto 1 do if re[i]=0 then write('0000') else begin for j:= 1 to 3-trunc(ln(re[i])/ln(10)) do write(0); write(re[i]); end; end; begin assign(input,'bag.in'); reset(input); assign(output,'bag.out'); rewrite(output); fillchar(prime,sizeof(prime),true); prime[1]:=false; i:=2; while i<=20000 do begin inc(npl); p[npl]:=i; j:=i+i; while j<=20000 do begin prime[j]:=false; inc(j,i); end; inc(i); while (i<=20000) and not prime[i] do inc(i); end; readln(t,n,d); for i:= 1 to t do begin

·165·

信息技术与信息学竞赛 read(a[i]); inc(sum,a[i]); end; readln; for i:= 1 to n do begin readln(x,y); xa[i]:=a[y]; xb[i]:=sum; inc(sum,d); inc(a[y],d); end; for i:= 1 to npl do begin pa:=1; pb:=1; while (pa<=n) and (pb<=n) do begin while (pa<=n) and (xa[pa] mod p[i]<>0) do inc(pa); while (pb<=n) and (xb[pb] mod p[i]<>0) do inc(pb); if (pa<=n) and (pb<=n) then begin xa[pa]:=xa[pa] div p[i]; xb[pb]:=xb[pb] div p[i]; end; end; end; ca[0]:=1;ca[1]:=1; cb[0]:=1;cb[1]:=1; for i:= 1 to n do begin mult(ca,xa[i]); mult(cb,xb[i]); end; print(ca); write('/'); print(cb); writeln; close(input); close(output); end.

例 2 出栈序列统计(stack.pas)。 【题目描述】 栈是常用的一种数据结构,有 n 个元素在栈顶端一侧等待进栈,栈顶端另一侧是出栈序列。你已经知道栈 的操作有两种:push 和 pop,前者是将一个元素进栈,后者是将栈顶元素弹出。现在要使用这两种操作,由一 个操作序列可以得到一系列的输出序列。请你编程求出对于给定的 n,计算并输出由操作数序列 1,2,…,n,经过 一系列操作可能得到的输出序列总数。 【输入】 就一个数 n(1≤n≤1000)。 【输出】 一个数,即可能输出序列的总数目。 【样例输入】 3 【样例输出】 5 【算法分析】 】 从排列组合的数学知识可以对此类问题加以解决。我们先对 n 个元素在出栈前可能的位置进行分析,它们 有 n 个等待进栈的位置,全部进栈后在栈里也占 n 个位置,也就是说 n 个元素在出栈前最多可能分布在 2×n 位

·166·

第3章

算法与程序设计模块

置上。 出栈序列其实是从这 2n 个位置上选择 n 个位置进行组合, 根据组合的原理, 2n 个位置选 n 个, C(2n,n) 从 有 个。但是这里不同的是有许多情况是重复的,每次始终有 n 个连续的空位置,n 个连续的空位置在 2n 个位置里 有 n+1 种,所以重复了 n+1 次。因此出栈序列的种类数目为(即公式): ans=c(2n,n)/(n+1)=2n×(2n-1) ×(2n-2)…×(n+1)/n!/(n+1)=2n×(2n-1) ×(2n-2) ×…×(n+2)/n! 考虑到这个数据可能比较大,所以用高精度运算来计算这个结果。 [程序]
program stack; uses math; type arr=array[0..5000] of longint; var n:longint; i,j:longint; ans:arr; function chu(a:arr;b:longint):arr; var i1,i2,p:longint; c:arr; begin fillchar(c,sizeof(c),0); p:=a[a[0]]; i1:=a[0]; repeat if p<b then begin p:=p*10; i1:=i1-1; p:=p+a[i1]; continue; end; c[i1]:=p div b; p:=p mod b; p:=p*10; i1:=i1-1; p:=p+a[i1]; until i1=0; for i1:=a[0] downto 1 do begin if c[i1]<>0 then begin c[0]:=i1; break; end; end; chu:=c; end; function cheng2(a:arr;b:longint):arr; var i1:longint; begin for i1:=1 to a[0] do a[i1]:=a[i1]*b; for i1:=1 to a[0]+10 do begin a[i1+1]:=a[i1+1]+a[i1] div 10; a[i1]:=a[i1] mod 10; end; for i1:=a[0]+10 downto 1 do if a[i1]>0 then begin

·167·

信息技术与信息学竞赛 a[0]:=i1; break; end; cheng2:=a; end; function cc(a,b:longint):arr; var i1,i2:longint; d:arr; begin fillchar(d,sizeof(d),0); d[0]:=1; d[1]:=1; for i1:=b downto b-a+1 do begin d:=cheng2(d,i1); end; for i1:=a downto 1 do d:=chu(d,i1); cc:=d; end; function jia(a,b:arr):arr; var i1:integer; begin for i1:=1 to max(a[0],b[0]) do a[i1]:=a[i1]+b[i1]; for i1:=1 to max(a[0],b[0])+2 do begin a[i1+1]:=a[i1+1]+a[i1] div 10; a[i1]:=a[i1] mod 10; end; repeat i1:=i1-1; until a[i1]<>0; a[0]:=i1; jia:=a; end; begin assign(input,'stack.in');reset(input); assign(output,'stack.out');rewrite(output); readln(n); ans[0]:=1; ans[1]:=1; ans:=chu(cc(n,2*n),n+1); for i:=ans[0] downto 1 do write(ans[i]); close(input); close(output); end.

例 3 称硬币(coin.pas)。 【题目描述】 】 现在,有从 1~N 编了号的 N 块硬币,其中有一块是假的,重量与真硬币不同。所有的真硬币的重量都一 样。现在,已经用天平称了 K 次,要你求出哪一块硬币是假的。 【输入】 】 第一行有两个整数 N 和 K(1≤N,K≤100)。接下来的 2K 行描述已经称了的硬币的情况,每个情况用两 行表示:第一行有一个整数 Pi,(1≤Pi≤N/2),表示放在天平每个盘子中的硬币的个数,接下来的 Pi 个整数 表示左盘中的硬币的编号,再接下来的 Pi 个整数表示右盘中的硬币的编号。第二行有“<”、“>”、“=”字 符,表示这次称量的结果。“<”表示左盘中的硬币比右盘中的硬币轻;“>”表示左盘中的硬币比右盘中的硬 币重;“=”表示左盘中的硬币与右盘中的硬币重量相等。
·168·

第3章

算法与程序设计模块

【输出】 】 如果可以确定哪一块是假币,则输出假币的编号,否则输出 0。 【样例输入】 】 53 21234 < 114 = 125 = 【样例输出】 】 3 【算法分析】 】 对 3 种情况分类讨论:(1)如果是不等号则证明剩下的不是假币,假币在不等号里面产生;(2)如果是 等号则证明剩下的有假币,等号两侧均不是假币;(3)而假币只有一个。 [程序]
program coin; var b:array[1..100] of 0..2; a:array[1..100,-1..100] of integer; n,k:longint; procedure init; var f:text; i,j:integer; ch:char; begin fillchar(b,sizeof(b),0); assign(f,'coin.in'); reset(f); readln(f,n,k); for i:=1 to k do begin read(f,a[i,0]); for j:=1 to 2*a[i,0] do read(f,a[i,j]); readln(f); readln(f,ch); case ch of '=': begin for j:=1 to 2*a[i,0] do b[a[i,j]]:=1; a[i,-1]:=0; end; '<': begin for j:=1 to 2*a[i,0] do if b[a[i,j]]=0 then b[a[i,j]]:=2; a[i,-1]:=1; end; '>': begin for j:=1 to 2*a[i,0] do if b[a[i,j]]=0 then b[a[i,j]]:=2; a[i,-1]:=2; end; end; end; end; procedure print(ans:integer); var f:text;

·169·

信息技术与信息学竞赛 begin assign(f,'coin.out'); rewrite(f); writeln(f,ans); close(f); end; function check(x:integer):boolean; var i,j,t,px:integer; p:boolean; begin px:=0; for i:=1 to k do case a[i,-1] of 0: for j:=1 to 2*a[i,0] do if a[i,j]=x then begin check:=false;exit;end; 1: begin t:=0; for j:=1 to 2*a[i,0] do if a[i,j]=x then t:=j; if t=0 then begin check:=false;exit;end; if t<=a[i,0] then begin if px=0 then px:=-1; if px=1 then begin check:=false;exit;end; end; if t>a[i,0] then begin if px=0 then px:=1; if px=-1 then begin check:=false;exit;end; end; end; 2: begin t:=0; for j:=1 to 2*a[i,0] do if a[i,j]=x then t:=j; if t=0 then begin check:=false;exit;end; if t<=a[i,0] then begin if px=0 then px:=1; if px=-1 then begin check:=false;exit;end; end; if t>a[i,0] then begin if px=0 then px:=-1; if px=1 then begin check:=false;exit;end; end; end; end; check:=true; end; procedure main; var i,j,k,t,ans:integer; begin t:=0;ans:=0; for i:=1 to n do if b[i]=1 then inc(t); if t=n-1 then for i:=1 to n do if b[i]<>1 then begin print(i);halt;end;

·170·

第3章

算法与程序设计模块

if t=n then begin print(0);halt;end; for i:=1 to n do begin if b[i]=1 then continue; if check(i) then if ans<>0 then begin print(0);halt;end else ans:=i; end; print(ans); end; begin init; main; end.

例 4 均分纸牌(a.pas)。 【题目描述】 】 有 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 堆纸牌,每堆纸牌初始数,1≤Ai≤10 000)。 【输出】所有堆均达到相等时的最少移动次数。 】 【样例输入】 】 4 9 8 17 6 【样例输出】 】 3 【算法分析】 】 本题有 3 点比较关键:一是善于将每堆牌数减去平均数,简化了问题;二是要过滤掉 0(不是所有的 0, 如-2,3,0,-1 中的 0 是不能过滤的);三是负数张牌也可以移动,这是辩证法(关键中的关键)。 [程序]
program a; var num:array[0..100]of integer; sum:longint; time,i,n:integer; begin assign(input,'a.in');reset(input); assign(output,'a.out');rewrite(output); fillchar(num,sizeof(num),0); readln(n); sum:=0; time:=0; for i:=1 to n-1 do begin read(num[i]); inc(sum,num[i]); end; readln(num[n]); inc(sum,num[n]);

·171·

信息技术与信息学竞赛 sum:=sum div n; for i:=1 to n do if num[i]<>sum then begin inc(time); inc(num[i+1],num[i]-sum); num[i]:=sum; end; writeln(time); close(input); close(output); end.

例 5 矩阵(bincod.pas)。 【题目描述】 】 考虑一个 N 位的二进制串 b1…bN,其对应的二进制矩阵为:

然后将这个矩阵的行按照字典顺序排序,“0”在“1”之前。 现在,你的任务是编写一个程序,给定排序后的矩阵的最后一列,求出已排序矩阵的第一行。 例如:考虑二进制串(00110),排序后的矩阵为:

则该矩阵的最后一列为(1 0 0 1 0)。给出了这一列,你的程序应该确定第一行为 (0 0 0 1 1)。 【输入】 】 输入文件名为 bincod.in。第一行包含一个整数 N(0≤20000),表示二进制串的位数。第二行包含 N 个整数, 表示已排序的矩阵的最后一列(从上到下)。 【输出】 】 输出文件名为 bincod.out。输出文件仅一行,包含 N 个整数,从左到右依次表示已排序的矩阵的第一行; 若无解,则输出-1。 【样例输入】 】 5 10010 【样例输出】 】 00011

·172·

第3章

算法与程序设计模块

【算法分析】 】 题目给出方阵末列的字串,根据题意可以知道:将末列按照从 0~1 进行排序,即可得到方阵首列的字串。 又因为所有的字串都是由 0 和 1 组成,所以排序的过程可以简略为统计 0 和 1 的数量即可。对于样例,该过程 之后,首列和末列的字串如下所示: 首列 0 0 0 1 1 末列 1 0 0 1 0 然而此时末列和首列各个字符之间的对应关系仍就难以很直观地体现。字符之间的先后顺序难以确定。那 么就让我们换一种思路,将每个字符所对应位置替换上面所示的字符,我们得到: 首列 2 3 5 1 4 末列 1 2 3 4 5 这样,末列与首列的对应关系便清晰可见了。按照上面所示的顺序,可以将方阵的第一行的字符位置串接 起来:1→4→5→3→2,再将每个位置换成所对应的字符,即得到第一行的字串。 关于无解的数据,只需要统计所得字串中 0 和 1 的数量是否与给定字串的相同即可。 [程序]
program bincod; var a,b,c,cc,bn,nz,no:array [1..20000] of integer; i,n,z,o,nzp,nop,d,k,p:longint; first,max,sum,maxposition,cz,ci:longint; begin assign(input,'bincod.in'); reset(input); assign(output,'bincod.out');rewrite(output); readln(n); z:=0; o:=0;{count01 数目} nzp:=0; nop:=0; {临时 01 指针} for i:= 1 to n do begin read(a[i]); if a[i]=0 then begin inc(z); inc(nzp); nz[nzp]:=i; end; if a[i]=1 then begin inc(o); inc(nop); no[nop]:=i; end; end; nzp:=0; nop:=0; for i:= 1 to z do begin b[i]:=0;inc(nzp);bn[i]:=nz[nzp];end; for i:= 1+z to o+z do begin b[i]:=1;inc(nop);bn[i]:=no[nop];end; k:=0; p:=1; d:=1; repeat inc(k); c[k]:=a[p]; p:=bn[p]; until k=n; first:=0; sum:=0; max:=0; maxposition:=0; k:=1; repeat if c[k]=0 then inc(sum) else begin if sum>max then begin max:=sum; maxposition:=k; end; sum:=0; end; inc(k); until k>n; k:=1; if (c[1]=0) and (c[n]=0) then repeat if c[k]=0 then inc(sum) else begin if sum>max then begin max:=sum; maxposition:=k; end; sum:=0; end; inc(k); until k>n; for i:= 1 to n do begin

·173·

信息技术与信息学竞赛 if c[i]=0 then begin inc(cz); end; end; if cz<>z then begin writeln(-1); close(output); close(input); halt; end; fillchar(cc,sizeof(cc),0); ci:=0; if maxposition-max>0 then begin for i:= maxposition-max to n do begin inc(ci); cc[ci]:=c[i] end; for i:= 1 to maxposition-max-1 do begin inc(ci); cc[ci]:=c[i] end; end else begin for i:= 1 to max do begin inc(ci); cc[ci]:=0 end; for i:= maxposition to n-(max-maxposition+1) do begin inc(ci); cc[ci]:=c[i] end; end; for i:= 1 to n do begin write(cc[i]); write(' '); end; writeln; close(input);close(output); end.

小结:对于此类没有现成算法可以套用的题目,而搜索算法又明显低效时,对于选手的思维能力和基本功 都是一个很好的锻炼。只有在扎实的基础之上,才会有这种“灵光一闪”的灵感,可谓是:“山穷水复疑无路, 柳暗花明又一村。”

练习题
1.乘积最大(produc.pas) 【题目描述】 】 今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰 90 周年。 在华罗庚先生的家乡——江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友 XZ 也有幸 得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目:设有一个长度 N 的数字串,要求选手使 用 K 个乘号将它分成 K+1 个部分,找出一种分法,使得这 K+1 个部分的乘积能够为最大。同时,为了帮助选 手能够正确理解题意,主持人还举了一个例子: 有一个数字串:312,当 N=3,K=1 时会有以下两种分法:

·174·

第3章

算法与程序设计模块

(1)3×12=36 (2)31×2=62 这时,符合题目要求的结果是:31×2=62。 现在,请帮助你的好朋友 XZ 设计一个程序,求得正确的答案。 【输入】 】 程序的输入共有两行:第一行共有 2 个自然数 N,K (6≤N≤40,1≤K≤6);第二行是一个 K 度为 N 的数字 串。 【输出】 】 结果显示在屏幕上,相对于输入,应输出所求得的最大乘积(一个自然数)。 【样例输入】 】 42 1231 【样例输出】 】 62 2.砝码称重(g4.pas) 设有 1G、2G、3G、5G、10G、20G 的砝码各若干枚(其总重≤1000G)。 【输入】 】 A1 A2 A3 A4 A5 A6 (表示 1G 砝码有 A1 个,2G 砝码有 A2 个…20G 砝码有 A6 个) 【输出】 】 Total=N (N 表示这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况) 【样例输入】 】 1 1 0 0 0 0 【样例输出】 】 Total=3(表示可以称出 1g、2g、3g 3 种不同的重量)

3.12

剪枝、优化

以上介绍的是一些常用的搜索算法,这些算法是经典的和有效的,可以解决相当一部分的问题。但是,很 多问题会有比较复杂的情况和比较特殊的约束条件,那么可能以上的算法将不能直接使用解决。所以,我们应 该根据问题的实际情况,对原有的搜索算法做相应的修改,优化原有的搜索状况,使之更有效地完成问题的要 求。同时,优化也是许多搜索问题比较注重的一个方面,很多问题,可能考的就是搜索的优化,而不是搜索的 方法。 下面,列举出一些在实际问题中比较常用的优化方法。 (1)缩小问题的状态空间 缩小问题的状态空间 缩小问题的状态空间。如果在搜索开始之前,可以缩小问题的状态空间,减少状态结点数,或者降 低问题的规模,那么将会大大地减小搜索量,提高搜索的效率。 (2)在广度优先搜索算法中,扩展存储结点的内存空间 在广度优先搜索算法中, 在广度优先搜索算法中 扩展存储结点的内存空间。广度优先搜索算法的一个重要问题是占用存储 空间比较大,往往在还没有找到问题的最优解之前,已经没有空间存放新扩展出来的结点了,从而导致搜索失 败。我们可以利用一些循环数组,链表等数据结构,充分释放一些无用结点的存储空间,以腾出空间存储更多 的新结点。 (3)根据问题的约束条件,在搜索中剪枝 根据问题的约束条件, 根据问题的约束条件 在搜索中剪枝。在搜索的过程中,如果可以判断出一个结点,它不可能扩展 到最优解,我们就可以删除这个结点,这个结点的所有子结点将不被扩展出来。这是极其重要和常用的一个搜 索优化方法。

·175·

信息技术与信息学竞赛

(4)利用搜索过程中的中间解 利用搜索过程中的中间解。为了提高搜索效率,我们可以适当地将搜索过程中的一些中间解存储下 利用搜索过程中的中间解 来,以后遇到相同的结点,将不用再一次进行搜索,而直接使用存储下来的数据。 (5)进行解变换 进行解变换。当找到一个解(但是并不是最优解)之后,我们可以不用急着在状态空间中改变搜索 进行解变换 方向,去寻找另外一个解。而可以尝试通过改变已有解的结构,看看是否可以通过已经找到的解,变换到我们 需要求的最优解。 (6)寻找问题的隐性条件 寻找问题的隐性条件。有些问题存在着一些隐藏的条件,如果可以发现这些条件,将可以大大约束 寻找问题的隐性条件 结点的扩展数量,以至尽快找到问题的解。 (7)问题分治 问题分治。有些问题比较复杂和庞大,直接搜索可能搜索量比较大,搜索效率相应比较低。那么, 问题分治 可以先将问题分成一些子问题,先搜索到这些子问题的解,再通过一些合并和推导的方式,找到原有问题的解。 其实,所有的优化方法都只有一个目的,就是减少搜索量,提高搜索效率,尽可能快地找到问题的解。希 望大家在使用搜索方法的过程中,多分析问题,找到有效的优化方法,提高使用搜索技术的能力。 例 1 能否组成一个正方形。 【题目描述】 】 给出 M 个数,判断这些数能否组成一个正方形。 【算法分析】 可以采用分步搜索,先判断可不可以分成两组和相同的数,再分别判断这组是否可再分为和相等的两组。 分成两组和相同的数,也就是搜索一组和为总和一半的数,如果成功,则能分成两组。 【优化】 】 两个经典剪枝: (1)当前的和大于目标和,剪掉。 (2)当前和加 i 以后的所有数之和小于目标和,剪掉(预处理时,可以对数先进行排序,再求 b[i](数 i 以及 i 以后的数的和))细节分析: 对数组进行第一步分组,产生两组数,一组标记为 0,另一组标记为 2,成功分组后再分别对这两组进行 分组,0 的可再分为 0、1、2 组可再分为 2、3,需要注意的是当 0 组分配成功,2 组分组未成功时,需要回溯 到先一次递归,这时标记数组原来的 0 可能为 0 和 1、2 可能为 2 或是 3,所以在以后写程序时要注意这一点。

·176·

第3章

算法与程序设计模块

例 2 加括号。 【题目描述】 】 输入两个数字(I,j),在第一个数字 i 中间添上若干个加号,使得这个代数式的值等于第二个数字 j。 【算法分析】 这道题采用的算法是剪枝搜索,逐一在第一个数字 i 各个数字之间添上加号,并计算出当前代数式的值, 如果等于第二个数字 j,则退出循环,打印结果“YES”;如果不是,则继续循环;当循环结束后,还未能得出 第二个数 j,则打印结果“NO”。 【算法流程】 (1)首先将以字符串输入的第一个数字 i 切成一个数字 e 段,放进一个数组 a[e]里。 (2)接着进行循环,逐一在第一个数字 i 各个数字之间添上加号,由于在各个数字之间添上加号后代数式 的值只有两种情况:大于第二个数字 j 或小于第二个数字 j,所以循环的内容如下所示。 ①以 h,i 分别作为当前处理的数字的首位在数组里的位置和在当前数字的第 i 位添 加号。 ②分别以 x1,x2 存放添加号后加号前的数值以及加号后的数值,x3 将赋值为 x1+x2,作为当前代数式的 值。当 x3>j 时,则进行将 h 赋值为 i,将要处理的数字赋值为加号后的数值,并将 x3 赋值为 x3-x2,作为加号 前的数值;当 x3<j,而且 i≤e 时,则将 i 赋值为 i+1,在当前处理的数字添加号的数位的后一位添上加号,并 将 x3 赋值为 x3-x2;若 i>e 时,则将 h 赋值为 h-1,i 赋值为 h+1,在当前处理的数字添加号的数位的前一位添 上加号,并将 x3 赋值为 x3-x2-a[i]。 (3)当 h≤0、h>e、i≤0、i>e、x3<>j 时,则退出循环并打印结果“NO”;当 0<h≤e、0<i≤e、x3=j 时, 则退出循环并打印结果“YES”。 [程序]
program aa; var a,b:text; c:string; d,e,g,h,i,x1,x2,x3,xx:integer; f:array [1..100] of integer; procedure bb; begin assign(a,'tjh.dat'); reset(a); readln(a,c,d); close(a); end; procedure cc; begin for e:=1 to length(c) do f[e]:=ord(c[e])-48; x1:=0; x2:=0; x3:=0; xx:=1; h:=1; i:=1; while x3<>d do begin for g:=h to i do x1:=x1*10+f[g]; for g:=i+1 to e do x2:=x2*10+f[g]; x3:=x1+x2+x3; if x3=d then exit; if (h<0) or (i<0) then begin xx:=0; exit; end; if x3<d then begin i:=i+1;

·177·

信息技术与信息学竞赛 x3:=x3-x1-x2; if i=5 then begin h:=h-1; i:=h+1; x3:=x3-f[i-1]; end; x1:=0; x2:=0; end; if x3>d then begin h:=h+1; i:=h; x1:=0; x3:=x3-x2; x2:=0; end; end; end; procedure dd; begin assign(b,'tjh.out'); rewrite(b); if xx=1 then writeln(b,'yes') else writeln(b,'no'); close(b); end; begin bb; cc; dd; end.

例 3 虫食算(alpha.pas)。 【题目描述】 】 所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母。 来看一个简单的例子: 43#9865#045 + 8468#6633 其中#号代表被虫子啃掉的数字。根据算式,我们很容易判断:第一行的两个数字分别是 5 和 3,第二行的 数字是 5。 现在,我们对问题做两个限制:首先,我们只考虑加法的虫食算。这里的加法是 N 进制加法,算式中 3 个 数都有 N 位,允许有前导的 0。其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的,我们将相同 的数字用相同的字母表示,不同的数字用不同的字母表示。如果这个算式是 N 进制的,我们就取英文字母表午 的前 N 个大写字母来表示这个算式中的 0~N-1 这 N 个不同的数字:但是这 N 个字母并不一定顺序地代表 0~ N-1。输入数据保证 N 个字母分别至少出现一次。 BADC + CRDA DCCC 上面的算式是一个 4 进制的算式。很显然,我们只要让 ABCD 分别代表 0123,便可以让这个式子成立了。 现在,你的任务是对于给定的 N 进制加法算式,求出 N 个不同的字母分别代表的数字,使得该加法算式成立。 输入数据保证有且仅有一组解。 【输入】 】 输入文件 alpha.in 包含 4 行。第一行有一个正整数 N(N≤26),后面的 3 行每行有一个由大写字母组成的 字符串,分别代表两个加数以及和。这 3 个字符串左右两端都没有空格,从高位到低位,并且恰好有 N 位。 【输出】 】

·178·

第3章

算法与程序设计模块

输出文件 alpha.out 包含一行。在这一行中,应当包含唯一的那组解。解是这样表示的:输出 N 个数字,分 别表示 A,B,C…所代表的数字,相邻的两个数字用一个空格隔开,不能有多余的空格。 【样例输入】 】 5 ABCED BDACE EBBAA 【样例输出】 】 10342 【数据规模】 】 对于 30%的数据,保证有 N≤10; 对于 50%的数据,保证有 N≤15; 对于全部的数据,保证有 N≤26。 【算法分析】 经典的搜索题。最单纯的搜索的时间复杂度为 O(n!),是会严重超时的。计算机是很“笨”的,它不会 思考,在盲目搜索的过程中,很容易出现这种情况:计算机在某一位搜索出了一个算式 1 + 1 = 3,并且继续搜 索。 明显,人眼很容易就看出这是不合法的,但计算机不会。于是,我们想到了第一个剪枝:每次搜索的时候, 从最后向前判断是否有不合法的式子。这一个剪枝非常简单,而且效果也非常的好。因为它剪去了很多不必要 的搜索。为了配合这一种剪枝更好的实行,搜索顺序的改变也成为大大提高程序效率的关键:从右往左,按照 字母出现顺序搜索,在很大程度上提高了先剪掉废枝的情况,使程序的效率得到大大提高。有了以上两个剪枝, 程序就已经可以通过大部分测试点了。但是有没有更多的剪枝呢?答案是肯定的。 根据前面的剪枝,我们可以找到类似的几个剪枝:对于 A+B=C 的形式,假如: A***?*** + B*?**?** C***???* 其中:*代表已知,?代表未知。那么,A + B 与 C 的情况并不能直接确定。但是,假如(A + B)% N 与(A + B + 1)% N 都不等于 C 的话,那么这个等式一定是不合法的。因为它只有进位和不进位的两种情况。 同样,我们在一个数组里记录了 Used[i]表示一个数字有没有用过,那么,对于某一位 A + B = C 的等 式,如果已经得到了两个数,另一个数还待搜索的时候,我们还可以根据这个加入一个剪枝:②对于 A + ? = C 的形式,假如: 考虑不进位的情况,则?处为 P1 = (C - A + N) % N; 考虑进位的情况,则?处为 P2 = (C - A - 1 + N) % N; P1、P2 均被使用过,那么这个搜索一定是无效的,可以剪去。 有了以上的剪枝,就可以很轻松地通过所有的测试数据了。当然,还有很多值得思考的剪枝以及其他的思 路。例如,枚举进位、解方程(但是可能需要枚举)等,在这里就不详细讨论了。 小结:搜索题的框架往往不难找到,关键就是在搜索的优化上。搜索问题的优化更多的需要选手的经验和 小结 思考及分析问题的能力,所以搜索剪枝也是竞赛中经久不衰的经典问题。

3.13
1.动态规划的基本方法

动 态 规 划

多阶段决策的最优化问题:所谓多阶段决策问题是指这样一类问题,该问题的决策过程可以按时间顺序分 解成若干相互联系的阶段, 在每一个阶段分别做出决策从而形成决策序列, 使得整个活动的总体效果达到最优。 可以看出,这类问题有两个要素:一个是阶段,一个是决策。
·179·

信息技术与信息学竞赛

阶段:将所给问题的过程,按时间或空间等自然特征分解成若干个相互联系的阶段,以便按次序去求每阶 阶段 段的解。描述阶段的变量称为阶段变量,常用字母 k 表示阶段变量。阶段是问题的属性 阶段是问题的属性。从阶段的定义中可以 阶段是问题的属性 看出阶段的两个特点,一是“相互联系”,二是“次序”。 状态:各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量,常用 sk 表示第 k 阶段的 状态 状态变量,状态变量 sk 的取值集合称为状态集合,用 Sk 表示。状态是阶段的属性 状态是阶段的属性。每个阶段通常包含若干个 状态是阶段的属性 状态,用以描述过程发展到这个阶段时所处在的一种客观情况。 这里所说的状态应该具有下面的性质:将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态, 它的决策只依赖于当前的状态,而与以前各阶段的状态无关。换句话说:过去的历史只能通过当前的状态去影 响它未来的发展,当前的状态是对以往历史的一个总结。这个性质称为无后效性。 决策:当各阶段的状态取定之后,就可以做出不同的决定,从而确定下一阶段的状态,这种决定称为决策。 决策 表示决策的变量,称为决策变量,常用 uk(sk)表示第 k 阶段当状态为 sk 时的决策变量。在实际问题中,决 策变量的取值往往限制在一定范围内,我们称此范围为允许决策集合。常用 Dk(sk)表示第 k 阶段从状态 sk 出发的允许决策集合。显然有 uk(sk)?Dk(sk)。决策是问题的解的属性 决策是问题的解的属性。决策的目的就是“确定下一阶段 决策是问题的解的属性 的状态”。 状态转移:动态规划中本阶段的状态往往是上一阶段的状态和上一阶段的决策的结果,由第 k 段的状态 sk 状态转移 和本阶段的决策 uk 确定第 k+1 段的状态 sk+1 的过程叫状态转移。 状态转移规律的形式化表示 sk+1=Tk (sk,uk) 称为状态转移方程。 由此可见,状态转移是决策的目的,决策是状态转移的途径。决策和状态转移是导出状态的途径,也是联 系各阶段的途径。 策略: 整个问题的决策序列就构成了一个策略, p1, 用 n={u1(s1), u2(s2), un(sn)} …, 策略 各阶段的决策确定后, 表示。对每个实际问题,可供选择的策略有一定范围,称为允许策略集合,记作 P1,n,使整个问题达到最优效 果的策略就是最优策略。 最优化原理:整个过程的最优策略应具有这样的性质:无论初始状态及初始决策如何,对于先前决策所形 最优化原理 成的状态而言,其以后的所有决策必须构成最优策略。简言之,就是“最优策略的子策略也是最优策略”。在 动态规划的算法设计中,这一性质又被称作最优子结构性质。 最优指标函数:用于衡量所选定策略优劣的数量指标称为指标函数,最优指标函数记为 fk(sk),它表示 最优指标函数 从第 k 段状态 sk 采用最优策略 p×k,n 到过程终止时的最佳效益值。最优指标函数其实就是我们真正关心的问 题的解。最优指标函数的求法一般是一个从目标状态出发的递推公式,称为规划方程。 其中 sk 是第 k 段的某个状态,uk 是从 sk 出发的允许决策集合 Dk(sk)中的一个决策,Tk(sk,uk)是由 sk 和 uk 所导出的第 k+1 段的某个状态 sk+1,g(x,uk)是定义在数值 x 和决策 uk 上的一个函数,而函数 opt 表示最优 化,根据具体问题分别表为 max 或 min。某个初始值,称为边界条件。 这里是一种从目标状态往回推的逆序求法,适用于目标状态确定的问题。当然,对于初始状态确定的问题, 我们也可以采用从初始状态出发往前推的顺序求法。事实上,这种方法对我们来说要更为直观、更易设计一些, 从而更多地出现在我们的解题过程中。 在动态规划的算法设计中, 最优指标函数与状态转移方程统称为状态转移方程, 它是动态规划模型的核心, 最优指标函数与状态转移方程统称为状态转移方程, 它是动态规划模型的核心, 也是动态规划算法设计的关键。 也是动态规划算法设计的关键

·180·

第3章

算法与程序设计模块

例 1 “破锣摇滚”乐队(g2.pas)。 你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的 N(1≤N≤600)首歌的版权。你打算从中精选 一些歌曲,发行 M(1≤M≤600)张 CD。每一张 CD 最多可以容纳 T(1≤T≤10000)分钟的音乐,一首歌不 能分装在两张 CD 中。不巧你是一位古典音乐迷,不懂如何判定这些歌的艺术价值。于是你决定根据以下标准 进行选择:(1)歌曲必须按照创作的时间顺序在 CD 盘上出现;(2)选中的歌曲数目尽可能地多。 【输入】 】 多组数据。第一行三个整数:N、T、M。第二行 N 个整数,分别表示每首歌的长度,按创作时间顺序排列。 【输出】 】 一个整数,表示可以装进 M 张 CD 盘的乐曲的最大数目。本题有多组测试数据。 【样例输入】 】 452 4342 【样例输出】 】 3 【算法分析】 直接说最优做法, O(n^2), f[I, 记 j]为前 i 个曲子取 j 个最小时间, f[I, 则 j]:=min(f[i-1, sum(f[i-1, j], j-1], g[I,j])),注意这个设法很巧妙。另外注意陷阱!有的碟片不能放进去。 [程序]
grogram g2 Uses Math; Const L=1000; INF=100000; Var g: array [0..L] of longint; f: array [0..L,0..L] of longint; n,t,m,i,j,ans: longint; Function Sum(a,b:longint):longint; var c,d:longint; begin d:= a div t + 1; c:= t - a mod t; if c >= b then exit( a + b ) else exit( d * t + b ); end; begin assign(input,'g2.in'); reset(input); assign(output,'g2.out'); rewrite(output); repeat readln(n,t,m); if n=0 then break; i:=0; j:=0; while j<n do begin inc(j); inc(i); read(g[i]); if g[i] > t then dec(i); end; readln; n:=i; fillchar(f,sizeof(f),0); for i:= 0 to n do for j:= 1 to n do f[i,j]:=inf; for i:= 1 to n do for j:= 1 to i do f[i,j]:=min(f[i-1,j],sum(f[i-1,j-1],g[i]));

·181·

信息技术与信息学竞赛 ans:=0; for i:= n downto 1 do if f[n,i] <= t * m then begin ans:=i; break; end; writeln(ans); until eof; close(input); close(output); end.

例 2 过河卒(river.pas)。 【题目描述】 】 如图 3-23 所示,A 点有一过河卒,需要走到目标 B 点。卒行走的规则:可以向下,或者向右。
卒 A 1 2 3 P5 1 2 3 4 X P7 P8 P1 P6 C 马 P2 4 5 P4 P3 6 7 8 Y

B(4,8)

图 3-23

过河卒示意图

同时在棋盘上的任一点有一个对方的马(如图 3-22 中 C 点),该马所在的点和所有跳跃一步可达的点称 为对方马的控制点。 例如,图 3-22 中 C 点的马可控制 9 个点(P1…P8,C)。卒不能通过对方马的控制点。棋盘用坐标表示,A 点(0,0),B 点(n,m)(n,m 为不超过 20 的整数,并有键盘输入),同样,马的位置坐标是需要给出的(约 定:C≠A 同时 C≠B)。 现在,需要你计算出卒从 A 点出发能够到达 B 点的路径的条数。 【输入】 B 点坐标(n,m)以及对马的坐标(X,Y)。{不用判错} 【输出】 一个整数。(路径的条数) 【样例输入】 6632 【样例输出】 17 【算法分析】 先开一个[-2..22,-2..22]的数组,以保证不出现错误 201(数组越界)。读入马的位置,(a,b)末位置。数组 清零。将马控制的位置变成-1。下面计算: for i:=a downto 0 do for j:=b downto 0 do 如果那两个没有-1,就加;有-1 就不加-1;都是-1 就便 0。输出(0,0)。 [程序]
program river; var a,b,c,d,e,f,g,h,i,j,k,l:longint;pp:boolean;

·182·

第3章

算法与程序设计模块

x:array[-2..22,-2..22] of int64; procedure init(); begin read(a,b,c,d); end; procedure befor(); begin fillchar(x,sizeof(x),0); x[c,d]:=-1; x[c-1,d-2]:=-1; x[c-2,d-1]:=-1; x[c-1,d+2]:=-1; x[c-2,d+1]:=-1; x[c+1,d+2]:=-1; x[c+1,d-2]:=-1; x[c+2,d+1]:=-1; x[c+2,d-1]:=-1; end; procedure doit(); begin x[a,b+1]:=1; for i:=a downto 0 do for j:=b downto 0 do if (x[i,j]<>-1) then begin if (x[i,j+1]=-1) and (x[i+1,j]=-1) then begin x[i,j]:=0; pp:=false; end; if (x[i,j+1]<>-1) and (x[i+1,j]=-1) and pp then x[i,j]:=x[i,j+1]; if (x[i,j+1]=-1) and (x[i+1,j]<>-1) and pp then x[i,j]:=x[i+1,j]; pp:=true; if (x[i,j+1]<>-1) and (x[i+1,j]<>-1) then x[i,j]:=x[i,j+1]+x[i+1,j]; end; write(x[0,0]); end; begin assign(input,'river.in');reset(input); assign(output,'river.out');rewrite(output); pp:=true; init(); befor(); doit(); close(input);close(output); end.

例 3 数的计算-加强版(cd1.pas)。 Problem 先输入一个自然数 n(n≤3000000),然后对此自然数按照如下方法进行处理: (1)不作任何处理。 (2)在它的左边加上一个自然数,但该自然数不能超过原数的一半。 (3)加上数后,继续按此规则进行处理,直到不能再加自然数为止。 例如,n=6。 6;16;26;126;36;136。所以满足要求的个数为 6。 【输入】 包含多个测试数据,每行是一个整数 n。(1≤n≤3000000) 【输出】 一个整数,表示解的个数。(保证不超过 50 位)

·183·

信息技术与信息学竞赛

【样例输入】 6 【样例输出】 6 【算法分析】 原题是找规律。 1→1 2→2 3→2 4→4 5→4 6→6 7→6 8→10 9→10 10→14 11→14 12→20 13→20 so... f[n]:=f[1]+f[2]+...f[n div 2] <=> n 奇数 f[n-1] n 偶数 f[n-1]+f[n div 2] 结果很大,高精度是当然的。 [程序]
program tju1059; const half=1500000; var s:array[0..half,0..2]of int64; n,i:longint; base:int64; m:integer; procedure tail(a:int64); var s:string; i:byte; begin str(a,s); for i:=length(s) to 17 do write('0'); write(s); end; procedure out(a,b,c:int64); begin if a>0 then begin write(a);tail(b);tail(c); end else if b>0 then begin write(b);tail(c); end else write(c); writeln; end; begin assign(input,'cd1.in');reset(input); assign(output,'cd1.out');rewrite(output); base:=1; for m:=1 to 9 do base:=base*10; {10 的 9 次方,在 fp2.0 下,只能用循环来实现} base:=base*base; s[0,0]:=1; for n:=1 to half do for i:=0 to 2 do begin inc(s[n,i],s[n-1,i]+s[n shr 1,i]); if s[n,i]>=base then begin inc(s[n,i+1]);dec(s[n,i],base); end; end; repeat

·184·

第3章 read(n);n:=n shr 1; out(s[n,2],s[n,1],s[n,0]); until seekeof; close(input);close(output); end.

算法与程序设计模块

例 4 文科生的悲哀(d3.pas)。 【题目描述】 化学不及格的 Matrix67 无奈选择了文科。他必须硬着头皮艰难地进行着文科的学习。 这学期的政治、历史和地理课本各有 n 章。每一科的教学必须按章节从前往后依次进行。若干章政治、若 干章历史和若干章的地理内容可以合成一个教学阶段。年级计划将整个学期的内容分成若干个阶段进行教学。 为了保证各科教学进度相同,年级规定每一个阶段包含的各科的章节数必须相同。一个阶段包含的章节越多, 这个阶段所需要的课时也就越多。经过研究,假如某个阶段包含政、史、地各 k 章,则政治学习需要花费 3k 天 的课时,历史学习需要花费 5k 天的课时,地理学习需要花费 2k 天的课时,最后还需要 4 天的综合训练。一个阶 段所花费的总时间是以上四项时间的和。 为了便于安排时间,学校希望每个阶段恰好需要若干周来完成。因此,划分出的每一个阶段所需要的天数 都必须是 7 的整数倍(高三是没有星期六和星期天的)。 那么,这学期的课程最多可以划分成多少个阶段呢?你会想到,要想划分的阶段数最多,一个阶段完成一 章的任务就行了(因为 31+51+21+4=14 是 7 的整数倍)。但问题没有这么简单。每个课本都可能有一些独立性 较强的连续章节,它们具有很强的连续性,必须在一个阶段中完成。如果你已知所有不能划分在两个或两个以 上的阶段中的连续章节,你还能计算出最多能安排多少个阶段吗? 【输入】 第一行有两个用空格隔开的正整数 n 和 m,分别表示各科课本的章节数和不可分割的连续章节的个数。 第二行到第 m+1 行,每行告诉了一个信息,该信息说明了哪一个课本的第几章到第几章必须一次性完成。 同一科目给定的章节有可能重复或有重叠。 每一行信息分为两个部分。第一部分是“Politics:”、“History:”、“Geography:”三个字符串中的一个;第 二部分是用“-”连接的两个数字 x,y(1≤x<y≤n),表示该行第一部分所示的课本从第 x 章到第 y 章具有连续性。 第二部分紧接在第一部分后面,没有任何符号分隔。 对于 30%的数据,n,m≤10; 对于 50%的数据,n,m≤1000; 对于 100%的数据,n,m≤100 000。 【输出】 一个正整数,表示按照学校和年级的种种要求,最多可以安排的阶段个数。如果没有符合条件的安排方案, 请输出-1。 注意: 注意:有 3 个要求需要同时考虑。(1)每一个阶段包含的各科章数相同;(2)按时间函数计算出的各阶 段所需天数必须是 7 的倍数;(3)给出的任一个连续章节都不能被分割开来。

·185·

信息技术与信息学竞赛

【样例输入】 83 Politics:1-2 History:5-6 Politics:1-4 【样例输出】 3 注释 Hint 【样例说明】 最多可以安排 3 个阶段,具体方案:第一阶段完成各科第 1~6 章的课程;第二阶段完成各科第 7 章的课 程;第三阶段完成各科第 8 章的课程。 【样例输入#2】 42 Geography:1-3 History:2-4 【样例输出#2】 -1 【算法分析】 类型:数学+动态规划。难题! 做法 1: 搜索,30 分。 做法 2: O(n2 )动态规划,50 分。 做法 3: O(n)动态规划,100 分,发现上当了。(1)3 科可以合为 1 科。(2)设 f[i,j]表示将前 i 章按这样 的要求划分所能得到的最多阶段数:最后一部分的章节数除以 6 余 j,且前面的章节按要求划分。因此,j 的取 值只能是 0~5。 :=f[i-1,0] 当 Cont[i-1]=True 时; f[i,1] :=Max{ f[i-1,0],f[i-1,1],f[i-1,2] }+1 当 Cont[i-1]=False 时; f[i,2]:=f[i-1,1]; f[i,3]:=f[i-1,2]; f[i,4]:=f[i-1,3]; f[i,5]:=f[i-1,4]; f[i,0]:=f[i-1,5]; 最后输出 f[n,0]、f[n,1]、f[n,2]中的最大值即可。 [程序]
Program d3; Const L =100000; var p:array [1..100000] of longint; ok: array [1..100000] of boolean; f:array [0..100000,0..5] of longint; i,j,n,m,x,y,v,ans: longint; s,t: string; begin assign(input,'d3.in');reset(input);assign(output,'d3.out');rewrite(output); readln(n,m); for i:= 1 to m do begin readln(s); v:=pos(':',s);delete(s,1,v);v:=pos('-',s);t:=copy(s,1,v-1); delete(s,1,v);val(t,x); val(s,y);if p[x]<y then p[x]:=y; end; v:=0;

·186·

第3章

算法与程序设计模块

for i:= 1 to n do begin if p[i]>v then v:=p[i]; if i<v then ok[i]:=true; end; for i:= 1 to 5 do f[0,i]:=-1; for i:= 1 to n do begin if not ok[i] then begin f[i,0]:=-1; if f[i-1,5]<>-1 then f[i,0]:=f[i-1,5]+1; if (f[i-1,0]<>-1) and (f[i-1,0]+1>f[i,0]) then f[i,0]:=f[i-1,0]+1; if (f[i-1,1]<>-1) and (f[i-1,1]+1>f[i,0]) then f[i,0]:=f[i-1,1]+1; end else f[i,0]:=f[i-1,5]; f[i,1]:=f[i-1,0];f[i,2]:=f[i-1,1]; f[i,3]:=f[i-1,2];f[i,4]:=f[i-1,3]; f[i,5]:=f[i-1,4]; end; if f[n,0]=0 then writeln('-1') else writeln(f[n,0]); close(input); close(output); end.

练习题
1.祖玛(zuma.pas) 精致细腻的背景,外加神秘的印加音乐衬托,仿佛置身在古老国度里面,进行一个神秘的游戏——这就是 著名的祖玛游戏。祖玛游戏的主角是一只石青蛙,石青蛙会吐出各种颜色的珠子,珠子造型美丽,并且有着神 秘的色彩,环绕着石青蛙的是载着珠子的轨道,各种颜色的珠子会沿着轨道往前滑动,石青蛙必需遏止珠子们 滚进去轨道终点的洞里头,如何减少珠子呢?就得要靠石青蛙吐出的珠子与轨道上的珠子相结合,颜色相同者 即可以消失得分。直到轨道上的珠子通通都被清干净为止。 或许你并不了解祖玛游戏,没关系。这里我们介绍一个简单版本的祖玛游戏规则。一条通道中有一些玻璃 珠,每个珠子有各自的颜色,如图 3-24 所示。玩家可以做的是选择一种颜色的珠子(注意:颜色可以任选,这 与真实游戏是不同的)射入某个位置。

·187·

信息技术与信息学竞赛

图 3-24

祖玛示意图(1)

图 3-25 中玩家选择一颗蓝色珠子,射入图示的位置,于是得到一个图 3-26 的局面。

图 3-25

祖玛示意图(2)

图 3-26

祖玛示意图(3)

当玩家射入一颗珠子后,如果射入的珠子与其他珠子组成了 3 颗以上连续相同颜色的珠子,这些珠子就会 消失。例如,将一颗白色珠子射入图 3-27 的位置,就会产生 3 颗眼色相同的白色珠子。这 3 颗珠子就会消失, 于是得到图 3-28 的局面。

图 3-27

祖玛示意图(4)

图 3-28

祖玛示意图(5)

需要注意的是,图 3-26 中的 3 颗连续的黄色珠子不会消失,因为并没有珠子射入其中。 珠子的消失还会产生连锁反应。当一串连续相同颜色的珠子消失后,如果消失位置左右的珠子颜色相同, 并且长度大于 2,则可以继续消失。例如,图 3-29 中,射入一颗红色珠子后,产生了 3 颗连续的红色珠子。当 红色珠子消失后,它左右都是白色的珠子,并且一共有四颗,于是白色珠子也消失了。之后,消失位置的左右 都是蓝色珠子,共有 3 颗,于是蓝色珠子也消失。最终得到图 3-30 的状态。 注意: 因为蓝色珠子消失的位置一边是紫色珠子, 另一边是黄色珠子, 注意 图 3-30 中的 3 颗黄色珠子不会消失, 颜色不同。

图 3-29

祖玛示意图(6)

·188·

第3章

算法与程序设计模块

图 3-30

祖玛示意图(7)

除了上述的情况,没有其他的方法可以消去珠子。 现在,我们有一排珠子,需要你去消除。对于每一轮,你可以自由选择不同颜色的珠子,射入任意的位置。 你的任务是射出最少的珠子,将全部珠子消去。 【输入】 第一行一个整数 n(n ≤500),表示珠子的个数。第二行 n 个整数(32 位整数范围内),用空格分割,每 个整数表示一种颜色的珠子。 【输出】 一个整数,表示最少需要射出的珠子个数。 【样例输入】 9 112233211 【样例输出】 1 2.选课(choose.pas) 大学实行学分制。每门课程都有一定的学分,学生只要选修了这门课,并通过考核就能获得相应的学分。 学生最后的学分是他各门课学分的总和。每个学生都要选择规定数量的课程。其中有些课程可以直接选修,有 些课程需要一定的基础知识,必须在选了其他的一些课程的基础上才能选修。例如,《剥皮术》就必须在选修 了《屠龙术》后才能选修。我们称《屠龙术》是《剥皮术》的选修课。每门课的直接选修课最多只有一门。两 门课也可能存在相同的选修课。 每门课都有一个课号,课号依次是 1,2,3…。以表 3-1 为例说明。
表 3-1 课 1 2 3 4 5 号 选 修 课 号 无 1 2 无 2 选修课学分表 学 1 1 3 3 4 分

表 3-1 中 1 是 2 的选修课,即如果要选修 2,则 1 必须已被选过。同样,要选修 3,那么 1 和 2 都一定被选 修过。 每个学生可选的课程总数是一定的,请找出一种方案,使得到的总学分最多。 【输入】 第一行包括两个正整数 M、N(中间一个空格),其中 M 表示总课程数,(1≤M≤1000),N 表示每个学生 最多可选的课程总数。(1≤N≤M)。 以下 M 行每行代表一门课, 课号依次是 1,2,…,M。 每行两个数, 第一个数为这门课的直接先修课的课号 (若 不存在则为 0),第二个数为该门课的学分。学分是不超过 10 的正整数。测试数据保证学生能够选满 N 门课。 【输出】 第一行只有一个数,即最多可得的学分。 如果 M≤99,则以下 N 行每行一个数,表示学生所选的课程的课号,课号按升序排列。 如果 M≥100,则不必输出具体方案。数据保证只有唯一的正确输出。 【样例输入】 74 22 01

·189·

信息技术与信息学竞赛

04 21 71 76 22 【样例输出】 13 2 3 6 7 3.祭祀(river.pas) 【题目描述】 在遥远的东方,有一个神秘的民族,自称 Y 族。他们世代居住在水面上,奉龙王为神。每逢重大庆典,Y 族都会在水面上举办盛大的祭祀活动。 我们可以把 Y 族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口,并且水在河道 内按照一个固定的方向流动。显然,水系中不会有环流(如图 3-31 中描述一个环流的例子)。
岔口 河道 环流 图 3-31 祭祀示意图

由于人数众多的原因,Y 族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重,这些祭祀地点的选 择必须非常慎重。准确地说,Y 族人认为,如果水流可以从一个祭祀点流到另外一个祭祀点,那么祭祀就会失 去它神圣的意义。族长希望在保持祭祀神圣性的基础上,选择尽可能多的祭祀的地点。 【输入】 输入文件 river.in 中第一行包含两个用空格隔开的整数 N、M,分别表示岔口和河道的数目,岔口从 1~N 编号。接下来 M 行,每行包含两个用空格隔开的整数 u、v,描述一条连接岔口 u 和岔口 v 的河道,水流方向 为自 u 向 v。 【输出】 第一行包含一个整数 K,表示最多能选取的祭祀点的个数。接下来一行输出一种可行的选取方案。对于每 个岔口依次输出一个整数,如果在该岔口设置了祭祀点,那么输出一个 1,否则输出一个 0。应确保你输出的 1 的个数最多,且中间没有空格。 接下来一行输出,在选择最多祭祀点的前提下,每个岔口是否能够设置祭祀点。对于每个岔口依次输出一个 整数,如果在该岔口能够设置祭祀点,那么输出一个 1,否则输出一个 0。 注意: 注意:多余的空格和换行可能会导致你的答案被判断为错误答案。 【样例输入】 44 12 34 32 42 【样例输出】 2 1010 1011

·190·

第3章

算法与程序设计模块

【样例说明】 在样例给出的水系中,不存在一种方法能够选择 3 个或者 3 个以上的祭祀点。包含两个祭祀点的测试点的 方案有两种:选择岔口 1 与岔口 3(如样例输出第二行),选择岔口 1 与岔口 4。 水流可以从任意岔口流至岔口 2。如果在岔口 2 建立祭祀点,那么任意其他岔口都不能建立祭祀点,但是 在最优的一种祭祀点的选取方案中我们可以建立两个祭祀点,所以岔口 2 不能建立祭祀点。对于其他岔口,至 少存在一个最优方案选择该岔口为祭祀点,所以输出为 1011。 【评分规则】 对于每个测试点:(1)如果你仅输出了正确的被选取的祭祀点个数,那么你将得到该测试点 30%的分数; (2)如果你仅输出了正确的被选取的祭祀点个数与一个可行的方案,那么你将得到该测试点 60%的分数; (3) 如果你的输出完全正确,那么你将得到该测试点 100%的分数; 【数据规模】 N≤100 M≤1 000 【算法分析】 】 这道题可以搜索、贪心、枚举、动态规划、匹配。

·191·


相关文章:
信息学奥赛试题精选33题(附带题解)
信息学奥赛试题精选33题(附带题解)_学科竞赛_高中教育_教育专区。信息学奥赛试题精选33题(附带题解) 基础题:【1 Prime Frequency】 【问题描述】给出一个仅包含...
怎样做好信息学奥赛培训辅导
怎样做好信息学奥赛培训辅导临邑洛北中学西校 摘要: 信息学奥林匹克竞赛是智力与计算机应用的比赛,是推动计算机知识普及深入的手段,是 一样高层次的计算机知识普及...
凭什么我得了信息学奥赛国家一等奖
凭什么我得了信息学奥赛国家一等奖_教学反思/汇报_教学研究_教育专区。这人就是牛啊!凭啥!凭的是意志!凭的是信念!凭什么我得了信息学奥赛国家一等奖 山东省莱州...
信息学奥赛初赛复习题
中国信息学奥赛 B. 中国国家奥委会 C. 国际信息学奥赛D. 中国信息学联赛 [重要作业] 1、微机内的存储器的地址是以( )编址的。 A.二进制位 B.字长 C....
信息学奥赛历年试题(解答)
信息学奥赛——算法入门教... 35页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
信息学奥赛基础知识习题(答案版)
信息学奥赛基础知识习题(答案版) 一、选择题(下列各题仅有一个正确答案,请将你认为是正确的答案填在相应的横线上) 1. 我们把计算机硬件系统和软件系统总称为 ...
历届信息学奥赛选择题
历届信息学奥赛选择题_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 历届信息学奥赛选择题_学科竞赛_高中教育_教育专区。泰安市实验学校 第五...
2015信息学奥赛初赛 普级组
2015信息学奥赛初赛 普级组_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档2015信息学奥赛初赛 普级组_学科竞赛_初中教育_教育专区。 ...
深入开展信息学奥赛之我见
深入开展信息学奥赛之我见安徽省蚌埠第九中学 张恩权 bbjzzeq@126.com 摘要:信息学奥林匹克竞赛是一项益智性的竞赛活动,核心是考查参赛选手的智力、 分析问题...
全国青少年信息学奥林匹克联赛大纲
1. 联赛命题委员会委员应具备如下资格: ●●● 从事一线计算机教学或信息学奥赛辅导工作两年(含)以上; 有精力和时间从事该项工作; 对此项工作有兴趣并愿意作为...
更多相关标签:
信息奥赛 | 信息学奥赛一本通 | 信息学奥赛培训 | 信息学 | 小学信息学奥赛 | 信息学竞赛 | 信息学奥林匹克竞赛 | 信息学奥赛辅导 |