算法合集之《測試數(shù)據(jù)設(shè)計中的三要素--準確性、全面性、美觀性》

1、準確性、全面性、美觀性測試數(shù)據(jù)設(shè)計中的三要素杭州外國語學校楊帆【關(guān)鍵字】測試數(shù)據(jù)準確性全面性美觀性【摘要】測試數(shù)據(jù)是當今信息學競賽不可或缺的有機組成部分，其作用已經(jīng)越來越被人們所重視。本文提出了測試數(shù)據(jù)設(shè)計中信、達、雅，即準確性，全面性，美觀性三要素的觀點，并就此進行了逐一論述一、引論國際信息學奧林匹克競賽(IOI)自1989年創(chuàng)辦以來已經(jīng)舉辦了整整十屆，而全國信息學奧林匹克競賽(NOI)也已有了15年的歷史。在這些年的發(fā)展過程中，信息學競賽不斷進行著自我完善，探索出了一套有自身特點的方法。信息學競賽和其他學科競賽有著很大的不同，其中之一，就是評分的方法不同：一般的學科競賽，采用的是分步給分的

2、辦法，即每一步中間過程均有相應(yīng)的分數(shù)；而信息學競賽，從早年的IOI開始，就實行了黑箱測試法，即不對源程序進行閱讀、分析，而僅僅根據(jù)源程序?qū)τ谒o定的測試數(shù)據(jù)得出的結(jié)果的正確性進行評分，所有這一切均由電腦自動完成。與相比原先的白箱測試，黑箱測試顯得更為客觀、公正、高效，因此目前被普遍采用。在黑箱測試過程中，給定的測試數(shù)據(jù)起著至關(guān)重要的作用，其重要程度，甚至不亞于題目本身。一道題目，即使再優(yōu)秀，如果沒有好的測試數(shù)據(jù)，其價值將大打折扣；同樣，一道看似平凡，或是毫不起眼的題，如果配上卓越的測試數(shù)據(jù)，往往就能夠起到令人拍案叫絕的效果。同時，測試數(shù)據(jù)也是評判題目難易的一個重要關(guān)卡，一道題目，采用不同的測試

3、數(shù)據(jù)其難易程度會有很大的差別。由此可見，測試數(shù)據(jù)是信息學競賽題中不可或缺的有機組成部分。因此，對測試數(shù)據(jù)的討論是重要的，也是必要的。著名學者嚴復曾經(jīng)在天演論·譯例言中提出“譯事三難信達雅”，把信、達、雅作為了翻譯的標準。盡管文學翻譯和信息學競賽并沒有必然聯(lián)系，但是嚴復的這個三字標準同樣可以運用在測試數(shù)據(jù)的設(shè)計上。信，是真實、確切的意思；達，是透徹、通達的意思，可引申為完備；雅，是高尚、美麗的意思。顯然，信、達、雅分別對應(yīng)了測試數(shù)據(jù)設(shè)計的三要素：準確性、全面性和美觀性。任何優(yōu)秀的測試數(shù)據(jù)，必定是這三者的完美結(jié)合。下面，本文將對測試數(shù)據(jù)設(shè)計的信、達、雅三要素進行一一論述。二、本論（1）信

4、測試數(shù)據(jù)的準確性顯然，測試數(shù)據(jù)的準確性的重要程度是至高無上的，如果失去了準確性，其他方面就無從談起，對于一道信息學競賽題來說，如果包含了錯誤的測試數(shù)據(jù)，那么它的競賽價值就等于零。具體地說，測試數(shù)據(jù)的準確性體現(xiàn)在以下幾個方面：一、測試數(shù)據(jù)的輸入輸出格式與題目要求符合；二、測試數(shù)據(jù)在題目限制的范圍之內(nèi)；三、測試數(shù)據(jù)的輸出結(jié)果是正確的。這三點，缺一不可。首先，測試數(shù)據(jù)的輸入輸出格式必須與題目要求符合。輸入和輸出格式的重要性在實行了計算機自動測試之后充分地顯示出來，因為格式的錯誤和算法的錯誤造成的后果是相同的，計算機在自動測試過程中只判別選手的輸出文件和標準輸出文件是否有區(qū)別，如果有，則判選手程序錯誤

