論程序的調(diào)試技巧

1、論程序的調(diào)試技巧論程序的調(diào)試技巧關(guān)鍵字】調(diào)試技巧、測(cè)試方法、測(cè)試用例設(shè)計(jì) 【摘要】 本文結(jié)合作者自身經(jīng)驗(yàn)， 對(duì)競(jìng)賽中程序的調(diào)試技巧做了詳細(xì)的闡述和總結(jié)。 在介紹了編程中常見(jiàn)的錯(cuò)誤類(lèi)型和集成環(huán)境 的調(diào)試工具之后， 給出了一般調(diào)試流程， 并著重講述了其中的動(dòng) 態(tài)查錯(cuò)技巧， 做了一定的歸納。 最后通過(guò)一個(gè)調(diào)試實(shí)例來(lái)體現(xiàn)本 文所論述的調(diào)試技巧的具體應(yīng)用?！菊摹恳弧⒊绦蛘{(diào)試的必要性 程序設(shè)計(jì)過(guò)程中，錯(cuò)誤是在所難免的。雖然有些程序員認(rèn)為一個(gè)程序可以 做到完美無(wú)瑕，但實(shí)際情況卻并非如此，不然就不會(huì)有人對(duì) Windows 怨氣沖天 了。盡管信息學(xué)競(jìng)賽中所編的程序從來(lái)不會(huì)像 Windows 那樣龐大，最多也是

2、僅 僅幾百 K 而已，但由于時(shí)間有限，選手們的程序難免有疏漏之處。因此，調(diào)試 就成了極其重要的一環(huán)。如何在緊迫的時(shí)間內(nèi)快速準(zhǔn)確地發(fā)現(xiàn)并改正錯(cuò)誤，正 是本文所要討論的問(wèn)題。二、常見(jiàn)錯(cuò)誤類(lèi)型歸納孫子兵法云： “知己知彼，百戰(zhàn)不殆。 ”對(duì)于程序調(diào)試者來(lái)說(shuō)，程序中 的錯(cuò)誤就好比是敵人，如能準(zhǔn)確把握敵人的情況，無(wú)疑是極為有利的。下面我 們就來(lái)對(duì)常見(jiàn)的一些錯(cuò)誤類(lèi)型進(jìn)行歸納并給出解決方法。1、思路錯(cuò)誤 這要看是基本算法錯(cuò)誤還是功能缺陷。前者需要重寫(xiě)大部分代碼，是否重 寫(xiě)則根據(jù)時(shí)間是否充裕而定，后者只需增加一部分代碼，再修改某些地方，這 時(shí)應(yīng)全面考慮，以防遺漏應(yīng)該修改的地方。2、語(yǔ)法錯(cuò)誤 這個(gè)沒(méi)什么可說(shuō)的，作

3、為一名信息學(xué)競(jìng)賽的選手，應(yīng)該對(duì)自己選擇的編程 語(yǔ)言的語(yǔ)法了如指掌，具體在這里就不多講了。3、書(shū)寫(xiě)錯(cuò)誤 這種錯(cuò)誤令人十分頭痛，一般的書(shū)寫(xiě)錯(cuò)誤在編譯時(shí)都能找出來(lái)，但如果你 在表達(dá)式中用到變量j時(shí)誤寫(xiě)成了 i,不但編譯程序找不出來(lái)，自己找時(shí)也由于 兩者樣子比較相似，難以發(fā)現(xiàn)。排除這種錯(cuò)誤只能靠“細(xì)心”兩字，具體可使 用下面要介紹的靜態(tài)查錯(cuò)法。4、輸出格式錯(cuò)誤 由于現(xiàn)在信息學(xué)競(jìng)賽采用黑箱測(cè)試法，由于輸出格式錯(cuò)誤而導(dǎo)致失分的例 子屢見(jiàn)不鮮。一個(gè)標(biāo)點(diǎn)，一個(gè)空格，都會(huì)導(dǎo)致最后的悔恨。因此，在調(diào)試時(shí)先要核對(duì)輸出格式，針對(duì)不同輸出格式多設(shè)計(jì)幾個(gè)測(cè)試用例，以防一失足成千古 恨。5、其它編程時(shí)易犯的錯(cuò)誤 除了上面所

4、說(shuō)的錯(cuò)誤類(lèi)型外，其它就屬于編程時(shí)在細(xì)節(jié)上考慮不周所造成 的了。下面僅列舉其中一些較為隱蔽的錯(cuò)誤。只有靠平時(shí)不斷總結(jié)積累，才能 真正的做到“知己知彼” 。 變量未賦初值 看下面的程序段For i： =1 to N DoIf Ai>Max Then Max ：=Ai ；WriteLn （Max ）；這個(gè)程序段的原意顯然是要輸出數(shù)組 A 中最大的數(shù)。但由于它遺漏了將 Max 賦初值的語(yǔ)句，因此很可能會(huì)出現(xiàn)輸出的數(shù)并不在數(shù)組 A 中的錯(cuò)誤。應(yīng)該 在過(guò)程開(kāi)頭添上一句 Max ：=-MaxInt ；。養(yǎng)成變量使用前先賦初值的習(xí)慣能預(yù)防 許多較隱蔽的錯(cuò)誤。 中間運(yùn)算越界 看下面這兩句語(yǔ)句 A： =10

5、00； B： =A*A Div 100；其中A, B都是Integer類(lèi)型。按照我們的想法，1000*1000 Div 100=10000。然而當(dāng)我們察看B的值的時(shí)候，卻發(fā)現(xiàn) B等于169。原因是PascaI在進(jìn)行編譯 時(shí)，總是先計(jì)算出 A*A，把它放到一個(gè)中間變量中，然后再計(jì)算出最后結(jié)果放 入B中。而A*A超出了 Integer的范圍，這就是造成錯(cuò)誤的根本原因。要使Pascal 能報(bào)告這類(lèi)錯(cuò)誤，只要打開(kāi)編譯開(kāi)關(guān) Q 即可。對(duì)此類(lèi)錯(cuò)誤解決方法是使用強(qiáng)制 類(lèi)型轉(zhuǎn)換，寫(xiě)成 B：=LongInt（A）*A Div 100。編譯程序會(huì)自動(dòng)把中間變量規(guī) 定為 LongInt 類(lèi)型，就不會(huì)越界了。 局部變

6、量與全局變量同名造成概念混亂這個(gè)實(shí)際上不能算錯(cuò)誤，然而有許多錯(cuò)誤正是因此而起。一個(gè)常見(jiàn)的錯(cuò)誤是當(dāng)我們?cè)谶^(guò)程中使用全局變量時(shí)，忘記了自己在該過(guò)程中還定義了一個(gè)同名 的局部變量，從而使得實(shí)際的程序與我們的思路不一致；另一個(gè)常見(jiàn)的錯(cuò)誤是 局部變量忘記定義，在過(guò)程（函數(shù)）中實(shí)際上使用的是全局變量，而出現(xiàn)錯(cuò)誤 往往是在這個(gè)過(guò)程（函數(shù)）之外某個(gè)需要使用該全局變量的地方，這就增加了 調(diào)試的難度。因此，應(yīng)該盡量避免使用同名變量。 If-Then-Else 語(yǔ)句混亂Pascal對(duì)If-Then-Else語(yǔ)句的規(guī)定是：If-Then語(yǔ)句可以沒(méi)有 Else語(yǔ)句與之 相匹配；Else語(yǔ)句總是匹配最近的If-Then語(yǔ)

