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

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

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

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

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

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

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

7、句。這一點使得我們在使用嵌套的 If-Else 語句時容易出錯。如下面這個例子：If 條件 aThen If 條件 b Then 代碼段 bElse 代碼段 a我們的原意是讓代碼段a在條件a不成立時執(zhí)行，但由于Else語句總是匹 配最近的If-Then語句，因此這個Else是與If條件b Then這個語句相匹配的， 也就是說代碼段 a 要滿足條件 a 成立且條件 b 不成立時才會執(zhí)行，與我們原意相去甚遠。解決方法是在需要的地方加一個空的Else,就如上面的例子，要在If 條件 b Then 語句后面加一個空的 Else。 實數(shù)比較出錯 在比較兩個實數(shù)是否相等時，如果直接用等號，往往會造成錯誤。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、格式可以看出，每一個矩形輸入三個頂點P1，P2和P3。這三個頂點的坐標分別為(P1.x P1.y)、( P2.x, P2.y)、( P3.x，P3.y)。由于矩形 的四條邊不一定平行x軸和y軸，因此我們預(yù)先對P1、P2、P3進行排序，使得 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)。然后求出矩形的第四個頂點 P4:P4.x= P1.x+P3.x-P2.xP4.y = P1.y+P3.y-P2.y例如輸入矩形的三個頂點( 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)由排序的定義可以看出， 對于每一個矩形的 4個頂點來說， P1 和 P2 互為對 角，P3和P4互為對

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

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

33、xBuilding=20;最大建筑物MaxPoint=82;最多頂點數(shù)MaxLine=120;最多線段數(shù)Zero=1e-8;相對極小量，用于實數(shù)比較TypeLocation=Record坐標類型x,y:Real;End;Line=Array1.2Of Location;線段類型VarBld,建筑物數(shù)Pn以頂點數(shù)Lne:Integer;線段數(shù)P:Array1.MaxPointOf Location;頂點序列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;計算叉積 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 通過快速排斥試驗 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);將頂點排序并計算第四個頂點坐標 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;計算兩點間距離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 點是否能看到 P2 點，即判斷兩點之間是否有建筑物阻擋 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;主程序，用標號法求最短路徑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.這個程序編譯已經(jīng)通過， 現(xiàn)在我們進行靜態(tài)查錯。 首先確定了函數(shù) GetMin ， GetMax ，GetMulti 是正確的。因為這三個函數(shù)很短，也很簡單，所以只要通過 靜態(tài)查錯應(yīng)該就可以了。 接著往下看， 發(fā)現(xiàn)在過程 Init 中有一行是 Inc( Pnt，4)； Inc( Pnt， 6)；明顯不對。程序的本意顯然是要增加Pnt 和 Lne 的值，所以應(yīng)該把Inc ( Pnt, 6)換成Inc (Lne, 6)。再往

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

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

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

46、=P3;P3:=T;End; 再次檢驗，答案無誤，前面的測試用例也全部通過。我們繼續(xù)下面的測試。這次我們根據(jù)矩形之間的關(guān)系進行分類，兩個矩形可以包含，相交，相切， 相離。這里的相切是指兩個矩形有一部分邊重合但不包含，因為題目規(guī)定了兩 個不同建筑物可能十分接近，但永遠不會重疊，因此排除相切這種情況，但可 以使相離的兩個矩形十分接近。這次我們使用兩個矩形，有下面三個測試用例： 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兩個測試用例沒有問題，第 9個輸出了 3,有問題，答案應(yīng)該是 5 才對。我們進入模塊調(diào)試，數(shù)據(jù)讀入及初始化沒有問題，接下去進入Main繼續(xù)跟蹤，首先我們對第一個循環(huán)用 Go to cursor一步執(zhí)行完畢，檢查數(shù)組 Dis，發(fā) 現(xiàn)除起點外共有4個點的值小于1e10。因為這是一個矩形包含的用例，按理應(yīng) 該只有兩個點的值會小于 1e10。檢查這四個點，發(fā)現(xiàn)被包含的那個矩形有兩個 點也被計算在內(nèi)。仔細一想就明白了，我們雖然加上了兩條對角線，但是對于 處于矩形內(nèi)部的點還是無法排除，我們的程序選擇的最短路徑應(yīng)該就是沿直線 走，因

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

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

50、ation=Record坐標類型x,y:Real;End;Line=Array1.20f Location;線段類型VarBld,建筑物數(shù)Pn以頂點數(shù)Lne:lnteger;線段數(shù)P:Array1.MaxPointOf Location; 頂點序列 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;計算叉積 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 通過快速排斥試驗 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); 將頂點排序并計算第四個頂點坐標 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;判斷點是否在矩形內(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