5、。因此，如果測試數(shù)據(jù)中的標準輸出文件錯誤，將會造成所有選手正確的輸出均被判錯。同時，如果輸入數(shù)據(jù)的格式有誤，或者沒有按題目要求進行排序等，也會使選手的正確程序無法讀出正確數(shù)據(jù)，從而得到錯解。在競賽中出現(xiàn)這樣的事故，后果將不堪設(shè)想。其次，測試數(shù)據(jù)一定要在題目的限制范圍內(nèi)。所謂題目的限制范圍，有很多含義，比如題目規(guī)定的數(shù)據(jù)規(guī)模限制，數(shù)據(jù)的上界和下界，數(shù)據(jù)的類型等等。例如IOI'98天外來客一題，“輸入文件大小可達2M”是對數(shù)據(jù)規(guī)模的限制，“0<n£20，0<a£b£12”是各數(shù)據(jù)的上限和下限，而“以2表示結(jié)尾的0,1序列”就是數(shù)據(jù)的類型。在這點上，

6、任何測試數(shù)據(jù)都不能越雷池一步。在平時練習時，經(jīng)常出現(xiàn)為了測試某個程序的運算速度而采用大規(guī)模數(shù)據(jù)的情況，在解搜索題中這種現(xiàn)象更為普遍。這樣的測試方法就給測試數(shù)據(jù)的正確性埋下了很大的隱患。因為這樣的數(shù)據(jù)規(guī)模很有可能會超出題目限制，或者表面上符合題目要求，但在程序運算過程中出現(xiàn)了數(shù)據(jù)越界的情況這是最容易發(fā)生，也是最難被查出的。例如，IOI'98多邊形一題，題目規(guī)定頂點數(shù)值總在-32768,32767的范圍內(nèi)，而一般的規(guī)模稍大的測試數(shù)據(jù)往往會出現(xiàn)運算結(jié)果在范圍內(nèi)，中間數(shù)值卻在范圍外的情況，顯然這樣的數(shù)據(jù)就不是符合要求的數(shù)據(jù)。最后，也是最重要的，就是測試數(shù)據(jù)的標準輸出結(jié)果，即俗稱的“標準答案”必

7、須正確無誤。這不僅是對信息學競賽題的要求，而且是對所有學科競賽題的共同要求，甚至可以說是對所有題目的要求。要實現(xiàn)這點，對于信息學競賽來說，必須保證標準程序的準確性，因為測試數(shù)據(jù)的標準輸出結(jié)果是由標準程序產(chǎn)生的，標準程序的錯誤將直接導致測試數(shù)據(jù)標準輸出的錯誤。在設(shè)計測試數(shù)據(jù)的時候，同樣應(yīng)該對這方面加以足夠重視，決不能有麻痹思想。綜上所述，只有注意了以上三個方面，測試數(shù)據(jù)才能保證其必須的正確性。正確的測試數(shù)據(jù)才是合格的測試數(shù)據(jù)。（2）達測試數(shù)據(jù)的全面性嚴復說過：“顧信而不達，雖譯猶不譯也。”翻譯如此，測試數(shù)據(jù)的設(shè)計同樣如此。如果只考慮準確性，還遠遠不能稱得上是好的測試數(shù)據(jù)，充其量只是符合最低要求罷

8、了。因此，在做到測試數(shù)據(jù)的準確性之后，必須考慮它的全面性，只有這樣才能區(qū)分程序的優(yōu)劣，達到競賽的目的。測試數(shù)據(jù)的全面性，大致體現(xiàn)在兩個方面：一是對特殊情況的考查；二是對算法的效率和程序的時空承受能力的考查。這兩點缺一不可。下面分別對全面性的這兩個方面進行論述。對特殊情況的考查是十分重要的。所謂特殊情況，又可以分為兩種，一種是題目的邊界條件，另一種則是題目沒有明文規(guī)定禁止出現(xiàn)，而又不合常情的情況。這兩種情況都是很容易被忽略的，尤其是后者。先來討論對邊界情況的考查。每道題都有自己的限制條件，即邊界條件。顯然，當測試數(shù)據(jù)的范圍超過邊界條件時，該測試數(shù)據(jù)失去了準確性。但是，當測試數(shù)據(jù)的范圍恰好在題目的