7、句。這一點(diǎn)使得我們?cè)谑褂们短椎?If-Else 語(yǔ)句時(shí)容易出錯(cuò)。如下面這個(gè)例子：If 條件 aThen If 條件 b Then 代碼段 bElse 代碼段 a我們的原意是讓代碼段a在條件a不成立時(shí)執(zhí)行，但由于Else語(yǔ)句總是匹 配最近的If-Then語(yǔ)句，因此這個(gè)Else是與If條件b Then這個(gè)語(yǔ)句相匹配的， 也就是說(shuō)代碼段 a 要滿(mǎn)足條件 a 成立且條件 b 不成立時(shí)才會(huì)執(zhí)行，與我們?cè)庀嗳ド踹h(yuǎn)。解決方法是在需要的地方加一個(gè)空的Else,就如上面的例子，要在If 條件 b Then 語(yǔ)句后面加一個(gè)空的 Else。 實(shí)數(shù)比較出錯(cuò) 在比較兩個(gè)實(shí)數(shù)是否相等時(shí)，如果直接用等號(hào)，往往會(huì)造成錯(cuò)誤。

8、這是浮 點(diǎn)運(yùn)算存在誤差所造成的，解決辦法是使用兩數(shù)差的絕對(duì)值與一個(gè)相對(duì)極小量 進(jìn)行比較，一般說(shuō)來(lái)如果 abs（a-b）1e-8,則可認(rèn)為a=b。三、集成環(huán)境的調(diào)試工具對(duì)于一個(gè)戰(zhàn)士來(lái)說(shuō)，對(duì)自己手中的武器性能特點(diǎn)應(yīng)該了如指掌。對(duì)于程序 調(diào)試者來(lái)說(shuō)，調(diào)試工具就相當(dāng)于武器，熟練掌握調(diào)試工具，充分發(fā)揮它的性能， 對(duì)于迅速找出錯(cuò)誤，加快我們的調(diào)試速度有著極大的幫助。下面就對(duì)集成環(huán)境 提供的調(diào)試工具做一些介紹。調(diào)試時(shí)主要使用的兩個(gè)菜單是 Run和Debug。Run菜單提供了各種程序執(zhí) 行方式，而 Debug 菜單提供了對(duì)變量的觀察，修改以及斷點(diǎn)等功能。 程序的執(zhí)行方式有四種：1、Run，運(yùn)行整個(gè)程序（Ctr

9、l+F9 ），該方式常用在總體測(cè)試上。一般每一個(gè)測(cè) 試用例都應(yīng)先用該方式執(zhí)行程序，如果輸出答案正確就可以直接轉(zhuǎn)到下一個(gè) 測(cè)試用例，免去了不必要的時(shí)間。即使發(fā)現(xiàn)錯(cuò)誤也只不過(guò)比直接進(jìn)入模塊調(diào) 試增加了一點(diǎn)點(diǎn)時(shí)間，是完全值得的。2、 Step over，單步執(zhí)行，把整個(gè)過(guò)程（函數(shù)）視為單步一次執(zhí)行（F8），該方 式常用在模塊調(diào)試時(shí)期，可以通過(guò)觀察變量在模塊執(zhí)行前后的變化情況來(lái)確 定該模塊中是否存在錯(cuò)誤，也可以用來(lái)跳過(guò)已測(cè)試完畢的模塊。3、 Trace into,單步執(zhí)行，對(duì)于過(guò)程（函數(shù)）進(jìn)入到內(nèi)部一步步執(zhí)行（F7），該 方式常用在底層調(diào)試時(shí)期，可以跟蹤程序的每步執(zhí)行過(guò)程。它的優(yōu)點(diǎn)是容易 直接定位錯(cuò)誤

