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

《論程序的調(diào)試技巧》由會員分享，可在線閱讀，更多相關《論程序的調(diào)試技巧（32頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、論程序的調(diào)試技巧 【核心字】調(diào)試技巧、測試措施、測試用例設計 【摘要】本文結合伙者自身經(jīng)驗，對競賽中程序的調(diào)試技巧做了具體的論述和總結。在簡介了編程中常用的錯誤類型和集成環(huán)境的調(diào)試工具之后，給出了一般調(diào)試流程，并著重講述了其中的動態(tài)查錯技巧，做了一定的歸納。最后通過一種調(diào)試實例來體現(xiàn)本文所論述的調(diào)試技巧的具體應用。 【正文】 一、 程序調(diào)試的必要性 程序設計過程中，錯誤是在所難免的。雖然有些程序員覺得一種程序可以做到完美無瑕，但實際狀況卻并非如此，否則就不會有人對Windows怨氣沖天了。盡管信息學競賽中所編的程序歷來不會像Windows那樣龐大，最多也是僅僅幾百K而已，但由于時間有

2、限，選手們的程序難免有疏漏之處。因此，調(diào)試就成了極其重要的一環(huán)。如何在急切的時間內(nèi)迅速精確地發(fā)現(xiàn)并改正錯誤，正是本文所要討論的問題。 二、 常用錯誤類型歸納 《孫子兵法》云：“知己知彼，百戰(zhàn)不殆?！睂τ诔绦蛘{(diào)試者來說，程序中的錯誤就好比是敵人，如能精確把握敵人的狀況，無疑是極為有利的。下面我們就來對常用的某些錯誤類型進行歸納并給出解決措施。 1、 思路錯誤 這要看是基本算法錯誤還是功能缺陷。前者需要重寫大部分代碼，與否重寫則根據(jù)時間與否富余而定，后者只需增長一部分代碼，再修改某些地方，這時應全面考慮，以防漏掉應當修改的地方。 2、 語法錯誤 這個沒什么可說的，作為一名信息學競賽的選

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

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

5、：=A*A Div 100； 其中A，B都是Integer類型。按照我們的想法，1000*1000 Div 100=10000。然而當我們察看B的值的時候，卻發(fā)現(xiàn)B等于169。因素是Pascal在進行編譯時，總是先計算出A*A，把它放到一種中間變量中，然后再計算出最后成果放入B中。而A*A超過了Integer的范疇，這就是導致錯誤的主線因素。要使Pascal能報告此類錯誤，只要打開編譯開關Q即可。對此類錯誤解決措施是使用強制類型轉換，寫成B：=LongInt（A）*A Div 100。編譯程序會自動把中間變量規(guī)定為LongInt類型，就不會越界了。 ③ 局部變量與全局變量同名導致概念混亂

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

7、If-Else語句時容易出錯。如下面這個例子： If 條件a Then If 條件b Then 代碼段b Else 代碼段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)士來說，對自己手中的武器性能特點應當了如指掌。對于程序調(diào)試者來說，調(diào)試工具就相稱于武器，純熟掌握調(diào)試工具，充足發(fā)揮它的性能，對于迅速找出錯誤，加快我們的調(diào)試速度有著極大的協(xié)助。下面就對集成環(huán)境提供的調(diào)試工具做某些簡介。 調(diào)試時重要使用的兩個菜單是Run和Debug。Run菜單提供了多種程序執(zhí)行方式，而Debug菜單提供了對變量的觀測，修改以及斷點等功能。 程序的執(zhí)行方式有四種： 1、 Run，運營整個程序（Ctrl+F9），該方式常用在總體測

9、試上。一般每一種測試用例都應先用該方式執(zhí)行程序，如果輸出答案對的就可以直接轉到下一種測試用例，免除了不必要的時間。雖然發(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í)行過程。它的長處是容易直接定位錯誤，缺陷是調(diào)試速度較慢，特別是當錯誤位于