9、邊界條件上時，就達到了對邊界條件考查的目的。這樣的測試數(shù)據(jù)，不但是準確的，而且是優(yōu)秀的。一般說來，題目的限制范圍有兩個，即上限和下限。對邊界條件的考查，一般情況下都是對題目要求的下限的考查，因為對上限的考查往往需要規(guī)模較大的數(shù)據(jù)，對算法的效率和時空承受能力有較高的要求，可以歸為對算法的效率和時空承受能力的考查一類。所以，對邊界情況的考查就是對題目限制范圍下限的考查。例如IOI'98夜空繁星一題規(guī)定“0£星座總數(shù)目£500”，這樣就可以設(shè)計一個全空的星圖，作為對星座數(shù)目等于0的邊界情況的考查。同樣是IOI'98，圓桌騎士一題規(guī)定“0£騎士數(shù)目

10、3;63”，可以依此設(shè)計沒有騎士的數(shù)據(jù)，考查選手考慮問題的全面性?？茖W界有一句名言：非絕對禁止者，皆不無可能。同樣，在信息學競賽中，只要是題目沒有明文規(guī)定禁止出現(xiàn)的情況，都有可能、且有必要出現(xiàn)在測試數(shù)據(jù)中。例如NOI'97文件匹配的第16個測試數(shù)據(jù)中就出現(xiàn)了對同一個文件，既要求進行操作，又要求不進行操作的情況。由于題目中并沒有明文規(guī)定不允許出現(xiàn)這種情況，而這個數(shù)據(jù)又恰好對此進行了考查，因此是一個漂亮的測試數(shù)據(jù)。這些特殊情況，既是選手考慮問題時容易忽視的地方，也同樣是設(shè)計測試數(shù)據(jù)時容易忽視的地方。對于這些細節(jié)，無論選手還是命題者，都必須加以足夠重視。對算法的效率和程序的時空承受能力的考查

11、同樣是十分重要的。一道題目，不同的選手在解答過程中，會建立不同的數(shù)學模型，采用不同的算法，并且，這些算法對于本題來說都是可行的?；谶@點，在測試時必須從算法效率上區(qū)分選手算法的優(yōu)劣，而這個任務(wù)，就理所當然地落到了測試數(shù)據(jù)身上。對算法的效率的考查一般使用的方法是設(shè)計大規(guī)模的測試數(shù)據(jù)，比如IOI'98多邊形一題，數(shù)據(jù)規(guī)模稍大，采用搜索法的程序，運算時間就會成幾何級數(shù)增長，而基于動態(tài)規(guī)劃算法的程序，效率就比較穩(wěn)定。顯然，通過這樣的測試，就達到了區(qū)分算法優(yōu)劣的目的。必須注意到，選手即使采用了完全相同的算法，在編程時，也會因為各種原因，用不同的數(shù)據(jù)結(jié)構(gòu)去實現(xiàn)相同的算法，這就必須對程序的時空承受能

12、力進行考查。在這里，程序的時間承受能力不僅與算法的效率有關(guān)，還與程序的優(yōu)化以及預處理的程度等各種因素有關(guān)。這點，在搜索算法中顯得尤為突出。為了對算法效率相同的程序進行優(yōu)劣區(qū)分，就必須設(shè)計一些測試數(shù)據(jù)，使進行優(yōu)化或預處理的程序能夠在規(guī)定時限內(nèi)出解，反之則不能，例如IOI'98圖形周長一題，可以設(shè)計一個矩形完全包含的數(shù)據(jù)，這樣，對此進行預處理的程序顯然就占有很大優(yōu)勢。而程序的空間承受能力與程序采用的數(shù)據(jù)結(jié)構(gòu)密切相關(guān)。采用好的數(shù)據(jù)結(jié)構(gòu)，往往能夠節(jié)省內(nèi)存開銷。顯然這些在運算時間上不能得到體現(xiàn)。因此，就必須針對這些情況，設(shè)計一些測試數(shù)據(jù)，區(qū)分程序數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣。比方說，對于搜索題，可以設(shè)法增加搜