10、，缺點(diǎn)是調(diào)試速度較慢，尤其是當(dāng)錯(cuò)誤位于程序后部時(shí)。所以 一般是采用先用模塊調(diào)試法盡量縮小錯(cuò)誤范圍，然后使用第 4 種執(zhí)行方式和 斷點(diǎn)來(lái)快速跳過(guò)沒(méi)有出現(xiàn)錯(cuò)誤的部分，最后才是用該方式來(lái)逐步跟蹤找出錯(cuò)誤。4、Go to cursor,執(zhí)行到光標(biāo)處（F4），之所以把這種方式放在最后介紹，是因 為這種方式的靈活度較大，不但可以一次執(zhí)行一行，也可以一次執(zhí)行多行； 可以直接跳過(guò)過(guò)程（函數(shù)） ，也可以進(jìn)入過(guò)程（函數(shù)）內(nèi)部。它有斷點(diǎn)的定位 能力強(qiáng)的優(yōu)點(diǎn)，又比斷點(diǎn)更加靈活。正確適當(dāng)?shù)厥褂眠@種方式可以大大加快 我們調(diào)試的速度，這需要靠豐富的調(diào)試經(jīng)驗(yàn)?？梢詤⒖己竺娴恼{(diào)試實(shí)例。Debug菜單中最常用選項(xiàng)是 Watch和

11、Add Watch，這兩個(gè)用于跟蹤觀察變 量和表達(dá)式在程序執(zhí)行過(guò)程中值的變化，這樣就可以隨時(shí)檢查它們是否按照算 法要求輸出，是否符合正確答案。大多數(shù)錯(cuò)誤在調(diào)試時(shí)都可以只使用它們以及 上面的四種執(zhí)行方式被檢查出來(lái)。有的時(shí)候，雖然知道該模塊有錯(cuò)，但一時(shí)無(wú)法找到錯(cuò)誤所在，并且上面所 講的后三種執(zhí)行方式都難以快速定位。例如對(duì)于一個(gè)程序，我們需要它執(zhí)行到 某個(gè)語(yǔ)句并滿(mǎn)足某個(gè)條件時(shí)停下來(lái)，Go to cursor只能保證執(zhí)行到這個(gè)語(yǔ)句時(shí)停下來(lái)，卻不能保證滿(mǎn)足條件，這時(shí)我們便需要使用斷點(diǎn)。斷點(diǎn)雖然沒(méi)有 Go to cursor靈活，但有一個(gè)Go to cursor無(wú)法取代的優(yōu)勢(shì)便是它可以設(shè)置中斷條件。 使用

12、 Add Breakpoint 選項(xiàng)（ Ctrl+F8 ）可以在當(dāng)前光標(biāo)處設(shè)置一個(gè)斷點(diǎn)， Breakpoints選項(xiàng)可以編輯斷點(diǎn)條件。要注意的是，斷點(diǎn)的設(shè)置會(huì)大大降低程序 執(zhí)行效率，因此調(diào)試完畢以后一定要記得清除所有斷點(diǎn)。Evaluate/modify選項(xiàng)（Ctrl+F4 ）用于臨時(shí)觀察修改表達(dá)式的值，如果在調(diào)試過(guò)程中，需要臨時(shí)觀察或修改某個(gè)表達(dá)式的值，則可以打開(kāi)Evaluate andmodify窗口進(jìn)行操作。這個(gè)方法尤其適用于對(duì)過(guò)程（函數(shù)）的調(diào)試，我們可以先用Go to cursor執(zhí)行到某個(gè)過(guò)程（函數(shù)）的開(kāi)頭，然后使用Evaluate/modify選項(xiàng)改變參數(shù)的值用于檢查不同情況下這個(gè)過(guò)

13、程（函數(shù)）的執(zhí)行結(jié)果。但是要 注意，一個(gè)過(guò)程（函數(shù)）通常不是孤立的，它經(jīng)常需要使用某些全局變量，因 此僅改變參數(shù)而不改變其他全局變量的值有可能是非法的。所以需要特別的小 心，避免出現(xiàn)這樣的情況。Call stack選項(xiàng)（Ctrl+F3）用于顯示當(dāng)前堆棧狀態(tài)，這特別適用于對(duì)遞歸算 法的調(diào)試。我們可以利用它察看每層參數(shù)的傳遞情況。不過(guò)一般來(lái)說(shuō)參數(shù)的傳 遞不易出錯(cuò)，因此該選項(xiàng)的用處并不是很大。四、調(diào)試的一般過(guò)程對(duì)于一道題我們一般按照以下流程圖進(jìn)行調(diào)試：這只是針對(duì)一般情況而言，在具體調(diào)試時(shí)，可以改變某些步驟，比如說(shuō)在 發(fā)現(xiàn)某個(gè)模塊有錯(cuò)誤改正以后，可以不返回到靜態(tài)查錯(cuò)階段，而是繼續(xù)該模塊 的查錯(cuò)。這要視

14、具體情況而定。下面我們對(duì)各個(gè)步驟作詳細(xì)的敘述。1、靜態(tài)查錯(cuò)靜態(tài)查錯(cuò)是指不執(zhí)行程序，僅根據(jù)程序和框圖對(duì)求解過(guò)程的描述來(lái)發(fā)現(xiàn)錯(cuò) 誤。由于有些錯(cuò)誤運(yùn)行時(shí)很難查出，但在靜態(tài)查錯(cuò)中卻容易發(fā)現(xiàn)，比如說(shuō)前面 說(shuō)到的書(shū)寫(xiě)錯(cuò)誤。因此，靜態(tài)查錯(cuò)往往是不可忽視的審查步驟。靜態(tài)查錯(cuò)一般 順序?yàn)橄炔槌绦蚓植?，后查程序整體。查局部主要是獨(dú)立地檢查各個(gè)子模塊的 功能是否按照算法要求實(shí)現(xiàn)，查整體主要是檢查各個(gè)局部之間的接口是否吻合, 是否缺少某些功能。在靜態(tài)查錯(cuò)階段，我們可以有針對(duì)性地檢查上面所列舉的 錯(cuò)誤類(lèi)型。在這個(gè)階段查出的錯(cuò)誤越多，節(jié)省的調(diào)試時(shí)間也就越多。2、動(dòng)態(tài)查錯(cuò) 靜態(tài)查錯(cuò)能夠查出錯(cuò)誤，但無(wú)法保證沒(méi)有錯(cuò)誤，因?yàn)檫@里

15、有一個(gè)人為的因 素在里面，只要一不小心，就可能漏掉一個(gè)錯(cuò)誤。因此，我們需要?jiǎng)討B(tài)查錯(cuò)與 之相結(jié)合來(lái)找出遺漏的錯(cuò)誤。與靜態(tài)查錯(cuò)相對(duì)地，動(dòng)態(tài)查錯(cuò)是指通過(guò)跟蹤程序 的執(zhí)行過(guò)程，核對(duì)輸出結(jié)果來(lái)發(fā)現(xiàn)錯(cuò)誤。動(dòng)態(tài)查錯(cuò)的技巧可分為兩大部分：測(cè) 試用例的設(shè)計(jì)和測(cè)試的方法。我們先來(lái)講測(cè)試方法， 動(dòng)態(tài)查錯(cuò)的測(cè)試方法可以按照兩種標(biāo)準(zhǔn)進(jìn)行分類(lèi)。 按照測(cè)試用例的設(shè)計(jì)依據(jù)的不同，可分為黑箱測(cè)試法和白箱測(cè)試法。 只知程序的輸入與輸出功能，而不知程序的具體結(jié)構(gòu)，通過(guò)列舉各種不同 的可能情況來(lái)設(shè)計(jì)測(cè)試用例，通過(guò)執(zhí)行測(cè)試用例來(lái)發(fā)現(xiàn)錯(cuò)誤的測(cè)試方法叫做黑 箱測(cè)試法。已知程序的內(nèi)部結(jié)構(gòu)和流向，根據(jù)程序內(nèi)部邏輯來(lái)設(shè)計(jì)測(cè)試用例， 通過(guò)執(zhí)行測(cè)試

16、用例來(lái)發(fā)現(xiàn)錯(cuò)誤的測(cè)試方法叫做白箱測(cè)試法。在競(jìng)賽中我們常常 使用兩者結(jié)合的方法進(jìn)行測(cè)試。在進(jìn)行底層模塊測(cè)試的時(shí)候可以使用白箱測(cè)試 法，通過(guò)專(zhuān)門(mén)的測(cè)試條件和測(cè)試數(shù)據(jù)來(lái)考慮程序在不同點(diǎn)上的狀態(tài)是否符合預(yù) 期的要求。在總體調(diào)試的時(shí)候則可以使用黑箱測(cè)試法，脫離程序內(nèi)部結(jié)構(gòu)來(lái)考 察對(duì)于不同情況下的測(cè)試數(shù)據(jù)程序是否能夠正確出解。對(duì)于中間模塊，可以用 黑箱，也可以用白箱，或是兩者兼用，具體要看適應(yīng)那種測(cè)試法。一般說(shuō)來(lái)， 結(jié)構(gòu)復(fù)雜的模塊使用黑箱測(cè)試法，結(jié)構(gòu)簡(jiǎn)單的使用白箱測(cè)試法。最后要說(shuō)的是， 由于白箱測(cè)試法測(cè)試用例設(shè)計(jì)比較困難，并且現(xiàn)在信息學(xué)競(jìng)賽都采用黑箱測(cè)試 法進(jìn)行測(cè)試，所以我們?cè)诟?jìng)賽時(shí)間緊張的情況下，可以一

