信息學聯賽輔導：全面考慮問題
2009-11-12 22:55:59網絡
在編程序時常常會遇到這樣的問題:一道很簡單的題目，編出的程序卻錯了很多測試點。這其中的主要原因是由于考慮問題不全面，只想到了一些普通的情況，而遺漏了很多特殊的地方。
下面通過幾個例子來進行討論。
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處斷開變?yōu)轫楁?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。這個程序顯然能通過上面的例子，由于這是一道簡單的題目，誰也不想在它上面多費時間，往往做到此為止�？墒侨绻屑毾胂耄倥e幾個例子，就會發(fā)現錯誤。上面的那條項鏈斷開后左有兩個珠子為紅色和藍色，在題目中這兩種顏色的珠子都比較"普通"，只有白色的珠子比較"特殊"。所以應舉一個斷開后左右兩端有白色珠子的例子。還是上面那條項鏈入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時，省去此項前面的加號(首項除外)。
我們一口氣寫了這么多條規(guī)則，每一條看起來都很正確，但合在一起是否還正確呢?當a=l或-1時要省去其中的數字1，這是針對一般情況而言。如果b=0，則數字1就不應當省去。所以我們不僅要單獨考慮a和b，而且要將其和起來考慮。
(2)其次對于整個多項式有哪些規(guī)則呢?
- 多項式的首項系數前不應有加號'+'；
- 如果一個多項式為零多項式，則應寫出數字'0'。
現在看起來這道題并不是一道很容易的題目。它需要一個人在很短的時間內能全面地總結出上述那么多規(guī)則。這對一個人的全面考慮問題的能力是一個很好的檢驗。
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個數的最大公約數時，可以先求兩個數的最大公約數，再將此數與第三個數求一次最大公約數。有人從那道題中得到"啟發(fā)"，設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]時，判斷其對應的字符是否也改變。即在上面的過程的循環(huán)中加一句判斷(設字符串為s):IF s[i]<> s[e[k]] THEN …; 這當然只是一個粗略的想法，我們僅僅用上面的例子就能發(fā)現問題: 程序在對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。輸入不要判錯。
所有變量為單個小寫字母。只是要求去掉所有多余括號，不要求對表達式化簡。
同多項式加法一樣，此題要求的也是一個我們平時很習慣但卻沒有注意的規(guī)則:去掉多余的括號。哪些括號是多余的呢?這要根據緊挨著括號前后的運算符號和括號中最后一個運算符號來決定。例如表達式a+(b*c+d)-e中，括號前的符號為"+"，括號后的符號為"-"，括號中最后一個運算符號為"+"，所以括號是多余的�？偨Y括號中最后一個運算符號為"+"、"-"、"*"，"/"時，括號前、后為何運算符號時括號是多余的，我們很容易得出表1.1。
表1.1 多余的括號滿足的條件
|
括號前的符號
|
括號中的符號
|
括號后的符號
|
|
+
|
+
|
+、-
|
|
+
|
-
|
+、-
|
|
+、-、*
|
*
|
+、-、*、/
|
|
+、-、*
|
/
|
+、-、*、/
|
上表只是對一般情況的分析，顯然是很不全面的。首先括號前，括號中和括號后都可能無運算符號，例如表達式((a))+b；其次變量前還可能帶有負號，例如表達式(-a)+ (-b)中的括號一個是多余的，一個不是多余的。還有一些其它的情況如表達式只有括號無任何變量等需要考慮。此題留給大家自己去完成。注意多用一些特殊的數據來測試自己的程序。大家也可以試著用表達式樹的方法來做此題。
6.合并表格(NOI'93第二題)
在兩個文本文件中各存有一個西文制表符制成的未填入任何表項的表結構，分別稱之為表1和表2，要求編程將表1和表2按下述規(guī)則合并成表3。
規(guī)則:表1在上表2在下，表1與表2在左邊框對齊，將表1的最底行與表2的最頂行合并。
例如，3張表見圖1.2。
|
|
|
||||||||||||||||||||||
|
表1
|
表2
|
表3
|
圖1.2
編程要求:
(l)程序應能從給定的文本文件中讀入兩個源表并顯示。
(2)若源表有錯，應能指出其錯(錯誤只出在表1的最底行和表2的第一行)。
(3)將表1和表2按規(guī)則合并成表3，并顯示之。
(4)所有制表符的ASCII碼應由選手自己從給出的示例文件中截取。
我們把此題的分析留給讀者去獨立完成。
"千里之堤，毀于蟻穴"。一些程序往往不是錯在算法上，而是錯在考慮得不全面上。希望通過以上幾個例子，能使大家對此引起重視，在以后的編程中多加注意，避免不應有的遺憾。
