荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: [参赛经验]2
发信站: 荔园晨风BBS站 (Thu Mar 18 16:59:09 2004), 站内信件
全面地考虑问题
在编程序时常常会遇到这样的问题:一道很简单的题目，编出的程序却错了很多测试点
。这其中的主要原因是由于考虑问题不全面，只想到了一些普通的情况，而遗漏了很多
特殊的地方。
下面通过几个例子来进行讨论。
1.项链(IOI'93第一题)
由n(n≤100)个珠子组成一个项链，珠子有红、蓝、白三种颜色，各种颜色的珠子的安
排顺序由输入文件任意给定。
图1.1可看作由字符b(代表蓝色珠子)和字符r(代表红色珠子)所组成的字符串。假定从
项链的某处将其剪断，把它摆成一直线，从一端收集同种颜色珠子(直到遇到另一种颜
色的珠子时停止)。然后再从另一端重复上述过程(请注意，这一端珠子的颜色不一定和
另一端珠子的颜色相同)。
brbrrrbbbrrrrbrrbbrbbbbrrrrb
图 1.1
请选择项链被剪断的位置，目标是使两端各自颜色相同的珠子数目之和最大。例如，对
于上图(只有红蓝两种颜色)，最大值M是8，断点位置在珠子9和珠子10之间，或珠子24
和珠子25之间。
项链中可以有三种颜色用b(蓝)、r(红)和w(白)表示。白色既可看成是红色，又可看成
蓝色。
(1)一个ASCII文件NECKLACE.DAT中的内容:该文件中每一行代表某个项链中各种颜色珠
子的配置。把输出内容写入ASCII输出文件NECKLACE.SOL中。
作为举例，输入文件的内容可以是:
brbrrrrbbbbrrrrrbbrbbbbrrrrb
bbwbrrrwbrbrrrrb
(2)对于给定的每个项链的配置，求出收集到的珠子数的最大值M及相应的断点位置(注
意可能存在多个位置)。
(3)在输出文件NECKLACE.SOL中写入收集到的珠子数的最大值M及断点位置。
例如:
brbrrrbbbrrrrrbbrbbbbrrrrb
8 between 9 and 10
bbwbrrrwbrbrrrrrb
10 between 16 and 17
作为竞赛的第一题，这道题目显然是比较简单的题目。它只包含两个步骤:剪断项链和
收集同颜色的珠子。例如下面的一条项链(a)从N=3处断开变为项链(b)。这个操作只需
要将前N个珠子移到后边即可。
brb | rrwb ------> rrwbbrb
(a) (b)
现在只剩下收集同颜色的珠子这一步，根据上面的例子我们很容易写出下面的程序。
用变量c来记录最左边珠子的颜色;
Left:=0;
FOR i:=1 TO 项链长度 DO
IF 左数第i个珠子的颜色与c相同
THEN Inc(Left)
ELSE Break;
这样变量Left中存放的就是从左边收集到的珠子的数目，同理可求得从右边收集到的珠
子的数目Right，则所求的值为Lett+Right。这个程序显然能通过上面的例子，由于这
是一道简单的题目，谁也不想在它上面多费时间，往往做到此为止。可是如果仔细想想
， 再举几个例子，就会发现错误。上面的那条项链断开后左有两个珠子为红色和蓝色
，在题目中这两种颜色的珠子都比较"普通"，只有白色的珠子比较"特殊"。所以应举一
个断开后左右两端有白色珠子的例子。还是上面那条项链入N=6处断开。
brbrrw| b------->bbrbrrw
正确答案应是收集到5个珠子:左边2个，有边3个。而上面的程序得到的结果却是3个:左
边2个，右边1个。错误就在于没有考虑到左右两端有白色珠子的情况。一种较容易的解
决方案是先将左有两端的白色珠子均取下，记其数目为Other，再用上面的程序来求，
结果为Left十Right十Other。我们解决了左右两端出现白色珠子的情况，还有没有别的
特殊情况呢?一个真正"特殊"的项链不应包含所有颜色的珠子，最好只包含一种颜色。
如下面的项链是由l0个红色的珠子组成。
rrrrrrrrrr
用我们的程序得出的结果是20个，显然是不对的。因为题目中要求是收集珠子而不是数
珠子，所以最后得到的总数不应超过珠子的总数。这虽然只是一个字眼的问题，却使当
年中国队的选手失了不少分。一个简单的改正措施是判断最后的结果是否大于珠子总数
，如果是则输出珠子的总数即可。
虽然项链这道题比较简单，却很难"简单"地得到满分，最容易出的错误就是考虑的不全
面。
2.多项式加法
由文件输入两个多项式的各项系数和指数，编程求出它们的和，并以手写的习惯输出此
多项式。
要求:
(1)多项式的每一项axb用axb的格式输出。
(2)两个多项式在文件中各占一行，每行有2m个数，依次为第一项的系数，第一项的指
数，第二项的系数，第二项的指数……
例如输入文件为:
l 2 3 0
-l 1
输出:
x2-x+3
此题是一道大学生竞赛的题目，很多人只用了很短的时间就编出程序。但最后测试的结
果却令他们很惊讶:通过的数据还不到一半!他们犯的错误归根结底就是考虑得不够全面
。
此题对于多项式相加的过程很简单，只要找出幂次相同的项相加即可。关键在于题目中
要求用符合手写的习惯输出结果。何为手写的习惯呢?例如多项式3x2-x中就有很多手写
的习惯。我们不会将其写成3x2一lx1+O。因为首先当某项系数为1时，我们习惯于不写
系数;其次对于一次项我们也要省略指数;还有我们从来不写出系数为0的项。一个简单
的多项式就有这么多的手写习惯，我们已经感觉到了要把这题全面地做出很不容易。虽
然我们平时总在写多项式，但是谁也不会留心我们写多项式时的习惯。我们写多项式的
习惯究竟有哪些呢?
(1)首先我们考虑对于多项式中的任一项axb它有多少手写习惯:
当a=0时，此项省去不写；
当a=l时，省去a；
当a=-1时，系数只写一个负号'-'；
当b=0时，省去x和b；
当b=l时，省去b；
当a<一1时，省去此项前面的加号(首项除外)。
我们一口气写了这么多条规则，每一条看起来都很正确，但合在一起是否还正确呢?当
a=l或-1时要省去其中的数字1，这是针对一般情况而言。如果b=0，则数字1就不应当省
去。所以我们不仅要单独考虑a和b，而且要将其和起来考虑。
(2)其次对于整个多项式有哪些规则呢?
多项式的首项系数前不应有加号'+'；
如果一个多项式为零多项式，则应写出数字'0'。
现在看起来这道题并不是一道很容易的题目。它需要一个人在很短的时间内能全面地总
结出上述那么多规则。这对一个人的全面考虑问题的能力是一个很好的检验。
3.求最长的公共子串(NOI'93第一题)
求N个字符串的最长公共子串，N<20，字符串长度不超过255。例如N=3，由键盘 依次输
入3个字符串为
What is local bus ?
Name some local buses.
local bus is a high speed I/O bus close to the processor.
则最长公共子串为"local bus"。
此题也是作为第一题出现，同样有很多入在此题上失分。我们都做过求n个数最大公 约
数的问题，在那道题中求3个数的最大公约数时，可以先求两个数的最大公约数，再将
此数与第三个数求一次最大公约数。有人从那道题中得到"启发"，设s(p,q)为字符串
p 和q的最长公共子串，则p、q、r的最长公共子串为s(s(p,q),r)。这样只需编写一个
求两个字符串的最长公共子串的过程即可。但这种方法对不对呢?看看下面的例子。
三个字符串分别为'abc'、'cab'、'c'，则s(p,q)='ab',s(s(p,q).r)=''。事实上这三
个字符串有公共子串'c'。显然上面的算法是错误的，原因在于没有考虑到本题与求最
大公约数那道题在性质上的不同之处。最大公约数可以由局部解得到全局解，而本题却
不能。正确的做法是列举出其中一个字符串的所有子串，找出其中最长的而且是公共的
子串。
FOR i:=l TO 第一个字符串的长度 DO
FOR j:=i TO 第一个字符串的长度 DO
IF (第i个字符到第j个字符的子串为公共子串)AND(j-i+1>当前找到的最长公共子串的
长度max)
THEN
BEGIN
max:=j-i+l;
最长公共子串:=此子串;
END;
为了提高效率，我们可以将最短的字符串作为第一个字符串。此题需要考虑的并不像多
项式加法那道题那么多，但是它提醒我们在不清楚题目的性质之前，不能滥用以前的方
法。
4.可重复排列(NOI'94第一题)
键盘输入一个仅由小写字母组成的字符串，输出以该串中任取M个字母的所有排列及排
列总数(输入数据均不需判错)。
此题是由全排列问题转变而来，不同之处在于:一个字符串中可能有相同的字符，导致
可能出现重复的排列。例如从字符串'aab'中取2个字符的排列只有三种:'aa'、'ab'、
'ba'。如何去掉那些可能重复的排列呢?一种想法就是每产生一种不同的排列就记录下
来，以便让以后产生的排列进行比较判重。这种想法显然没有考虑到随着字符串长度的
增加，排列将会多得无法记录，而且这种判重方法在效率上也会很低。最好有一种方法
能在产生排列的过程中就能将重复的去掉。先看一看全排列的递归过程
PROCEDURE Work(k);
BEGIN
IF k=m+l THEN 打印结果
ELSE FOR i:=1 TO 字符串长度n DO
IF (i<>e[l],e[2],e[k-1]) THEN
BEGIN
e[k]:=i;
Work(k+l);
END;
END;
让我们来分析产生重复的原因。考虑从字符串。'aab'中取2个字符的排列。当e[1]从l
变到2时，字符串中的字符却没有变，都是'a'。这样我们只要在改变e[k]时，判断其对
应的字符是否也改变。即在上面的过程的循环中加一句判断(设字符串为s):IF
s[i]<> s[e[k]] THEN …; 这当然只是一个粗略的想法，我们仅仅用上面的例子就能发
现问题: 程序在对e[k]的每一次赋值之前都要进行一次判断，而不是我们预想的在改变
e[k]时才进行判重。我们用一个布尔型的局部变量First来记录是否是对e[k]进行第一
次赋值。修改后的程序如下:
PROCEDURE Work(k);
BEGIN
First:=True;
IF k=m+l THEN 打印结果
ELSE FOR i:=1 TO 字符串长度n DO
IF (i<>e[l],e[2],e[k-1]) THEN
BEGIN
First:=false;
e[k]:=i;
Work(k+l);
END;
END;
很多选手的程序到此就为止了，可是它还有一个致命的错误:我们在判重时假定这个字
符串中的字符已经排好顺序，即相同的字符已经连在一起。事实上并不是这样，输入的
字符串中的字符排列是任意的，需要我们在递归之前作一次排序的初始化才能保证程序
运行得正确。可见虽然本题的难点是在递归过程中，但是那些简单的初始化却是程序最
容易忽略，最容易出错的部分。
5·删除多余括号(IOI'94国家队选拔赛第一题)
键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，
去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表
达式等价。
例:输入表达式
a+(b+c)
(a*b)+c/d
a+b/(c-d)
应输出表达式
a+b+c
a*b+c/d
a+b/(c一d)
注意输入a+b时不能输出b+a。
表达式以字符串输入，长度不超过255。输入不要判错。
所有变量为单个小写字母。只是要求去掉所有多余括号，不要求对表达式化简。
同多项式加法一样，此题要求的也是一个我们平时很习惯但却没有注意的规则:去掉多
余的括号。哪些括号是多余的呢?这要根据紧挨着括号前后的运算符号和括号中最后一
个运算符号来决定。例如表达式a+(b*c+d)-e中，括号前的符号为"+"，括号后的符号为
"-"，括号中最后一个运算符号为"+"，所以括号是多余的。总结括号中最后一个运算符
号为"+"、"-"、"*"，"/"时，括号前、后为何运算符号时括号是多余的，我们很容易得
出表1.1。
表1.1 多余的括号满足的条件
括号前的符号 括号中的符号 括号后的符号
+ + +、-
+ - +、-
+、-、* * +、-、*、/
+、-、* / +、-、*、/
上表只是对一般情况的分析，显然是很不全面的。首先括号前，括号中和括号后都可能
无运算符号，例如表达式((a))+b；其次变量前还可能带有负号，例如表达式(-a)+
(-b)中的括号一个是多余的，一个不是多余的。还有一些其它的情况如表达式只有括号
无任何变量等需要考虑。此题留给大家自己去完成。注意多用一些特殊的数据来测试自
己的程序。大家也可以试着用表达式树的方法来做此题。
"千里之堤，毁于蚁穴"。一些程序往往不是错在算法上，而是错在考虑得不全面上。希
望通过以上几个例子，能使大家对此引起重视，在以后的编程中多加注意，避免不应有
的遗憾。
--
Long long ago,there is a hero stand at the edge of the land.......
▁▁
▕天外▏
▕飞仙▏
▔▔
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.157]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店