17、律采用黑箱測(cè)試法， 這樣效率比較高。 按照測(cè)試順序的不同，可分為由底向上測(cè)試和從頂向下測(cè)試。 由底向上測(cè)試是先測(cè)最底層的模塊，然后依次向上測(cè)試，最后測(cè)試主模塊。從頂向下測(cè)試剛好與之相反，先測(cè)主模塊，然后按照從頂向下設(shè)計(jì)的順序依次 測(cè)試各個(gè)模塊。為了加快調(diào)試的速度，建議采用從頂向下的測(cè)試順序，只在發(fā) 現(xiàn)某個(gè)模塊有錯(cuò)時(shí)才進(jìn)入下一層調(diào)試，這樣對(duì)迅速定位錯(cuò)誤也有很大幫助。 在運(yùn)用這些測(cè)試方法時(shí)，我們要注意哪些問(wèn)題呢？首先，對(duì)自己所編的程序的 結(jié)構(gòu)、模塊的功能一定要了如指掌。采用從頂向下的測(cè)試方法時(shí)，經(jīng)常是一個(gè) 模塊還沒(méi)有測(cè)試完，就轉(zhuǎn)到了下一個(gè)模塊，因而特別容易忘記和疏漏。如果對(duì) 程序結(jié)構(gòu)心中沒(méi)有概念，

18、就很容易被弄糊涂。又如果對(duì)模塊的功能不是很清楚， 則難以判斷模塊執(zhí)行結(jié)果的對(duì)錯(cuò)，從而無(wú)法準(zhǔn)確確定錯(cuò)誤所在。其次，測(cè)試需 要有條理地進(jìn)行。堅(jiān)持使用同一個(gè)測(cè)試用例直到輸出正確為止；在一個(gè)模塊沒(méi) 有測(cè)試完畢時(shí)，不要進(jìn)行下一個(gè)模塊的測(cè)試，除非這個(gè)模塊是當(dāng)前模塊的子模 塊且在當(dāng)前模塊的測(cè)試中發(fā)現(xiàn)這個(gè)子模塊有錯(cuò)。最后，在每次修改了源代碼之 后一定要把已經(jīng)測(cè)過(guò)的所有測(cè)試用例再測(cè)一遍，以防產(chǎn)生新的錯(cuò)誤。講完了測(cè)試方法，我們?cè)賮?lái)講講測(cè)試用例的設(shè)計(jì)。 黑箱測(cè)試法的測(cè)試用例是根據(jù)輸入數(shù)據(jù)的不同情況來(lái)設(shè)計(jì)的。由于一道題 的輸入數(shù)據(jù)可以千變?nèi)f化，因此黑箱測(cè)試法不可能測(cè)遍所有的情況。如有這樣 一道題，已知程序要求輸入兩個(gè)

19、 Longlnt類(lèi)型的整數(shù)X、Y,輸出的是它們的和。 X共有2八32個(gè)不同值，Y也有2八32個(gè)不同值，這樣不同的輸入數(shù)據(jù)共有 2八32*2八32=2八64種不同情況。假設(shè)執(zhí)行一遍程序要 1毫秒，那么要測(cè)遍所有的 不同情況大約需要五億年，顯然是不可能做到的。白箱測(cè)試法的測(cè)試用例是根據(jù)程序內(nèi)部邏輯來(lái)設(shè)計(jì)的。要完全測(cè)試整個(gè)程序，測(cè)試用例就必須覆蓋程序的所有執(zhí)行路徑，這通常也是不可能的。例如, 有一程序的流程圖如下：其中從 a 到 b 有五條路徑，再外套循環(huán) 20次，根據(jù)乘法原理，執(zhí)行一遍程 序可能經(jīng)過(guò)的不同路徑共有 5八2010八14條。假如程序執(zhí)行一遍從a到b要0.1 秒，那么測(cè)試完所有路徑就需要

20、一百多萬(wàn)年，這顯然也是不可能的。 由上面兩例可以看出，動(dòng)態(tài)查錯(cuò)和靜態(tài)查錯(cuò)一樣，只能發(fā)現(xiàn)某些錯(cuò)誤的存在， 而不能證明錯(cuò)誤的不存在。所以，我們?cè)谠O(shè)計(jì)測(cè)試用例的時(shí)候，需要考慮測(cè)試 用例的經(jīng)濟(jì)性。所謂經(jīng)濟(jì)性是指用盡可能少的測(cè)試用例來(lái)覆蓋盡可能多的情況，對(duì)于黑箱 測(cè)試法來(lái)說(shuō)，就是要包括盡可能多的不同的輸入數(shù)據(jù)類(lèi)型，對(duì)于白箱測(cè)試法來(lái) 說(shuō)，就是要覆蓋盡可能多的執(zhí)行路徑?？紤]到在競(jìng)賽中的測(cè)試以黑箱測(cè)試法為 主，我們僅討論黑箱測(cè)試法的用例設(shè)計(jì)。常用的設(shè)計(jì)方法有等價(jià)分類(lèi)法、邊界 分析法和錯(cuò)誤推測(cè)法等等。等價(jià)分類(lèi)法 所謂等價(jià)分類(lèi)法就是根據(jù)程序功能將輸入的數(shù)據(jù)劃分成若干個(gè)等價(jià)類(lèi)，然 后考慮數(shù)據(jù)選擇，設(shè)計(jì)出測(cè)試用例，以

21、達(dá)到測(cè)試目的。有這樣一道題：輸入三個(gè)整數(shù)表示一個(gè)三角形的三條邊長(zhǎng)。要求輸出能否 構(gòu)成一個(gè)三角形，如能則輸出是等腰，等邊還是既非等邊又非等腰三角形。對(duì)于這道題，我們運(yùn)用等價(jià)分類(lèi)法，根據(jù)三角形是否合理可以將輸入數(shù)據(jù) 分成兩個(gè)等價(jià)類(lèi)：合理三角形和不合理三角形。對(duì)于合理三角形，我們可以繼 續(xù)將該等價(jià)類(lèi)分為等腰三角形和既非等邊又非等腰三角形，而對(duì)于等腰三角形， 還可以分為單純的等腰三角形和等邊三角形。這樣我們通過(guò)不斷地等價(jià)分類(lèi)最 后共可以設(shè)計(jì)出四種測(cè)試用例。另外還可以根據(jù)輸入數(shù)據(jù)的不同排列方式來(lái)分 類(lèi)。但如果你的程序是先排序再進(jìn)行判斷，而且能夠保證排序正確性，就沒(méi)必 要使用這種分類(lèi)方法。邊界分析法程序運(yùn)

22、行出錯(cuò)常常發(fā)生在邊界狀態(tài)，所以在測(cè)試中我們常首先根據(jù)程序的 功能確定邊界情況的數(shù)據(jù)變化，以便設(shè)計(jì)測(cè)試用例。這種對(duì)邊界狀態(tài)進(jìn)行分析， 以設(shè)計(jì)測(cè)試用例來(lái)測(cè)試程序的方法稱(chēng)為邊界分析法。邊界值的選擇要根據(jù)題目實(shí)際情況有針對(duì)性地，有一定創(chuàng)造性地進(jìn)行。一 般來(lái)說(shuō)，可考慮如下幾種情況： 恰好在邊界附近，且欲越界的數(shù)據(jù)； 取最大或最小值，最多或最少值加減 1 的數(shù)據(jù)； 循環(huán)或迭代的初始值與終值數(shù)據(jù)； 有序集合的第一個(gè)或最后一個(gè)數(shù)據(jù)元素； 零點(diǎn)附近的元素； 最大誤差值的數(shù)據(jù)； 數(shù)據(jù)量最大或最小的數(shù)據(jù) 計(jì)算量最大或最小的數(shù)據(jù)仍然使用上面那道三角形的題目作為例子，有如下三個(gè)測(cè)試數(shù)據(jù)：a、兩邊之和等于第三邊；b、三個(gè)