10、程序后部時。因此一般是采用先用模塊調(diào)試法盡量縮小錯誤范疇，然后使用第4種執(zhí)行方式和斷點來迅速跳過沒有浮現(xiàn)錯誤的部分，最后才是用該方式來逐漸跟蹤找出錯誤。 4、 Go to cursor，執(zhí)行到光標處（F4），之因此把這種方式放在最后簡介，是由于這種方式的靈活度較大，不僅可以一次執(zhí)行一行，也可以一次執(zhí)行多行；可以直接跳過過程（函數(shù)），也可以進入過程（函數(shù)）內(nèi)部。它有斷點的定位能力強的長處，又比斷點更加靈活。對的合適地使用這種方式可以大大加快我們調(diào)試的速度，這需要靠豐富的調(diào)試經(jīng)驗?？梢詤⒄毡趁娴恼{(diào)試實例。 Debug菜單中最常用選項是Watch和Add Watch，這兩個用于跟蹤觀測變量和體現(xiàn)

11、式在程序執(zhí)行過程中值的變化，這樣就可以隨時檢查它們與否按照算法規(guī)定輸出，與否符合對的答案。大多數(shù)錯誤在調(diào)試時都可以只使用它們以及上面的四種執(zhí)行方式被檢查出來。 有的時候，雖然懂得該模塊有錯，但一時無法找到錯誤所在，并且上面所講的后三種執(zhí)行方式都難以迅速定位。例如對于一種程序，我們需要它執(zhí)行到某個語句并滿足某個條件時停下來，Go to cursor只能保證執(zhí)行到這個語句時停下來，卻不能保證滿足條件，這時我們便需要使用斷點。斷點雖然沒有Go to cursor靈活，但有一種Go to cursor無法取代的優(yōu)勢便是它可以設立中斷條件。使用Add Breakpoint選項（Ctrl+F8）可以在目

12、前光標處設立一種斷點，Breakpoints選項可以編輯斷點條件。要注意的是，斷點的設立會大大減少程序執(zhí)行效率，因此調(diào)試完畢后來一定要記得清除所有斷點。 Evaluate/modify選項（Ctrl+F4）用于臨時觀測修改體現(xiàn)式的值，如果在調(diào)試過程中，需要臨時觀測或修改某個體現(xiàn)式的值，則可以打開Evaluate and modify窗口進行操作。這個措施特別合用于對過程（函數(shù)）的調(diào)試，我們可以先用Go to cursor執(zhí)行到某個過程（函數(shù)）的開頭，然后使用Evaluate/modify選項變化參數(shù)的值用于檢查不同狀況下這個過程（函數(shù)）的執(zhí)行成果。但是要注意，一種過程（函數(shù)）一般不是孤立的，

13、它常常需要使用某些全局變量，因此僅變化參數(shù)而不變化其她全局變量的值有也許是非法的。因此需要特別的小心，避免浮現(xiàn)這樣的狀況。 Call stack選項（Ctrl+F3）用于顯示目前堆棧狀態(tài)，這特別合用于對遞歸算法的調(diào)試。我們可以運用它察看每層參數(shù)的傳遞狀況。但是一般來說參數(shù)的傳遞不易出錯，因此該選項的用處并不是很大。 四、 調(diào)試的一般過程 對于一道題我們一般按照如下流程圖進行調(diào)試： 調(diào)試開始 通過靜態(tài)查錯？

14、 Y 總體測試通過？ Y N N 模塊測試通過？ Y 所有模塊已經(jīng)測試完畢？ Y N 跟蹤調(diào)試 修改錯誤，重新編碼

15、 測試用例完否？ Y N 調(diào)試結束 這只是針對一般狀況而言，在具體調(diào)試時，可以變化某些環(huán)節(jié)，例如說在發(fā)現(xiàn)某個模塊有錯誤改正后來，可以不返回到靜態(tài)查錯階段，而是繼續(xù)該模塊的查錯。這要視具體狀況而定。 下面我們對各個環(huán)節(jié)作具體的論述。 1、 靜態(tài)查錯 靜態(tài)查錯是指不執(zhí)行程序，僅根據(jù)程序和框圖對求解過程的描述來發(fā)現(xiàn)錯誤。由于有些錯誤運營時很難查出，但在靜態(tài)查錯中卻容易發(fā)現(xiàn)，例如說前面說到的書寫錯誤。因此，靜態(tài)查錯往往是不可忽視的審查環(huán)

16、節(jié)。靜態(tài)查錯一般順序為先查程序局部，后查程序整體。查局部重要是獨立地檢查各個子模塊的功能與否按照算法規(guī)定實現(xiàn)，查整體重要是檢查各個局部之間的接口與否吻合，與否缺少某些功能。在靜態(tài)查錯階段，我們可以有針對性地檢查上面所列舉的錯誤類型。在這個階段查出的錯誤越多，節(jié)省的調(diào)試時間也就越多。 2、 動態(tài)查錯 靜態(tài)查錯可以查出錯誤，但無法保證沒有錯誤，由于這里有一種人為的因素在里面，只要一不小心，就也許漏掉一種錯誤。因此，我們需要動態(tài)查錯與之相結合來找出漏掉的錯誤。與靜態(tài)查錯相對地，動態(tài)查錯是指通過跟蹤程序的執(zhí)行過程，核對輸出成果來發(fā)現(xiàn)錯誤。動態(tài)查錯的技巧可分為兩大部分：測試用例的設計和測試的措施。我

17、們先來講測試措施， 動態(tài)查錯的測試措施可以按照兩種原則進行分類。 ① 按照測試用例的設計根據(jù)的不同，可分為黑箱測試法和白箱測試法。 只知程序的輸入與輸出功能，而不知程序的具體構造，通過列舉多種不同的也許狀況來設計測試用例，通過執(zhí)行測試用例來發(fā)現(xiàn)錯誤的測試措施叫做黑箱測試法。已知程序的內(nèi)部構造和流向，根據(jù)程序內(nèi)部邏輯來設計測試用例，通過執(zhí)行測試用例來發(fā)現(xiàn)錯誤的測試措施叫做白箱測試法。在競賽中我們常常使用兩者結合的措施進行測試。在進行底層模塊測試的時候可以使用白箱測試法，通過專門的測試條件和測試數(shù)據(jù)來考慮程序在不同點上的狀態(tài)與否符合預期的規(guī)定。在總體調(diào)試的時候則可以使用黑箱測試法，脫離程序內(nèi)

18、部構造來考察對于不同狀況下的測試數(shù)據(jù)程序與否可以對的出解。對于中間模塊，可以用黑箱，也可以用白箱，或是兩者兼用，具體要看適應那種測試法。一般說來，構造復雜的模塊使用黑箱測試法，構造簡樸的使用白箱測試法。最后要說的是，由于白箱測試法測試用例設計比較困難，并且目前信息學競賽都采用黑箱測試法進行測試，因此我們在競賽時間緊張的狀況下，可以一律采用黑箱測試法，這樣效率比較高。 ② 按照測試順序的不同，可分為由底向上測試和從頂向下測試。 由底向上測試是先測最底層的模塊，然后依次向上測試，最后測試主模塊。從頂向下測試剛好與之相反，先測主模塊，然后按照從頂向下設計的順序依次測試各個模塊。為了加快調(diào)試的速度

19、，建議采用從頂向下的測試順序，只在發(fā)現(xiàn)某個模塊有錯時才進入下一層調(diào)試，這樣對迅速定位錯誤也有很大協(xié)助。 在運用這些測試措施時，我們要注意哪些問題呢？一方面，對自己所編的程序的構造、模塊的功能一定要了如指掌。采用從頂向下的測試措施時，常常是一種模塊還沒有測試完，就轉到了下一種模塊，因而特別容易忘掉和疏漏。如果對程序構造心中沒有概念，就很容易被弄糊涂。又如果對模塊的功能不是很清晰，則難以判斷模塊執(zhí)行成果的對錯，從而無法精確擬定錯誤所在。另一方面，測試需要有條理地進行。堅持使用同一種測試用例直到輸出對的為止；在一種模塊沒有測試完畢時，不要進行下一種模塊的測試，除非這個模塊是目前模塊的子模塊且在目前

20、模塊的測試中發(fā)現(xiàn)這個子模塊有錯。最后，在每次修改了源代碼之后一定要把已經(jīng)測過的所有測試用例再測一遍，以防產(chǎn)生新的錯誤。 講完了測試措施，我們再來講講測試用例的設計。 黑箱測試法的測試用例是根據(jù)輸入數(shù)據(jù)的不同狀況來設計的。由于一道題的輸入數(shù)據(jù)可以千變?nèi)f化，因此黑箱測試法不也許測遍所有的狀況。如有這樣一道題，已知程序規(guī)定輸入兩個LongInt類型的整數(shù)X、Y，輸出的是它們的和。X共有2^32個不同值，Y也有2^32個不同值，這樣不同的輸入數(shù)據(jù)共有2^32*2^32=2^64種不同狀況。假設執(zhí)行一遍程序要1毫秒，那么要測遍所有的不同狀況大概需要五億年，顯然是不也許做到的。 白箱測試法的測試用例

