信息學(xué)聯(lián)賽輔導(dǎo)：全面考慮問題
2009-11-12 22:55:59網(wǎng)絡(luò)
在編程序時(shí)常常會(huì)遇到這樣的問題:一道很簡單的題目，編出的程序卻錯(cuò)了很多測試點(diǎn)。這其中的主要原因是由于考慮問題不全面，只想到了一些普通的情況，而遺漏了很多特殊的地方。
下面通過幾個(gè)例子來進(jìn)行討論。
1.項(xiàng)鏈(IOI'93第一題)
由n(n≤100)個(gè)珠子組成一個(gè)項(xiàng)鏈，珠子有紅、藍(lán)、白三種顏色，各種顏色的珠子的安排順序由輸入文件任意給定。
圖1.1可看作由字符b(代表藍(lán)色珠子)和字符r(代表紅色珠子)所組成的字符串。假定從項(xiàng)鏈的某處將其剪斷，把它擺成一直線，從一端收集同種顏色珠子(直到遇到另一種顏色的珠子時(shí)停止)。然后再從另一端重復(fù)上述過程(請注意，這一端珠子的顏色不一定和另一端珠子的顏色相同)。
brbrrrbbbrrrrbrrbbrbbbbrrrrb
圖 1.1
請選擇項(xiàng)鏈被剪斷的位置，目標(biāo)是使兩端各自顏色相同的珠子數(shù)目之和最大。例如，對于上圖(只有紅藍(lán)兩種顏色)，最大值M是8，斷點(diǎn)位置在珠子9和珠子10之間，或珠子24和珠子25之間。
項(xiàng)鏈中可以有三種顏色用b(藍(lán))、r(紅)和w(白)表示。白色既可看成是紅色，又可看成藍(lán)色。
(1)一個(gè)ASCII文件NECKLACE.DAT中的內(nèi)容:該文件中每一行代表某個(gè)項(xiàng)鏈中各種顏色珠子的配置。把輸出內(nèi)容寫入ASCII輸出文件NECKLACE.SOL中。
作為舉例，輸入文件的內(nèi)容可以是:
brbrrrrbbbbrrrrrbbrbbbbrrrrb
bbwbrrrwbrbrrrrb
(2)對于給定的每個(gè)項(xiàng)鏈的配置，求出收集到的珠子數(shù)的最大值M及相應(yīng)的斷點(diǎn)位置(注意可能存在多個(gè)位置)。
(3)在輸出文件NECKLACE.SOL中寫入收集到的珠子數(shù)的最大值M及斷點(diǎn)位置。
例如:
brbrrrbbbrrrrrbbrbbbbrrrrb
8 between 9 and 10
bbwbrrrwbrbrrrrrb
10 between 16 and 17
作為競賽的第一題，這道題目顯然是比較簡單的題目。它只包含兩個(gè)步驟:剪斷項(xiàng)鏈和收集同顏色的珠子。例如下面的一條項(xiàng)鏈(a)從N=3處斷開變?yōu)轫?xiàng)鏈(b)。這個(gè)操作只需要將前N個(gè)珠子移到后邊即可。
brb | rrwb ------> rrwbbrb
(a) (b)
現(xiàn)在只剩下收集同顏色的珠子這一步，根據(jù)上面的例子我們很容易寫出下面的程序。
用變量c來記錄最左邊珠子的顏色;
Left:=0;
FOR i:=1 TO 項(xiàng)鏈長度 DO
IF 左數(shù)第i個(gè)珠子的顏色與c相同
THEN Inc(Left)
ELSE Break;
這樣變量Left中存放的就是從左邊收集到的珠子的數(shù)目，同理可求得從右邊收集到的珠子的數(shù)目Right，則所求的值為Lett+Right。這個(gè)程序顯然能通過上面的例子，由于這是一道簡單的題目，誰也不想在它上面多費(fèi)時(shí)間，往往做到此為止�？墒侨绻屑�(xì)想想，再舉幾個(gè)例子，就會(huì)發(fā)現(xiàn)錯(cuò)誤。上面的那條項(xiàng)鏈斷開后左有兩個(gè)珠子為紅色和藍(lán)色，在題目中這兩種顏色的珠子都比較"普通"，只有白色的珠子比較"特殊"。所以應(yīng)舉一個(gè)斷開后左右兩端有白色珠子的例子。還是上面那條項(xiàng)鏈入N=6處斷開。
brbrrw| b------->bbrbrrw
正確答案應(yīng)是收集到5個(gè)珠子:左邊2個(gè)，有邊3個(gè)。而上面的程序得到的結(jié)果卻是3個(gè):左邊2個(gè)，右邊1個(gè)。錯(cuò)誤就在于沒有考慮到左右兩端有白色珠子的情況。一種較容易的解決方案是先將左有兩端的白色珠子均取下，記其數(shù)目為Other，再用上面的程序來求，結(jié)果為Left十Right十Other。我們解決了左右兩端出現(xiàn)白色珠子的情況，還有沒有別的特殊情況呢?一個(gè)真正"特殊"的項(xiàng)鏈不應(yīng)包含所有顏色的珠子，最好只包含一種顏色。如下面的項(xiàng)鏈?zhǔn)怯蒷0個(gè)紅色的珠子組成。
rrrrrrrrrr
用我們的程序得出的結(jié)果是20個(gè)，顯然是不對的。因?yàn)轭}目中要求是收集珠子而不是數(shù)珠子，所以最后得到的總數(shù)不應(yīng)超過珠子的總數(shù)。這雖然只是一個(gè)字眼的問題，卻使當(dāng)年中國隊(duì)的選手失了不少分。一個(gè)簡單的改正措施是判斷最后的結(jié)果是否大于珠子總數(shù)，如果是則輸出珠子的總數(shù)即可。
雖然項(xiàng)鏈這道題比較簡單，卻很難"簡單"地得到滿分，最容易出的錯(cuò)誤就是考慮的不全面。
2.多項(xiàng)式加法
由文件輸入兩個(gè)多項(xiàng)式的各項(xiàng)系數(shù)和指數(shù)，編程求出它們的和，并以手寫的習(xí)慣輸出此多項(xiàng)式。
要求:
(1)多項(xiàng)式的每一項(xiàng)axb用axb的格式輸出。
(2)兩個(gè)多項(xiàng)式在文件中各占一行，每行有2m個(gè)數(shù)，依次為第一項(xiàng)的系數(shù)，第一項(xiàng)的指數(shù)，第二項(xiàng)的系數(shù)，第二項(xiàng)的指數(shù)……
例如輸入文件為:
l 2 3 0
-l 1
輸出:
x2-x+3
此題是一道大學(xué)生競賽的題目，很多人只用了很短的時(shí)間就編出程序。但最后測試的結(jié)果卻令他們很驚訝:通過的數(shù)據(jù)還不到一半!他們犯的錯(cuò)誤歸根結(jié)底就是考慮得不夠全面。
此題對于多項(xiàng)式相加的過程很簡單，只要找出冪次相同的項(xiàng)相加即可。關(guān)鍵在于題目中要求用符合手寫的習(xí)慣輸出結(jié)果。何為手寫的習(xí)慣呢?例如多項(xiàng)式3x2-x中就有很多手寫的習(xí)慣。我們不會(huì)將其寫成3x2一lx1+O。因?yàn)槭紫犬?dāng)某項(xiàng)系數(shù)為1時(shí)，我們習(xí)慣于不寫系數(shù);其次對于一次項(xiàng)我們也要省略指數(shù);還有我們從來不寫出系數(shù)為0的項(xiàng)。一個(gè)簡單的多項(xiàng)式就有這么多的手寫習(xí)慣，我們已經(jīng)感覺到了要把這題全面地做出很不容易。雖然我們平時(shí)總在寫多項(xiàng)式，但是誰也不會(huì)留心我們寫多項(xiàng)式時(shí)的習(xí)慣。我們寫多項(xiàng)式的習(xí)慣究竟有哪些呢?
(1)首先我們考慮對于多項(xiàng)式中的任一項(xiàng)axb它有多少手寫習(xí)慣:
- 當(dāng)a=0時(shí)，此項(xiàng)省去不寫；
- 當(dāng)a=l時(shí)，省去a；
- 當(dāng)a=-1時(shí)，系數(shù)只寫一個(gè)負(fù)號'-'；
- 當(dāng)b=0時(shí)，省去x和b；
- 當(dāng)b=l時(shí)，省去b；
- 當(dāng)a<一1時(shí)，省去此項(xiàng)前面的加號(首項(xiàng)除外)。
我們一口氣寫了這么多條規(guī)則，每一條看起來都很正確，但合在一起是否還正確呢?當(dāng)a=l或-1時(shí)要省去其中的數(shù)字1，這是針對一般情況而言。如果b=0，則數(shù)字1就不應(yīng)當(dāng)省去。所以我們不僅要單獨(dú)考慮a和b，而且要將其和起來考慮。
(2)其次對于整個(gè)多項(xiàng)式有哪些規(guī)則呢?
- 多項(xiàng)式的首項(xiàng)系數(shù)前不應(yīng)有加號'+'；
- 如果一個(gè)多項(xiàng)式為零多項(xiàng)式，則應(yīng)寫出數(shù)字'0'。
現(xiàn)在看起來這道題并不是一道很容易的題目。它需要一個(gè)人在很短的時(shí)間內(nèi)能全面地總結(jié)出上述那么多規(guī)則。這對一個(gè)人的全面考慮問題的能力是一個(gè)很好的檢驗(yàn)。
3.求最長的公共子串(NOI'93第一題)
求N個(gè)字符串的最長公共子串，N<20，字符串長度不超過255。例如N=3，由鍵盤 依次輸入3個(gè)字符串為
What is local bus ?
Name some local buses.
local bus is a high speed I/O bus close to the processor.
則最長公共子串為"local bus"。
此題也是作為第一題出現(xiàn)，同樣有很多入在此題上失分。我們都做過求n個(gè)數(shù)最大公 約數(shù)的問題，在那道題中求3個(gè)數(shù)的最大公約數(shù)時(shí)，可以先求兩個(gè)數(shù)的最大公約數(shù)，再將此數(shù)與第三個(gè)數(shù)求一次最大公約數(shù)。有人從那道題中得到"啟發(fā)"，設(shè)s(p,q)為字符串p 和q的最長公共子串，則p、q、r的最長公共子串為s(s(p,q),r)。這樣只需編寫一個(gè)求兩個(gè)字符串的最長公共子串的過程即可。但這種方法對不對呢?看看下面的例子。
三個(gè)字符串分別為'abc'、'cab'、'c'，則s(p,q)='ab',s(s(p,q).r)=''。事實(shí)上這三個(gè)字符串有公共子串'c'。顯然上面的算法是錯(cuò)誤的，原因在于沒有考慮到本題與求最大公約數(shù)那道題在性質(zhì)上的不同之處。最大公約數(shù)可以由局部解得到全局解，而本題卻不能。正確的做法是列舉出其中一個(gè)字符串的所有子串，找出其中最長的而且是公共的子串。
FOR i:=l TO 第一個(gè)字符串的長度 DO
FOR j:=i TO 第一個(gè)字符串的長度 DO
IF (第i個(gè)字符到第j個(gè)字符的子串為公共子串)AND(j-i+1>當(dāng)前找到的最長公共子串的長度max)
THEN
BEGIN
max:=j-i+l;
最長公共子串:=此子串;
END;
為了提高效率，我們可以將最短的字符串作為第一個(gè)字符串。此題需要考慮的并不像多項(xiàng)式加法那道題那么多，但是它提醒我們在不清楚題目的性質(zhì)之前，不能濫用以前的方法。
4.可重復(fù)排列(NOI'94第一題)
鍵盤輸入一個(gè)僅由小寫字母組成的字符串，輸出以該串中任取M個(gè)字母的所有排列及排列總數(shù)(輸入數(shù)據(jù)均不需判錯(cuò))。
此題是由全排列問題轉(zhuǎn)變而來，不同之處在于:一個(gè)字符串中可能有相同的字符，導(dǎo)致可能出現(xiàn)重復(fù)的排列。例如從字符串'aab'中取2個(gè)字符的排列只有三種:'aa'、'ab'、'ba'。如何去掉那些可能重復(fù)的排列呢?一種想法就是每產(chǎn)生一種不同的排列就記錄下來，以便讓以后產(chǎn)生的排列進(jìn)行比較判重。這種想法顯然沒有考慮到隨著字符串長度的增加，排列將會(huì)多得無法記錄，而且這種判重方法在效率上也會(huì)很低。最好有一種方法能在產(chǎn)生排列的過程中就能將重復(fù)的去掉。先看一看全排列的遞歸過程
PROCEDURE Work(k);
BEGIN
IF k=m+l THEN 打印結(jié)果
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;
讓我們來分析產(chǎn)生重復(fù)的原因。考慮從字符串。'aab'中取2個(gè)字符的排列。當(dāng)e[1]從l變到2時(shí)，字符串中的字符卻沒有變，都是'a'。這樣我們只要在改變e[k]時(shí)，判斷其對應(yīng)的字符是否也改變。即在上面的過程的循環(huán)中加一句判斷(設(shè)字符串為s):IF s[i]<> s[e[k]] THEN …; 這當(dāng)然只是一個(gè)粗略的想法，我們僅僅用上面的例子就能發(fā)現(xiàn)問題: 程序在對e[k]的每一次賦值之前都要進(jìn)行一次判斷，而不是我們預(yù)想的在改變e[k]時(shí)才進(jìn)行判重。我們用一個(gè)布爾型的局部變量First來記錄是否是對e[k]進(jìn)行第一次賦值。修改后的程序如下:
PROCEDURE Work(k);
BEGIN
First:=True;
IF k=m+l THEN 打印結(jié)果
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;
很多選手的程序到此就為止了，可是它還有一個(gè)致命的錯(cuò)誤:我們在判重時(shí)假定這個(gè)字符串中的字符已經(jīng)排好順序，即相同的字符已經(jīng)連在一起。事實(shí)上并不是這樣，輸入的字符串中的字符排列是任意的，需要我們在遞歸之前作一次排序的初始化才能保證程序運(yùn)行得正確�？梢婋m然本題的難點(diǎn)是在遞歸過程中，但是那些簡單的初始化卻是程序最容易忽略，最容易出錯(cuò)的部分。
5·刪除多余括號(IOI'94國家隊(duì)選拔賽第一題)
鍵盤輸入一個(gè)含有括號的四則運(yùn)算表達(dá)式，可能含有多余的括號，編程整理該表達(dá)式，去掉所有多余的括號，原表達(dá)式中所有變量和運(yùn)算符相對位置保持不變，并保持與原表達(dá)式等價(jià)。
例:輸入表達(dá)式
a+(b+c)
(a*b)+c/d
a+b/(c-d)
應(yīng)輸出表達(dá)式
a+b+c
a*b+c/d
a+b/(c一d)
注意輸入a+b時(shí)不能輸出b+a。
表達(dá)式以字符串輸入，長度不超過255。輸入不要判錯(cuò)。
所有變量為單個(gè)小寫字母。只是要求去掉所有多余括號，不要求對表達(dá)式化簡。
同多項(xiàng)式加法一樣，此題要求的也是一個(gè)我們平時(shí)很習(xí)慣但卻沒有注意的規(guī)則:去掉多余的括號。哪些括號是多余的呢?這要根據(jù)緊挨著括號前后的運(yùn)算符號和括號中最后一個(gè)運(yùn)算符號來決定。例如表達(dá)式a+(b*c+d)-e中，括號前的符號為"+"，括號后的符號為"-"，括號中最后一個(gè)運(yùn)算符號為"+"，所以括號是多余的�？偨Y(jié)括號中最后一個(gè)運(yùn)算符號為"+"、"-"、"*"，"/"時(shí)，括號前、后為何運(yùn)算符號時(shí)括號是多余的，我們很容易得出表1.1。
表1.1 多余的括號滿足的條件
|
括號前的符號
|
括號中的符號
|
括號后的符號
|
|
+
|
+
|
+、-
|
|
+
|
-
|
+、-
|
|
+、-、*
|
*
|
+、-、*、/
|
|
+、-、*
|
/
|
+、-、*、/
|
上表只是對一般情況的分析，顯然是很不全面的。首先括號前，括號中和括號后都可能無運(yùn)算符號，例如表達(dá)式((a))+b；其次變量前還可能帶有負(fù)號，例如表達(dá)式(-a)+ (-b)中的括號一個(gè)是多余的，一個(gè)不是多余的。還有一些其它的情況如表達(dá)式只有括號無任何變量等需要考慮。此題留給大家自己去完成。注意多用一些特殊的數(shù)據(jù)來測試自己的程序。大家也可以試著用表達(dá)式樹的方法來做此題。
6.合并表格(NOI'93第二題)
在兩個(gè)文本文件中各存有一個(gè)西文制表符制成的未填入任何表項(xiàng)的表結(jié)構(gòu)，分別稱之為表1和表2，要求編程將表1和表2按下述規(guī)則合并成表3。
規(guī)則:表1在上表2在下，表1與表2在左邊框?qū)R，將表1的最底行與表2的最頂行合并。
例如，3張表見圖1.2。
|
|
|
||||||||||||||||||||||
|
表1
|
表2
|
表3
|
圖1.2
編程要求:
(l)程序應(yīng)能從給定的文本文件中讀入兩個(gè)源表并顯示。
(2)若源表有錯(cuò)，應(yīng)能指出其錯(cuò)(錯(cuò)誤只出在表1的最底行和表2的第一行)。
(3)將表1和表2按規(guī)則合并成表3，并顯示之。
(4)所有制表符的ASCII碼應(yīng)由選手自己從給出的示例文件中截取。
我們把此題的分析留給讀者去獨(dú)立完成。
"千里之堤，毀于蟻穴"。一些程序往往不是錯(cuò)在算法上，而是錯(cuò)在考慮得不全面上。希望通過以上幾個(gè)例子，能使大家對此引起重視，在以后的編程中多加注意，避免不應(yīng)有的遺憾。