23、數(shù)中包含 0；c、三個(gè)數(shù)均為0；a屬于第種情況，b、c屬于第種情況，這就是邊界值分析法的應(yīng)用。邊界分析法是很重要的一種方法，是一般測(cè)試中必不可少的。它比較精煉， 又容易發(fā)現(xiàn)錯(cuò)誤。問(wèn)題在于有些程序的邊界情況是極其復(fù)雜的，有時(shí)甚至不存 在。比如說(shuō)讓你把 10 個(gè)數(shù)從大到小排序輸出，因?yàn)樗惴ㄖ慌c兩個(gè)數(shù)之間的大小 關(guān)系有關(guān)，與每個(gè)數(shù)的數(shù)值大小無(wú)關(guān)，數(shù)的總數(shù)也是固定的，這時(shí)就不存在邊 界情況，也就無(wú)法使用邊界分析法來(lái)設(shè)計(jì)測(cè)試用例。 錯(cuò)誤推測(cè)法 錯(cuò)誤推測(cè)法實(shí)際上是利用了黑箱白箱結(jié)合的思想，根據(jù)自己設(shè)計(jì)的程序來(lái) 找出容易出現(xiàn)錯(cuò)誤的地方，然后有針對(duì)性地設(shè)計(jì)測(cè)試用例。例如在一個(gè)有許多 If-Then-Else

24、語(yǔ)句嵌套的地方，就很容易出現(xiàn)錯(cuò)誤，而一般的測(cè)試用例很難找出 這種錯(cuò)誤。這時(shí)錯(cuò)誤推測(cè)法就能派上大用場(chǎng)，對(duì)于這一系列的 If-Else 語(yǔ)句，設(shè) 計(jì)出覆蓋不同路徑的測(cè)試用例，從而檢驗(yàn)程序的正確性。至于具體測(cè)試時(shí)選用哪種方法，我們常用的策略是首先用邊界分析法，再 用等價(jià)分類(lèi)法加以補(bǔ)充。最后對(duì)于程序中結(jié)構(gòu)復(fù)雜的部分重點(diǎn)使用錯(cuò)誤推測(cè)法 進(jìn)行測(cè)試。當(dāng)然在時(shí)間允許的情況下，應(yīng)該使用更多的測(cè)試數(shù)據(jù)來(lái)覆蓋更多的 功能。3、跟蹤調(diào)試 跟蹤調(diào)試通常是一件繁瑣的事。它需要選手的耐心和細(xì)心。選擇哪些變量 進(jìn)行跟蹤也是至關(guān)重要的，準(zhǔn)確的變量選擇可以起到事半功倍的效果。一般來(lái) 說(shuō)，首先要跟蹤的是存放輸入數(shù)據(jù)的變量，尤其對(duì)于

25、那些需要對(duì)輸入數(shù)據(jù)進(jìn)行 一定處理的題目來(lái)說(shuō)更是如此，輸入數(shù)據(jù)不正確，即使是正確的程序也會(huì)與答 案不符合；其次是那些頻繁用到的全局變量，這些變量往往貫穿于整個(gè)程序中， 一旦某處出錯(cuò)，會(huì)影響到其他模塊的正確性，由此造成定位錯(cuò)誤。出錯(cuò)的地方 沒(méi)有測(cè)試，正確的地方反而反復(fù)測(cè)試。因此對(duì)于這些全局變量的變化要密切加 以關(guān)注，不可放過(guò)任何錯(cuò)誤；再次就是那些循環(huán)變量了，跟蹤循環(huán)變量可以準(zhǔn) 確地得知程序的執(zhí)行進(jìn)度，從時(shí)間上把握錯(cuò)誤所在；最后其他的變量則要根據(jù) 實(shí)際情況加以選擇，對(duì)使用較多的變量應(yīng)優(yōu)先加以跟蹤。另外 Watch 窗口的大小位置也要合理安排，使得在跟蹤過(guò)程中重要的變量 的變化情況能夠一目了然，從而免

26、去許多不必要的窗口切換，節(jié)省時(shí)間。五、總結(jié) 在信息學(xué)競(jìng)賽中，程序效率高低并不是首要的。不正確的程序效率再高， 也是等于零。效率低的程序只要正確，總是能拿到一點(diǎn)分?jǐn)?shù)。因此調(diào)試水平的 高低，很大程度上也反映了一個(gè)選手整體水平的高低?？偟膩?lái)說(shuō)，程序的調(diào)試 主要靠的還是經(jīng)驗(yàn)。經(jīng)驗(yàn)越豐富，調(diào)試效果也就越好。因此我們平時(shí)訓(xùn)練時(shí)決 不能只注意對(duì)思路算法的訓(xùn)練，還應(yīng)該注意訓(xùn)練自己的調(diào)試水平。六、一個(gè)調(diào)試實(shí)例題目： 在一些美國(guó)主要城市里，為企業(yè)傳送文件和小物品的自行車(chē)快遞長(zhǎng)期以來(lái) 就是流動(dòng)運(yùn)輸服務(wù)的一部分。波士頓的騎車(chē)人是不同尋常的一族。他們以超速、 不遵守單行道和紅綠燈、無(wú)視汽車(chē)、出租、公交和行人的存在而臭名

27、遠(yuǎn)揚(yáng)?？?遞服務(wù)競(jìng)爭(zhēng)激烈。比利快遞服務(wù)公司（BBMs）也不例外。為發(fā)展業(yè)務(wù)，制定合 理的收費(fèi)， BBMS 正根據(jù)快遞員能走的最短路線制定一項(xiàng)快遞收費(fèi)標(biāo)準(zhǔn)。而 你則要替 BBMS 編寫(xiě)一個(gè)程序來(lái)確定這些路線的長(zhǎng)度。以下假設(shè)可以幫助你簡(jiǎn)化工作： 快遞員可以在地面上除建筑物內(nèi)部以外的任何地方騎車(chē)。地形不規(guī)則的建筑物可以認(rèn)為是若干矩形的合并。并規(guī)定，任何相交矩形擁 有共同內(nèi)部，而且是同一建筑物的一部分。盡管兩個(gè)不同的建筑物可能非常接近，但永遠(yuǎn)不會(huì)重疊。 （快遞員可以從任意 兩個(gè)建筑物之間穿過(guò)。他們能夠繞過(guò)最急的拐彎，可以貼著建筑物的邊緣疾駛。） 起點(diǎn)和終點(diǎn)不會(huì)落在建筑物內(nèi)部。總有一條連接起訖點(diǎn)的線路。