21、是根據(jù)程序內(nèi)部邏輯來設計的。要完全測試整個程序，測試用例就必須覆蓋程序的所有執(zhí)行途徑，這一般也是不也許的。例如，有一程序的流程圖如下： a P A Q C B F G D R H E 循環(huán)20次 I J b 其中從a到b有五條途徑，再外套循環(huán)20次，根據(jù)乘法原理，執(zhí)行一遍程序也許通過的不同途徑共有5^20≈10^14條。如果程序執(zhí)行一遍從a到

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

23、慮數(shù)據(jù)選擇，設計出測試用例，以達到測試目的。 有這樣一道題：輸入三個整數(shù)表達一種三角形的三條邊長。規(guī)定輸出能否構成一種三角形，如能則輸出是等腰，等邊還是既非等邊又非等腰三角形。 對于這道題，我們運用等價分類法，根據(jù)三角形與否合理可以將輸入數(shù)據(jù)提成兩個等價類：合理三角形和不合理三角形。對于合理三角形，我們可以繼續(xù)將該等價類分為等腰三角形和既非等邊又非等腰三角形，而對于等腰三角形，還可以分為單純的等腰三角形和等邊三角形。這樣我們通過不斷地等價分類最后共可以設計出四種測試用例。此外還可以根據(jù)輸入數(shù)據(jù)的不同排列方式來分類。但如果你的程序是先排序再進行判斷，并且可以保證排序?qū)Φ男?，就沒必要使用這種分