13、索層數(shù)；對于需要處理大量數(shù)據(jù)的題可以增大數(shù)據(jù)容量；對于運算量大的題，可以增大數(shù)據(jù)規(guī)模。這樣，假如程序采用的數(shù)據(jù)結(jié)構(gòu)不是最優(yōu)的，就有可能出現(xiàn)程序執(zhí)行出錯，如棧溢出、堆溢出、超過儲存范圍等等，或者干脆造成死機。這樣一來，對于不同的程序，空間承受能力立刻得到了區(qū)分。只有算法效率高，而且數(shù)據(jù)結(jié)構(gòu)選用恰當?shù)某绦虿拍芡ㄟ^這些測試數(shù)據(jù)。這樣的數(shù)據(jù)無疑是有極大作用的。綜上所述，要做到全面測試，死板地規(guī)定5個或10個的測試數(shù)據(jù)顯然不行，測試數(shù)據(jù)的最佳數(shù)量是由題目本身決定的，和題目的難度以及要求的數(shù)據(jù)規(guī)模密切相關(guān)。少了，不能做到全面測試；多了，又起不到太大作用。例如IOI'98圓桌騎士一題，題目本身比較簡

14、單，最大規(guī)模的數(shù)據(jù)也只有63個騎士，因此只需少量數(shù)據(jù)就可以實現(xiàn)全面測試了；而像圖形周長，不僅數(shù)據(jù)規(guī)模大，而且情況繁多，使用不同的算法效率也將有較大區(qū)別，因此就必須采用較多的測試數(shù)據(jù)進行測試。同時，測試數(shù)據(jù)的難度往往能夠決定一道競賽題的難度，這也是需要十分注意的。一般情況下，可以把測試數(shù)據(jù)的分值作以下分配：簡單數(shù)據(jù)（規(guī)模較?。?5%特殊情況20%對算法效率考查（規(guī)模較大）20%對程序時空承受能力考查（規(guī)模較大）35%必須指出的是，對程序時空承受能力考查的測試數(shù)據(jù)同樣也考查了算法效率，因此上面的四部分的劃分并不截然分明。按如上比例劃分測試數(shù)據(jù)，顯得比較平均，適合一般競賽。但是，對于層次較高，或是層

15、次較低的競賽，就應(yīng)該重新設(shè)計測試數(shù)據(jù)難度比例。請看以下兩種劃分比例：一二簡單數(shù)據(jù)（規(guī)模較?。?5%5%特殊情況10%15%對算法效率考查（規(guī)模較大）20%25%對程序時空承受能力考查（規(guī)模較大）15%55%顯然，對于同一道題來說，第一種測試數(shù)據(jù)難度比例降低了題目難度，而第二種則提高了題目難度。這樣，測試數(shù)據(jù)就起到了調(diào)節(jié)題目難度的作用。這樣的例子屢見不鮮。例如NOI'98第一題個人所得稅就極為典型。這道題本身并不算難，算法一目了然。它之所以出現(xiàn)在全國競賽上，而且得分率僅為11%，就是測試數(shù)據(jù)在起調(diào)節(jié)作用。本題的10個標準測試數(shù)據(jù)有9個是對程序時空承受能力的考查，只有使用高精度運算才能得出