28、下圖是一張典型的鳥(niǎo)瞰圖。StopO4812輸入文件包含如下若干行：第一行：n場(chǎng)景中描述建筑物的矩形個(gè)數(shù)。o<=n<=20第二行：x1、y1、x2、y2路線起訖點(diǎn)的x和y坐標(biāo)。余下 n 行： x1、y1、x2、y2、x3、y3矩形三個(gè)頂點(diǎn)的坐標(biāo)所有x、y坐標(biāo)是屬于0到1000 (包含0和1000)的實(shí)數(shù)，每行中相鄰的 坐標(biāo)由一個(gè)或多個(gè)空格分開(kāi)。正如下面輸出范例給出的那樣。輸出應(yīng)給出從起 點(diǎn)到終點(diǎn)的最短線路的長(zhǎng)度，精確到小數(shù)點(diǎn)后第二位。輸入范例56.591031533665.2528283.5610612912761161181071171111輸出范例7.28 算法分析：由輸入文件的

29、格式可以看出，每一個(gè)矩形輸入三個(gè)頂點(diǎn)P1，P2和P3。這三個(gè)頂點(diǎn)的坐標(biāo)分別為(P1.x P1.y)、( P2.x, P2.y)、( P3.x，P3.y)。由于矩形 的四條邊不一定平行x軸和y軸，因此我們預(yù)先對(duì)P1、P2、P3進(jìn)行排序，使得 P2 在 P1 的右方或者正上方，即(P2.x>P1.x) or (P2.x= P1.x) and (P2.y>=P1.y); P3 在 P1 的右方或者正上方，即(P3,x>P1.x)or( P3.x= P1.x)and( P3.y>=P1.y); P3 在 P2 的右方或者正上方，即(P3. x> P2.x) or ( P3

30、.x=P2.x)and ( P3.y> =P2.y)。然后求出矩形的第四個(gè)頂點(diǎn) P4:P4.x= P1.x+P3.x-P2.xP4.y = P1.y+P3.y-P2.y例如輸入矩形的三個(gè)頂點(diǎn)( 3， 3)、(1， 5)、(6， 6)。按上述方法排序后 P1=( 1， 5)， P2=(3， 3)， P3=(6， 6)P4.x= pl. x+ P3.x-P2.x)= 1 + 6 一 3= 4 P4.y = P1.x+P3.y 一 P2.y= 5 十 6 一 3= 8 即 P4=( 4， 8)由排序的定義可以看出， 對(duì)于每一個(gè)矩形的 4個(gè)頂點(diǎn)來(lái)說(shuō)， P1 和 P2 互為對(duì) 角，P3和P4互為對(duì)

31、角。由于快遞員是在地面上除建筑物內(nèi)部以外(包括建筑物邊緣)的空間尋找 一條最短路線，因此，這條路線上的頂點(diǎn)除起訖兩個(gè)點(diǎn)外，其余都為矩形的頂 點(diǎn)。最短路線上每條線段的兩個(gè)端點(diǎn)既不能被任何建筑物所擋。也不能為同一 矩形的對(duì)角點(diǎn)(不能穿過(guò)矩形對(duì)應(yīng)的建筑物) 。我們將最短路線的起點(diǎn)、終點(diǎn)以及每個(gè)矩形頂點(diǎn)放入一個(gè)頂點(diǎn)序列表P中,其中P1、P4*n+2存貯起訖點(diǎn)，P2P4*n + 1存貯n個(gè)矩形的頂點(diǎn)。顯然，最短路線上的頂點(diǎn)取自于 P 表。在建立 P 表中的同時(shí)建立一張線段表 L， 將每個(gè)矩形的四條矩形邊和兩條對(duì)角線存入該表。設(shè)置 L 表的目的是為了判斷 快遞員的行車(chē)路線是否符合規(guī)則。如果行車(chē)路線與表中任

32、一條矩形邊相交，則 說(shuō)明快遞員進(jìn)入了建筑物內(nèi)部，這種情況必須排除。問(wèn)題是：為什么 L 表還要 存貯每個(gè)矩形的對(duì)角線呢？這是為了剔除一種如下圖的邊界錯(cuò)誤。起1/點(diǎn)、F如果起點(diǎn)和終點(diǎn)貼在同一個(gè)矩形邊上(這種情況是允許的，因?yàn)榭爝f員可 以貼著建筑物的邊緣疾駛)，則快遞員將毫無(wú)顧忌地穿越“禁區(qū)”，因?yàn)閮牲c(diǎn)間 未相交任何矩形邊。增設(shè)行車(chē)路線不能與矩形的對(duì)角線相交的條件，便可避免 這個(gè)不易察覺(jué)的漏洞。求最短路徑則可采用標(biāo)號(hào)法。 程序：Program Corner;ConstFinName='corner.in'輸入文件名FoutName='comer.out'輸出文件名Ma

33、xBuilding=20;最大建筑物MaxPoint=82;最多頂點(diǎn)數(shù)MaxLine=120;最多線段數(shù)Zero=1e-8;相對(duì)極小量，用于實(shí)數(shù)比較TypeLocation=Record坐標(biāo)類(lèi)型x,y:Real;End;Line=Array1.2Of Location;線段類(lèi)型VarBld,建筑物數(shù)Pn以頂點(diǎn)數(shù)Lne:Integer;線段數(shù)P:Array1.MaxPointOf Location;頂點(diǎn)序列L:Array1.MaxLineOf Line;線段序列Dis:Array1.MaxPointOf Real;最短距離表Function GetMin(Var a,b:Real):Real;返

34、回兩數(shù)較小值 BeginIf a>b Then GetMin:=b Else GetMin:=a; End;Function GetMax(Var a,b:Real):Real; 返回兩數(shù)較小值 BeginIf a>b Then GetMax:=a Else GetMax:=b; End;Function GetMulti(p0,p1,p2:Location):Real;計(jì)算叉積 BeginGetMulti:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);End;Function lntersect(Var L1,L2:Line):