24、類措施。 ②邊界分析法 程序運營出錯常常發(fā)生在邊界狀態(tài)，因此在測試中我們常一方面根據(jù)程序的功能擬定邊界狀況的數(shù)據(jù)變化，以便設計測試用例。這種對邊界狀態(tài)進行分析，以設計測試用例來測試程序的措施稱為邊界分析法。 邊界值的選擇要根據(jù)題目實際狀況有針對性地，有一定發(fā)明性地進行。一般來說，可考慮如下幾種狀況： ㈠ 正好在邊界附近，且欲越界的數(shù)據(jù)； ㈡ 取最大或最小值，最多或至少值加減1的數(shù)據(jù)； ㈢ 循環(huán)或迭代的初始值與終值數(shù)據(jù)； ㈣ 有序集合的第一種或最后一種數(shù)據(jù)元素； ㈤ 零點附近的元素； ㈥ 最大誤差值的數(shù)據(jù)； ㈦ 數(shù)據(jù)量最大或最小的數(shù)據(jù) ㈧ 計算量最大或最小的數(shù)據(jù) 仍然使用

25、上面那道三角形的題目作為例子，有如下三個測試數(shù)據(jù)： a、 兩邊之和等于第三邊； b、 三個數(shù)中涉及0； c、 三個數(shù)均為0； a屬于第㈠種狀況，b、c屬于第㈤種狀況，這就是邊界值分析法的應用。 邊界分析法是很重要的一種措施，是一般測試中必不可少的。它比較精煉，又容易發(fā)現(xiàn)錯誤。問題在于有些程序的邊界狀況是極其復雜的，有時甚至不存在。例如說讓你把10個數(shù)從大到小排序輸出，由于算法只與兩個數(shù)之間的大小關系有關，與每個數(shù)的數(shù)值大小無關，數(shù)的總數(shù)也是固定的，這時就不存在邊界狀況，也就無法使用邊界分析法來設計測試用例。 ③錯誤推測法 錯誤推測法事實上是運用了黑箱白箱結合的思想，根據(jù)自己設計的

26、程序來找出容易浮現(xiàn)錯誤的地方，然后有針對性地設計測試用例。例如在一種有許多If-Then-Else語句嵌套的地方，就很容易浮現(xiàn)錯誤，而一般的測試用例很難找出這種錯誤。這時錯誤推測法就能派上大用場，對于這一系列的If-Else語句，設計出覆蓋不同途徑的測試用例，從而檢查程序的對的性。 至于具體測試時選用哪種措施，我們常用的方略是一方面用邊界分析法，再用等價分類法加以補充。最后對于程序中構造復雜的部分重點使用錯誤推測法進行測試。固然在時間容許的狀況下，應當使用更多的測試數(shù)據(jù)來覆蓋更多的功能。 3、 跟蹤調(diào)試 跟蹤調(diào)試一般是一件繁瑣的事。它需要選手的耐心和細心。選擇哪些變量進行跟蹤也是至關重要

27、的，精確的變量選擇可以起到事半功倍的效果。一般來說，一方面要跟蹤的是寄存輸入數(shù)據(jù)的變量，特別對于那些需要對輸入數(shù)據(jù)進行一定解決的題目來說更是如此，輸入數(shù)據(jù)不對的，雖然是對的的程序也會與答案不符合；另一方面是那些頻繁用到的全局變量，這些變量往往貫穿于整個程序中，一旦某處出錯，會影響到其她模塊的對的性，由此導致定位錯誤。出錯的地方?jīng)]有測試，對的的地方反而反復測試。因此對于這些全局變量的變化要密切加以關注，不可放過任何錯誤；再次就是那些循環(huán)變量了，跟蹤循環(huán)變量可以精確地得知程序的執(zhí)行進度，從時間上把握錯誤所在；最后其她的變量則要根據(jù)實際狀況加以選擇，對使用較多的變量應優(yōu)先加以跟蹤。 此外Watch

28、窗口的大小位置也要合理安排，使得在跟蹤過程中重要的變量的變化狀況可以一目了然，從而免除許多不必要的窗口切換，節(jié)省時間。 五、 總結 在信息學競賽中，程序效率高下并不是首要的。不對的的程序效率再高，也是等于零。效率低的程序只要對的，總是能拿到一點分數(shù)。因此調(diào)試水平的高下，很大限度上也反映了一種選手整體水平的高下。總的來說，程序的調(diào)試重要靠的還是經(jīng)驗。經(jīng)驗越豐富，調(diào)試效果也就越好。因此我們平時訓練時決不能只注意對思路算法的訓練，還應當注意訓練自己的調(diào)試水平。 六、 一種調(diào)試實例 題目： 在某些美國重要都市里，為公司傳送文獻和小物品的自行車快遞長期以來就是流動運送服務的一部分。波士頓的騎車