16、正確解。在競賽時，只有極少數(shù)選手考慮到了這點，通過了8到9個測試數(shù)據(jù)，其余選手無一幸免。不妨在此做一個假設(shè)：假如當時比賽時并沒有采用這批測試數(shù)據(jù)，而用規(guī)模較小的數(shù)據(jù)，這樣，這道題的得分率肯定在90%以上。即使在分區(qū)聯(lián)賽中，這樣的題也只能算是簡單題了。由此可見，測試數(shù)據(jù)的難度比例是極其重要的。在做到了全面測試之后，測試點分值比例分配將直接影響題目的難度和得分率。當然，這些都是建立在全面的測試數(shù)據(jù)上的。沒有全面性，測試數(shù)據(jù)就很難影響題目的難度。因此，歸根結(jié)底，測試數(shù)據(jù)的全面性才是真正的要點所在。（3）雅測試數(shù)據(jù)的美觀性僅僅做到了準確性和全面性，能不能算得上好的測試數(shù)據(jù)？答案是否定的?！白釉晦o達而已

17、，又曰言之無文，行之不遠。三者乃文章正軌，亦即為譯事楷模。故信達而外，求其而雅。”同樣，對于測試數(shù)據(jù)來說，“信達而外，求其而雅”也是不可缺少的。所謂測試數(shù)據(jù)的雅，就是指測試數(shù)據(jù)的美觀性，它和文學的“雅”是有很大區(qū)別的。后者指的是語言文字的潤色，能使文章更為生動。顯然，測試數(shù)據(jù)只是簡簡單單的字符、數(shù)字的組合，要做到生動的確是勉為其難了，因此，它的“雅”，它的美觀，是有自己獨特的含義的。但是歷來信息學競賽的命題者對此都沒有引起足夠的重視。常言道：規(guī)范是美，和諧是美。測試數(shù)據(jù)的美正是建立在這兩點的基礎(chǔ)上的。測試數(shù)據(jù)不僅僅是給電腦用來進行自動測試、自動評分的，它最終還是要給人看的。選手或是教練在賽后對

18、題目進行分析、總結(jié)時，往往要查看測試數(shù)據(jù)。此時，一個和諧、規(guī)范的測試數(shù)據(jù)起到的作用就遠遠超過一個雜亂無章的測試數(shù)據(jù)。那么，究竟怎么樣測試數(shù)據(jù)才是規(guī)范的，才是和諧的呢？不妨先看一個例子，以IOI'98圖形周長為例，給出下面五個測試數(shù)據(jù)（為了表述方便、直觀，測試數(shù)據(jù)均轉(zhuǎn)換成原始圖形）： 顯然，圖1、圖4給人的感覺要遠遠好于圖2、圖3給人的感覺，而圖5則介于兩者之間。為什么？這就是規(guī)范、和諧的作用。圖2、圖3給人雜亂無章的感覺，已經(jīng)轉(zhuǎn)換成直觀的圖形尚且如此，就更不用說原數(shù)據(jù)了。由此可以看出，規(guī)范、和諧都是相對概念，因此沒有絕對的規(guī)范和絕對的和諧。所謂規(guī)范、和諧只是人的一種感覺罷了。如果真要下

19、個定義，可以說假如只看測試數(shù)據(jù)，就能在腦中形成一個直觀的圖形，那么這個測試數(shù)據(jù)就是美的。對比這個標準，在歷年競賽的測試數(shù)據(jù)中，能夠稱得上“雅”的鳳毛麟角，更多的數(shù)據(jù)是隨機產(chǎn)生的。不可否認，隨機產(chǎn)生的數(shù)據(jù)具有一般性，在每道題的數(shù)據(jù)中攙雜幾個隨機數(shù)據(jù)的確必要，甚至是達到全面性的必須，但過多過濫的隨機數(shù)據(jù)就不但不是必須，而且破壞了整道題應(yīng)有的美感。不僅如此，當選手在賽后分析題目的時候，可以想象，如果遇到的都是隨機產(chǎn)生的測試數(shù)據(jù)，他將不可能對程序進行很好的分析，因為他讀不懂這些數(shù)據(jù)；相反，假如他遇到的是美觀的數(shù)據(jù)，那么他就可以更好地，更徹底地分析程序，人腦、電腦一起發(fā)動，自然事半功倍。因此，單就這點而言，測試數(shù)據(jù)的美觀性就是極為必要的，因為一道競賽題的價值不僅僅只在于競賽，更重要的是在賽后，選手對它分析、總結(jié)，從而提高自己的水平。如果