35、Boolean;判斷兩條線段是否相交 VarM1,M2,M3,M4:Real;Beginlntersect:=False;lf (GetMin(L11.x,L12.x)<=GetMax(L21.x,L22.x)And(GetMax(L11.x,L12.x)>=GetMin(L21.x,L22.x)And(GetMin(L11.y,L12.y)<=GetMax(L21.y,L22.y)And(GetMax(L11.y,L12.y)>=GetMin(L21.y,L22.y) Then 通過(guò)快速排斥試驗(yàn) BeginM1:=GetMulti(L11,L21,L12);M2:=G

36、etMulti(L11,L12,L22);M3:=GetMulti(L21,L11,L22);M2:=GetMulti(L21,L22,L12); lf (Abs(M1)>Zero)And(Abs(M2)>Zero)And(Abs(M3)>Zero)And(Abs(M4)>Zero)And(M1*M2>0)And(M3*M4>0) Then lntersect:=True;End;End;Procedure GetNextPoint(Var P1,P2,P3,P4:Location);將頂點(diǎn)排序并計(jì)算第四個(gè)頂點(diǎn)坐標(biāo) VarT:Location;Beginlf

37、 (P2.x<P1.x)Or(P2.x=P1.x)And(P2.y<P1.y) ThenBegin T:=P1;P1:=P2;P2:=T;End;lf (P3.x<P1.x)Or(P3.x=P1.x)And(P3.y<P1.y) ThenBegin T:=P1;P1:=P3;P3:=T;End;lf (P3.x<P2.x)Or(P3.x=P2.x)And(P3.y<P2.y) ThenBegin T:=P3;P3:=P2;P2:=T;End;P4.x:=P1.x+P3.x-P2.x;P4.y:=P1.y+P3.y-P2.y;End;Procedure lni

38、t;讀入數(shù)據(jù)，并初始化Vari,j:Byte;BeginReadLn(Bld);Lne:=0;Pnt:=1;ReadLn(P1.x,P1.y,PBld*4+2.x,PBld*4+2.y);For i:=1 to Bld DoBeginFor j:=1 to 3 DoRead(PPnt+j.x,PPnt+j.y);ReadLn;GetNextPoint(PPnt+1,PPnt+2,PPnt+3,PPnt+4);For j:=1 to 3 DoBeginLLne+j,1:=PPnt+j;LLne+j,2:=PPnt+j+1;End;LLne+4,1:=PPnt+4;LLne+4,2:=PPnt+1

39、;LLne+5,1:=PPnt+1;LLne+5,2:=PPnt+3;LLne+6,1:=PPnt+2;LLne+6,2:=PPnt+4;Inc(Pnt,4);Inc(Pnt,6);End;Inc(Pnt);End;Function GetDis(a,b:Byte):Real;計(jì)算兩點(diǎn)間距離BeginGetDis:=Sqrt(Pa.x-Pb.x)*(Pa.x-Pb.x)+(Pa.y-Pb.y)*(Pa.y-Pb.y);End;Function Visible(Var P1,P2:Location):Boolean;判斷在 P1 點(diǎn)是否能看到 P2 點(diǎn)，即判斷兩點(diǎn)之間是否有建筑物阻擋 VarTL

40、:Line;i:Byte;BeginTL1:=P1;TL2:=P2;For i:=1 to Lne DoIf Intersect(Li,TL) ThenBegin Visible:=False;Exit;End;Visible:=True;End;Procedure Main;主程序，用標(biāo)號(hào)法求最短路徑Vari,j,k:Byte;Min:Real;S:Set Of Byte;BeginDis1:=0;For i:=2 to Pnt DoIf Visible(P1,Pi) Then Disi:=GetDis(1,i)Else Disi:=1e10;S:=1;For i:=2 to Pnt DoB

41、eginMin:=1e10;k:=0;For j:=2 to Pnt DoIf (Not(j In S)And(Disj<Min) Then Begin k:=j;Min:=Disj;End;If k=Pnt Then Break;S:=S+k;For j:=2 to Pnt DoIf (Not(j In S)And(Visible(Pk,Pj)And(Disk+GetDis(j,k)<Disj) ThenDisj:=Disk+GetDis(j,k);End;WriteLn(DisPnt:0:2); 輸出答案 End;BeginAssign(Input,FinName);Reset

42、(Input);Assign(Output,FoutName);Rewrite(Output);Init;Main;Close(Input);Close(Output);End.這個(gè)程序編譯已經(jīng)通過(guò)， 現(xiàn)在我們進(jìn)行靜態(tài)查錯(cuò)。 首先確定了函數(shù) GetMin ， GetMax ，GetMulti 是正確的。因?yàn)檫@三個(gè)函數(shù)很短，也很簡(jiǎn)單，所以只要通過(guò) 靜態(tài)查錯(cuò)應(yīng)該就可以了。 接著往下看， 發(fā)現(xiàn)在過(guò)程 Init 中有一行是 Inc( Pnt，4)； Inc( Pnt， 6)；明顯不對(duì)。程序的本意顯然是要增加Pnt 和 Lne 的值，所以應(yīng)該把Inc ( Pnt, 6)換成Inc (Lne, 6)。再往

43、下，又發(fā)現(xiàn)在函數(shù) Intersect中計(jì) 算叉積時(shí)連續(xù)給 M2 賦了兩次值， 這樣前面一次賦值就沒(méi)有意義了， 這明顯是一 個(gè)書(shū)寫(xiě)錯(cuò)誤,后面的 M2 應(yīng)改為 M4 。再往下就沒(méi)有發(fā)現(xiàn)其他錯(cuò)誤了。接著進(jìn)入動(dòng)態(tài)查錯(cuò),我們用的第一個(gè)例子當(dāng)然是樣例,輸入樣例后發(fā)現(xiàn)輸 出 7.28,與答案一致。 因此沒(méi)有必要再進(jìn)行模塊測(cè)試。 現(xiàn)在應(yīng)該設(shè)計(jì)自己的測(cè)試 用例了。首先使用邊界值分析法, 這道題在建筑物個(gè)數(shù)上有兩個(gè)邊界： 0和 20。上邊 界測(cè)使用例設(shè)計(jì)比較繁瑣,因此我們先嘗試下邊界 0 以及下邊界附近的 1。坐標(biāo) 也有兩個(gè)邊界： 0 和 1000,我們可以結(jié)合建筑物個(gè)數(shù)的邊界,得到如下兩個(gè)測(cè)試用例： coner

44、1.in 00 0 1000 1000corner2.in10 0 1000 10000 0 0 1000 1000 1000對(duì)于cornerl程序輸出是1414.21,正確。對(duì)于corner2程序輸出是2000.00, 也是正確的。接下去我們采用等價(jià)分類(lèi)法設(shè)計(jì)測(cè)試用例。 首先根據(jù)數(shù)據(jù)的排列方式進(jìn)行分類(lèi)，我們只使用一個(gè)矩形，然后把它的三 個(gè)頂點(diǎn)的六種排列方式都進(jìn)行嘗試，這樣共有 6 個(gè)測(cè)試用例，下面僅列出一個(gè)： corner3.in10 0 1 10 0 0 1 1 1答案應(yīng)該全為 2.00，但測(cè)到頂點(diǎn)排列方式為 0 1 1 1 0 0 時(shí)，程序輸出了 1.41， 因?yàn)槠渌麠l件都不變，因此最有

45、可能便是過(guò)程 GetNextPoint 出錯(cuò)。使用 Go to cursor執(zhí)行到過(guò)程GetNextPoint開(kāi)頭處，添加變量數(shù)組 P到Watch窗口，再使 用Trace into 一步步執(zhí)行下去。我們看到程序?qū)?P1、P2沒(méi)有進(jìn)行交換，對(duì)P2、 P3 進(jìn)行了交換，但根據(jù)我們的算法，顯然需要把( 0， 0)放到第一個(gè)位置。由 此恍然大悟，應(yīng)該在比較完 P1、P2后，再比較P1、P3,最后才比較P2、P3。 所以應(yīng)該在第一句 If-Then-Else 語(yǔ)句后添上：If (P3.x<P1.x)Or(P3.x=P1.x)And(P3.y<P1.y) ThenBegin T:=P1;P1:

46、=P3;P3:=T;End; 再次檢驗(yàn)，答案無(wú)誤，前面的測(cè)試用例也全部通過(guò)。我們繼續(xù)下面的測(cè)試。這次我們根據(jù)矩形之間的關(guān)系進(jìn)行分類(lèi)，兩個(gè)矩形可以包含，相交，相切， 相離。這里的相切是指兩個(gè)矩形有一部分邊重合但不包含，因?yàn)轭}目規(guī)定了兩 個(gè)不同建筑物可能十分接近，但永遠(yuǎn)不會(huì)重疊，因此排除相切這種情況，但可 以使相離的兩個(gè)矩形十分接近。這次我們使用兩個(gè)矩形，有下面三個(gè)測(cè)試用例： corner9.in包含21 0 1 30 0 0 3 3 31 1 1 2 2 2corner10.in相 交21 0 1 10 0 0 1 2 11 0 1 1 3 1corner11.in相離，但十分接近21 0 1

47、10 0 0 1 1 11.0001 0 1.0001 1 3 110、11兩個(gè)測(cè)試用例沒(méi)有問(wèn)題，第 9個(gè)輸出了 3,有問(wèn)題，答案應(yīng)該是 5 才對(duì)。我們進(jìn)入模塊調(diào)試，數(shù)據(jù)讀入及初始化沒(méi)有問(wèn)題，接下去進(jìn)入Main繼續(xù)跟蹤，首先我們對(duì)第一個(gè)循環(huán)用 Go to cursor一步執(zhí)行完畢，檢查數(shù)組 Dis，發(fā) 現(xiàn)除起點(diǎn)外共有4個(gè)點(diǎn)的值小于1e10。因?yàn)檫@是一個(gè)矩形包含的用例，按理應(yīng) 該只有兩個(gè)點(diǎn)的值會(huì)小于 1e10。檢查這四個(gè)點(diǎn)，發(fā)現(xiàn)被包含的那個(gè)矩形有兩個(gè) 點(diǎn)也被計(jì)算在內(nèi)。仔細(xì)一想就明白了，我們雖然加上了兩條對(duì)角線，但是對(duì)于 處于矩形內(nèi)部的點(diǎn)還是無(wú)法排除，我們的程序選擇的最短路徑應(yīng)該就是沿直線 走，因

48、為中間多了兩個(gè)矩形頂點(diǎn)把它分為三條線段，這兩個(gè)頂點(diǎn)又恰好在對(duì)角 線上，所以這三條線段都不與對(duì)角線相交。程序就選擇了這條“最短路徑”走。StopStart解決方案：因?yàn)槠瘘c(diǎn)和終點(diǎn)都不會(huì)在矩形內(nèi)部，所以我們可以在讀完所有頂點(diǎn) 后，排除那些處于矩形內(nèi)部的點(diǎn)。具體修改可見(jiàn)附錄。我們還可以按照起點(diǎn)和終點(diǎn)的位置關(guān)系進(jìn)行分類(lèi)，因?yàn)檫@牽涉到矩形的分 布，情況比較復(fù)雜，所以我們只考慮起點(diǎn)和終點(diǎn)是否重合，因此還需添加一個(gè) 測(cè)試用例：cornerll.in00 0 0 0輸出為0.00,正確。最后我們使用錯(cuò)誤推測(cè)法，這道題中最復(fù)雜的無(wú)疑是Intersect和InBuilding 這兩個(gè)函數(shù)。因此可以針對(duì)這兩個(gè)函數(shù)，