29、人是不同尋常的一族。她們以超速、不遵守單行道和紅綠燈、忽視汽車、出租、公交和行人的存在而臭名遠揚?？爝f服務競爭劇烈。比利快遞服務公司（BBMs）也不例外。為發(fā)展業(yè)務，制定合理的收費， BBMS正根據(jù)快遞員能走的最短路線制定一項快遞收費原則。而你則要替BBMS編寫一種程序來擬定這些路線的長度。 如下假設可以協(xié)助你簡化工作： ●快遞員可以在地面上除建筑物內(nèi)部以外的任何地方騎車。 ●地形不規(guī)則的建筑物可以覺得是若干矩形的合并。并規(guī)定，任何相交矩形擁有共同內(nèi)部，并且是同一建筑物的一部分。 ●盡管兩個不同的建筑物也許非常接近，但永遠不會重疊。（快遞員可以從任意兩個建筑物之間穿過。她們可以繞過最

30、急的拐彎，可以貼著建筑物的邊沿疾駛。） ●起點和終點不會落在建筑物內(nèi)部。 ●總有一條連接起訖點的線路。 12 Start 8 4 Stop O 4 8 12 下圖是一張典型的鳥瞰圖。 輸入文獻涉及如下若干行： 第一行：n 場景中描述建筑物的矩形個數(shù)。o<=n<=20 第二行：x1、y1、x2、y2 路線起訖點的x 和y坐標。 余下n行：x1、y1、x2、y2、x

31、3、y3 矩形三個頂點的坐標 所有x 、y坐標是屬于0到1000（涉及0和1000）的實數(shù)，每行中相鄰的坐標由一種或多種空格分開。正如下面輸出范例給出的那樣。輸出應給出從起點到終點的最短線路的長度，精確到小數(shù)點后第二位。 輸入范例 5 6.5 9 10 3 1 5 3 3 6 6 5.25 2 8 2 8 3.5 6 10 6 12 9 12 7 6 11 6 11 8 10 7 11 7

32、11 11 輸出范例 7.28 算法分析： 由輸入文獻的格式可以看出，每一種矩形輸入三個頂點P1，P2和P3。這三個頂點的坐標分別為（P1.x P1.y）、（P2.x，P2.y)、（P3.x，P3.y）。由于矩形的四條邊不一定平行x軸和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.x=

33、P2.x）and（P3.y＞=P2.y））。然后求出矩形的第四個頂點P4： P4.x＝P1.x+P3.x-P2.x P4.y＝P1.y+P3.y-P2.y 例如輸入矩形的三個頂點（3，3）、（1，5）、（6，6）。按上述措施排序后 P1=（1，5），P2=（3，3），P3=（6，6） P4.x＝p1．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互為對角。 由于快遞員是在地面上除建筑物內(nèi)部以外（涉及建筑物邊沿）的空間尋找一條

34、最短路線，因此，這條路線上的頂點除起訖兩個點外，其他都為矩形的頂點。最短路線上每條線段的兩個端點既不能被任何建筑物所擋。也不能為同一矩形的對角點（不能穿過矩形相應的建筑物）。 我們將最短路線的起點、終點以及每個矩形頂點放入一種頂點序列表P中，其中P[1]、P[4*n+2]存貯起訖點， P[2]…P[4*n＋1]存貯n個矩形的頂點。顯然，最短路線上的頂點取自于P表。在建立P表中的同步建立一張線段表L，將每個矩形的四條矩形邊和兩條對角線存入該表。設立L表的目的是為了判斷快遞員的行車路線與否符合規(guī)則。如果行車路線與表中任一條矩形邊相交，則闡明快遞員進入了建筑物內(nèi)部，這種狀況必須排除。問題是：為什

35、么L表還要存貯每個矩形的對角線呢？這是為了剔除一種如下圖的邊界錯誤。 起點 終點 如果起點和終點貼在同一種矩形邊上（這種狀況是容許的，由于快遞員可以貼著建筑物的邊沿疾駛），則快遞員將毫無顧忌地穿越“禁區(qū)”，由于兩點間未相交任何矩形邊。增設行車路線不能與矩形的對角線相交的條件，便可避免這個不易察覺的漏洞。 求最短途徑則可采用標號法。 程序： Program Corner; Const FinName='corner.in';{輸入文獻名} FoutName='corner.out';{輸出文獻名} MaxBuilding=20;{最大建筑物} Ma

36、xPoint=82;{最多頂點數(shù)} MaxLine=120;{最多線段數(shù)} Zero=1e-8;{相對極小量，用于實數(shù)比較} Type Location=Record{坐標類型} x,y:Real; End; Line=Array[1..2]Of Location;{線段類型} Var Bld,{建筑物數(shù)} Pnt,{頂點數(shù)} Lne:Integer;{線段數(shù)} P:Array[1..MaxPoint]Of Location;{頂點序列} L:Array[1..MaxLine]Of Line;{線段序列} Dis:

37、Array[1..MaxPoint]Of Real;{最短距離表} Function GetMin(Var a,b:Real):Real;{返回兩數(shù)較小值} Begin If a>b Then GetMin:=b Else GetMin:=a; End; Function GetMax(Var a,b:Real):Real; {返回兩數(shù)較小值} Begin If a>b Then GetMax:=a Else GetMax:=b; End; Function GetMulti(p0,p1,p2:Location):Real;{計算叉積} Begin GetMu

38、lti:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); End; Function Intersect(Var L1,L2:Line):Boolean;{判斷兩條線段與否相交} Var M1,M2,M3,M4:Real; Begin Intersect:=False; If (GetMin(L1[1].x,L1[2].x)<=GetMax(L2[1].x,L2[2].x)) And(GetMax(L1[1].x,L1[2].x)>=GetMin(L2[1].x,L2[2].x)) And(GetM

39、in(L1[1].y,L1[2].y)<=GetMax(L2[1].y,L2[2].y)) And(GetMax(L1[1].y,L1[2].y)>=GetMin(L2[1].y,L2[2].y)) Then {通過迅速排斥實驗} Begin M1:=GetMulti(L1[1],L2[1],L1[2]);M2:=GetMulti(L1[1],L1[2],L2[2]); M3:=GetMulti(L2[1],L1[1],L2[2]);M2:=GetMulti(L2[1],L2[2],L1[2]); If (Abs(M1)>Zero)An

40、d(Abs(M2)>Zero) And(Abs(M3)>Zero)And(Abs(M4)>Zero) And(M1*M2>0)And(M3*M4>0) Then Intersect:=True; End; End; Procedure GetNextPoint(Var P1,P2,P3,P4:Location); {將頂點排序并計算第四個頂點坐標} Var T:Location; Begin If (P2.x

41、;P2:=T;End; If (P3.x

42、adLn(Bld); Lne:=0;Pnt:=1; ReadLn(P[1].x,P[1].y,P[Bld*4+2].x,P[Bld*4+2].y); For i:=1 to Bld Do Begin For j:=1 to 3 Do Read(P[Pnt+j].x,P[Pnt+j].y); ReadLn; GetNextPoint(P[Pnt+1],P[Pnt+2],P[Pnt+3],P[Pnt+4]); For j:=1 to 3 Do Begin L

43、[Lne+j,1]:=P[Pnt+j]; L[Lne+j,2]:=P[Pnt+j+1]; End; L[Lne+4,1]:=P[Pnt+4];L[Lne+4,2]:=P[Pnt+1]; L[Lne+5,1]:=P[Pnt+1];L[Lne+5,2]:=P[Pnt+3]; L[Lne+6,1]:=P[Pnt+2];L[Lne+6,2]:=P[Pnt+4]; Inc(Pnt,4);Inc(Pnt,6); End; Inc(Pnt); End; Function GetDis(a,b:

44、Byte):Real;{計算兩點間距離} Begin GetDis:=Sqrt((P[a].x-P[b].x)*(P[a].x-P[b].x)+(P[a].y-P[b].y)*(P[a].y-P[b].y)); End; Function Visible(Var P1,P2:Location):Boolean; {判斷在P1點與否能看到P2點，即判斷兩點之間與否有建筑物阻擋} Var TL:Line; i:Byte; Begin TL[1]:=P1;TL[2]:=P2; For i:=1 to Lne Do If Intersect(L[i]

45、,TL) Then Begin Visible:=False;Exit;End; Visible:=True; End; Procedure Main;{主程序，用標號法求最短途徑} Var i,j,k:Byte; Min:Real; S:Set Of Byte; Begin Dis[1]:=0; For i:=2 to Pnt Do If Visible(P[1],P[i]) Then Dis[i]:=GetDis(1,i) Else Dis[i]:=1e10; S:=[1]; For i:=2 t

46、o Pnt Do Begin Min:=1e10;k:=0; For j:=2 to Pnt Do If (Not(j In S))And(Dis[j]

47、 Dis[j]:=Dis[k]+GetDis(j,k); End; WriteLn(Dis[Pnt]:0:2);{輸出答案} End; Begin Assign(Input,FinName); Reset(Input); Assign(Output,FoutName); Rewrite(Output); Init; Main; Close(Input); Close(Output); End. 這個程序編譯已經(jīng)通過，目前我們進行靜態(tài)查錯。一方面擬定了函數(shù)GetMin，GetMax，GetMulti是對的的。

48、由于這三個函數(shù)很短，也很簡樸，因此只要通過靜態(tài)查錯應當就可以了。接著往下看，發(fā)目前過程Init中有一行是Inc（Pnt，4）；Inc（Pnt，6）；明顯不對。程序的本意顯然是要增長Pnt和Lne的值，因此應當把Inc（Pnt，6）換成Inc（Lne，6）。再往下，又發(fā)目前函數(shù)Intersect中計算叉積時持續(xù)給M2賦了兩次值，這樣前面一次賦值就沒故意義了，這明顯是一種書寫錯誤，背面的M2應改為M4。再往下就沒有發(fā)現(xiàn)其她錯誤了。 接著進入動態(tài)查錯，我們用的第一種例子固然是樣例，輸入樣例后發(fā)現(xiàn)輸出7.28，與答案一致。因此沒有必要再進行模塊測試。目前應當設計自己的測試用例了。 一方面使用邊界值

49、分析法，這道題在建筑物個數(shù)上有兩個邊界：0和20。上邊界測使用例設計比較繁瑣，因此我們先嘗試下邊界0以及下邊界附近的1。坐標也有兩個邊界：0和1000，我們可以結合建筑物個數(shù)的邊界，得到如下兩個測試用例： coner1.in 0 0 0 1000 1000 corner2.in 1 0 0 1000 1000 0 0 0 1000 1000 1000 對于corner1程序輸出是1414.21，對的。對于corner2程序輸出是.00，也是對的的。接下去我們采用等價分類法設計測試用例。 一方面根據(jù)數(shù)據(jù)的排列方式進行分類，我們只使用一種矩形，然后把它的三個頂點的六種排列方式都進

50、行嘗試，這樣共有6個測試用例，下面僅列出一種： corner3.in 1 0 0 1 1 0 0 0 1 1 1 答案應當全為2.00，但測到頂點排列方式為0 1 1 1 0 0時，程序輸出了1.41，由于其她條件都不變，因此最有也許便是過程GetNextPoint出錯。使用Go to cursor執(zhí)行到過程GetNextPoint開頭處，添加變量數(shù)組P到Watch窗口，再使用Trace into一步步執(zhí)行下去。我們看到程序?qū)1、P2沒有進行互換，對P2、P3進行了互換，但根據(jù)我們的算法，顯然需要把（0，0）放到第一種位置。由此恍然大悟，應當在比較完P1、P2后，再比較P1、P3，

51、最后才比較P2、P3。因此應當在第一句If-Then-Else語句后添上： If (P3.x

52、r9.in{涉及} 2 1 0 1 3 0 0 0 3 3 3 1 1 1 2 2 2 corner10.in{相交} 2 1 0 1 1 0 0 0 1 2 1 1 0 1 1 3 1 corner11.in{相離，但十分接近} 2 1 0 1 1 0 0 0 1 1 1 1.0001 0 1.0001 1 3 1 Stop Start 10、11兩個測試用例沒有問題，第9個輸出了3，有問題，答案應當是5才對。我們進入模塊調(diào)試，數(shù)據(jù)讀入及初始化沒有問題，接下去進入Main繼續(xù)跟蹤，一方面我們對第一種循環(huán)用Go to curso

53、r一步執(zhí)行完畢，檢查數(shù)組Dis，發(fā)現(xiàn)除起點外共有4個點的值不不小于1e10。由于這是一種矩形涉及的用例，按理應當只有兩個點的值會不不小于1e10。檢查這四個點，發(fā)現(xiàn)被涉及的那個矩形有兩個點也被計算在內(nèi)。仔細一想就明白了，我們雖然加上了兩條對角線，但是對于處在矩形內(nèi)部的點還是無法排除，我們的程序選擇的最短途徑應當就是沿直線走，由于中間多了兩個矩形頂點把它分為三條線段，這兩個頂點又正好在對角線上，因此這三條線段都不與對角線相交。程序就選擇了這條“最短途徑”走。 解決方案：由于起點和終點都不會在矩形內(nèi)部，因此我們可以在讀完所有頂點后，排除那些處在矩形內(nèi)部的點。具體修改可見附錄。 我們還可以按照起

54、點和終點的位置關系進行分類，由于這牽涉到矩形的分布，狀況比較復雜，因此我們只考慮起點和終點與否重疊，因此還需添加一種測試用例： corner11.in 0 0 0 0 0 輸出為0.00，對的。 最后我們使用錯誤推測法，這道題中最復雜的無疑是Intersect和InBuilding這兩個函數(shù)。因此可以針對這兩個函數(shù)，把它們分別作為一道小題目來測?？梢詤⒄丈厦嬷v的環(huán)節(jié)設計測試用例，先用邊界值分析法，后用等價分類法，具體的測試用例就不再給出。這樣測試后的成果也是沒有錯誤。整道題的測試到此就圓滿完畢了。 【附錄】 一、 修改后的程序 {闡明：紅色表達修改后的部分} Program

55、Corner; Const FinName='corner.in';{輸入文獻名} FoutName='corner.out';{輸出文獻名} MaxBuilding=20;{最大建筑物} MaxPoint=82;{最多頂點數(shù)} MaxLine=120;{最多線段數(shù)} Zero=1e-8;{相對極小量，用于實數(shù)比較} Type Location=Record{坐標類型} x,y:Real; End; Line=Array[1..2]Of Location;{線段類型} Var Bld,{建筑物數(shù)} Pnt,{頂點

56、數(shù)} Lne:Integer;{線段數(shù)} P:Array[1..MaxPoint]Of Location;{頂點序列} L:Array[1..MaxLine]Of Line;{線段序列} Dis:Array[1..MaxPoint]Of Real;{最短距離表} Function GetMin(Var a,b:Real):Real;{返回兩數(shù)較小值} Begin If a>b Then GetMin:=b Else GetMin:=a; End; Function GetMax(Var a,b:Real):Real; {返回兩數(shù)較小值} Begin

57、 If a>b Then GetMax:=a Else GetMax:=b; End; Function GetMulti(p0,p1,p2:Location):Real;{計算叉積} Begin GetMulti:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); End; Function Intersect(Var L1,L2:Line):Boolean;{判斷兩條線段與否相交} Var M1,M2,M3,M4:Real; Begin Intersect:=False; If (GetMin(L1[1]

58、.x,L1[2].x)<=GetMax(L2[1].x,L2[2].x)) And(GetMax(L1[1].x,L1[2].x)>=GetMin(L2[1].x,L2[2].x)) And(GetMin(L1[1].y,L1[2].y)<=GetMax(L2[1].y,L2[2].y)) And(GetMax(L1[1].y,L1[2].y)>=GetMin(L2[1].y,L2[2].y)) Then {通過迅速排斥實驗} Begin M1:=GetMulti(L1[1],L2[1],L1[2]);M2:=GetMulti(L1[1],L1[

59、2],L2[2]); M3:=GetMulti(L2[1],L1[1],L2[2]);M4:=GetMulti(L2[1],L2[2],L1[2]); If (Abs(M1)>Zero)And(Abs(M2)>Zero) And(Abs(M3)>Zero)And(Abs(M4)>Zero) And(M1*M2>0)And(M3*M4>0) Then Intersect:=True; End; End; Procedure GetNextPoint(Var P1,P2,P3,P4:Location); {將頂點排序并計算第

60、四個頂點坐標} Var T:Location; Begin If (P2.x

61、4.x:=P1.x+P3.x-P2.x; P4.y:=P1.y+P3.y-P2.y; End; Function InBuilding(Var p0:Location):Boolean;{判斷點與否在矩形內(nèi)} Var i,j,k:Byte; M1,M2:Real; Temp:Boolean; Begin k:=1; For i:=1 to Bld Do Begin M1:=GetMulti(p0,P[k+4],P[k+1]); If Abs(M1)

62、=True; For j:=1 to 3 Do Begin M2:=GetMulti(p0,P[k+j],P[k+j+1]); If (Abs(M2)

63、讀入數(shù)據(jù)，并初始化} Var i,j:Byte; Mark:Array[1..MaxPoint]Of Boolean;{對要去掉的點坐上標記} Begin ReadLn(Bld); Lne:=0;Pnt:=1; ReadLn(P[1].x,P[1].y,P[Bld*4+2].x,P[Bld*4+2].y); For i:=1 to Bld Do Begin For j:=1 to 3 Do Read(P[Pnt+j].x,P[Pnt+j].y); ReadLn; GetNextPoin

64、t(P[Pnt+1],P[Pnt+2],P[Pnt+3],P[Pnt+4]); For j:=1 to 3 Do Begin L[Lne+j,1]:=P[Pnt+j]; L[Lne+j,2]:=P[Pnt+j+1]; End; L[Lne+4,1]:=P[Pnt+4];L[Lne+4,2]:=P[Pnt+1]; L[Lne+5,1]:=P[Pnt+1];L[Lne+5,2]:=P[Pnt+3]; L[Lne+6,1]:=P[Pnt+2];L[Lne+6,2]:

65、=P[Pnt+4]; Inc(Pnt,4);Inc(Lne,6); End; Inc(Pnt); FillChar(Mark,SizeOf(Mark),False); For i:=2 to Pnt Do If InBuilding(P[i]) Then Mark[i]:=True; i:=2; While i

66、 End; End; Function GetDis(a,b:Byte):Real;{計算兩點間距離} Begin GetDis:=Sqrt((P[a].x-P[b].x)*(P[a].x-P[b].x)+(P[a].y-P[b].y)*(P[a].y-P[b].y)); End; Function Visible(Var P1,P2:Location):Boolean; {判斷在P1點與否能看到P2點，即判斷兩點之間與否有建筑物阻擋} Var TL:Line; i:Byte; Begin TL[1]:=P1;TL[2]:=P2; For i:=1 to Lne Do If Intersect(L[i],TL) Then Begin Visible:=False;Exit;End; Visible:=True; End; Procedure Main;{主程序，用標號法求最短途徑} Var i,j,k:Byte; Min:Real; S:Set Of Byte; Begin D