49、把它們分別作為一道小題目來(lái)測(cè)?？?以參照上面講的步驟設(shè)計(jì)測(cè)試用例，先用邊界值分析法，后用等價(jià)分類(lèi)法，具 體的測(cè)試用例就不再給出。這樣測(cè)試后的結(jié)果也是沒(méi)有錯(cuò)誤。整道題的測(cè)試到 此就圓滿(mǎn)完成了?！靖戒洝恳弧⑿薷暮蟮某绦蛘f(shuō)明：紅色表示修改后的部分Program Corner;ConstFinName='corner.in'輸入文件名 FoutName='corner.out'®出文件名 MaxBuilding=20;最大建筑物MaxPoint=82; 最多頂點(diǎn)數(shù) MaxLine=120; 最多線段數(shù) Zero=1e-8;相對(duì)極小量，用于實(shí)數(shù)比較TypeLoc

50、ation=Record坐標(biāo)類(lèi)型x,y:Real;End;Line=Array1.20f Location;線段類(lèi)型VarBld,建筑物數(shù)Pn以頂點(diǎn)數(shù)Lne:lnteger;線段數(shù)P:Array1.MaxPointOf Location; 頂點(diǎn)序列 L:Array1.MaxLineOf Line; 線段序列 Dis:Array1.MaxPointOf Real; 最短距離表 Function GetMin(Var a,b:Real):Real;返回兩數(shù)較小值Beginlf a>b Then GetMin:=b Else GetMin:=a;End;Function GetMax(Var

51、a,b:Real):Real; 返回兩數(shù)較小值 Beginlf a>b Then GetMax:=a Else GetMax:=b;End;Function GetMulti(p0,p1,p2:Location):Real;計(jì)算叉積 BeginGetMulti:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);End;Function lntersect(Var L1,L2:Line):Boolean;判斷兩條線段是否相交 VarM1,M2,M3,M4:Real;Beginlntersect:=False;lf (GetMin(L11.x,

52、L12.x)<=GetMax(L21.x,L22.x)And(GetMax(L11.x,L12.x)>=GetMin(L21.x,L22.x)And(GetMin(L11.y,L12.y)<=GetMax(L21.y,L22.y)And(GetMax(L11.y,L12.y)>=GetMin(L21.y,L22.y) Then 通過(guò)快速排斥試驗(yàn) Begin M1:=GetMulti(L11,L21,L12);M2:=GetMulti(L11,L12,L22); M3:=GetMulti(L21,L11,L22); M4:=GetMulti(L21,L22,L12); l

53、f (Abs(M1)>Zero)And(Abs(M2)>Zero) And(Abs(M3)>Zero)And(Abs(M4)>Zero) And(M1*M2>0)And(M3*M4>0) Then lntersect:=True;End;End;Procedure GetNextPoint(Var P1,P2,P3,P4:Location); 將頂點(diǎn)排序并計(jì)算第四個(gè)頂點(diǎn)坐標(biāo) VarT:Location;BeginIf (P2.x<P1.x)Or(P2.x=P1.x)And(P2.y<P1.y) ThenBegin T:=P1;P1:=P2;P2:

54、=T;End;If (P3.x<P1.x)Or(P3.x=P1.x)And(P3.y<P1.y) ThenBegin T:=P1;P1:=P3;P3:=T;End;If (P3.x<P2.x)Or(P3.x=P2.x)And(P3.y<P2.y) Then Begin T:=P3;P3:=P2;P2:=T;End;P4.x:=P1.x+P3.x-P2.x;P4.y:=P1.y+P3.y-P2.y;End;Function InBuildingWar p0:Location):Boolean;判斷點(diǎn)是否在矩形內(nèi) Vari,j,k:Byte;M1,M2:Real;Temp:Boolean;Begink:=1;For i:=1 to Bld DoBeginM1:=GetMulti(p0,Pk+4,Pk+1);If Abs(M1)<Zero Then Continue;Temp:=True;For j:=1 to 3 DoBeginM2:=GetMulti(p0,Pk+j,Pk+j+1);If (Abs(M2)<Zero)Or(M1*M2<0) ThenBegin Temp:=F