PMChap6小程序設(shè)計(jì)的基本方法

1、第六章第六章 程序設(shè)計(jì)基本方法程序設(shè)計(jì)基本方法主要內(nèi)容：主要內(nèi)容：n引言引言-程序設(shè)計(jì)的基本原則程序設(shè)計(jì)的基本原則n選擇語句的設(shè)計(jì)選擇語句的設(shè)計(jì)n循環(huán)語句的設(shè)計(jì)循環(huán)語句的設(shè)計(jì)n循環(huán)不變式的設(shè)計(jì)循環(huán)不變式的設(shè)計(jì)n界函數(shù)的設(shè)計(jì)界函數(shù)的設(shè)計(jì)6.1 程序設(shè)計(jì)的基本原則程序設(shè)計(jì)的基本原則principle 1: a program and its proof should be developed hand in hand, with the proof usually leading the way, 一個(gè)程序和它的正確性證明應(yīng)同時(shí)設(shè)計(jì)，并且最一個(gè)程序和它的正確性證明應(yīng)同時(shí)設(shè)計(jì)，并且最好以考慮證明為先

2、導(dǎo)。好以考慮證明為先導(dǎo)。principle 2：使用理論來提供正確性的理解，而：使用理論來提供正確性的理解，而在適當(dāng)?shù)牡胤接贸ＷR(shí)和直觀方法，但當(dāng)出現(xiàn)困難在適當(dāng)?shù)牡胤接贸ＷR(shí)和直觀方法，但當(dāng)出現(xiàn)困難和復(fù)雜情況時(shí)，仍然依據(jù)形式理論作保證。當(dāng)然和復(fù)雜情況時(shí)，仍然依據(jù)形式理論作保證。當(dāng)然一個(gè)人只有既有常識(shí)又掌握理論才能有效地在形一個(gè)人只有既有常識(shí)又掌握理論才能有效地在形式化和常識(shí)之間進(jìn)行協(xié)調(diào)，前者是程序員一直在式化和常識(shí)之間進(jìn)行協(xié)調(diào)，前者是程序員一直在使用。使用。6.1 程序設(shè)計(jì)的基本原則程序設(shè)計(jì)的基本原則principle 3：要了解將用程序來處理的對：要了解將用程序來處理的對象的性質(zhì)。象的性質(zhì)。例：

3、假設(shè)有一袋裝有黑白兩色棋子。每次例：假設(shè)有一袋裝有黑白兩色棋子。每次從袋中任取兩粒子，若它們同色，則丟掉從袋中任取兩粒子，若它們同色，則丟掉這兩粒子，然后再補(bǔ)進(jìn)一只黑子，否則丟這兩粒子，然后再補(bǔ)進(jìn)一只黑子，否則丟掉黑子，放回白子。連續(xù)執(zhí)行這一步驟，掉黑子，放回白子。連續(xù)執(zhí)行這一步驟，直至袋中只剩下一子為止。試問最后這一直至袋中只剩下一子為止。試問最后這一子是黑或白？編一程序回答此問題。子是黑或白？編一程序回答此問題。6.1 程序設(shè)計(jì)的基本原則程序設(shè)計(jì)的基本原則principle 4：不要忽視任何看起來十分明顯的原：不要忽視任何看起來十分明顯的原則，只有通過有意識(shí)地運(yùn)用這些原則才會(huì)獲得成則，只有

4、通過有意識(shí)地運(yùn)用這些原則才會(huì)獲得成功。功。principle 5：認(rèn)識(shí)一個(gè)原則和應(yīng)用一個(gè)原則是兩：認(rèn)識(shí)一個(gè)原則和應(yīng)用一個(gè)原則是兩回事?；厥?。 ideas may be simple and easy to understand, but their application may require efforts. recognizing a principle and applying it are two different things.principle 6:在著手編程之前，首先要弄清楚問題在著手編程之前，首先要弄清楚問題是要求是要求“做什么做什么”的，并將其抽象化為前置條件的，并將其抽

5、象化為前置條件和后置條件，即給出精確的程序規(guī)范，且勿倉促和后置條件，即給出精確的程序規(guī)范，且勿倉促編碼。編碼。6.1 程序設(shè)計(jì)的基本原則程序設(shè)計(jì)的基本原則principle 7: 程序設(shè)計(jì)是一種面向目標(biāo)的設(shè)計(jì)活動(dòng)。即程序設(shè)計(jì)是一種面向目標(biāo)的設(shè)計(jì)活動(dòng)。即程序設(shè)計(jì)是圍繞著目標(biāo)程序設(shè)計(jì)是圍繞著目標(biāo)q進(jìn)行的，這意味著進(jìn)行的，這意味著q起著比起著比p更重要的作用。更重要的作用。關(guān)于證明和測試數(shù)據(jù)分析關(guān)于證明和測試數(shù)據(jù)分析n邊進(jìn)行程序設(shè)計(jì)，邊寫下有關(guān)的測試數(shù)據(jù)。關(guān)鍵在邊進(jìn)行程序設(shè)計(jì)，邊寫下有關(guān)的測試數(shù)據(jù)。關(guān)鍵在于有效地選擇和生成測試數(shù)據(jù)集；于有效地選擇和生成測試數(shù)據(jù)集；n從工程角度看，測試是重要的；從工程

6、角度看，測試是重要的；n但從人員培訓(xùn)的角度看，應(yīng)該訓(xùn)練程序員具有編制但從人員培訓(xùn)的角度看，應(yīng)該訓(xùn)練程序員具有編制正確程序的能力；正確程序的能力；n因此，學(xué)習(xí)和研究形式證明技術(shù)是培養(yǎng)能力的一種因此，學(xué)習(xí)和研究形式證明技術(shù)是培養(yǎng)能力的一種有效的途徑有效的途徑n測試只能證明程序有錯(cuò)，并不能證明程序是正確的。測試只能證明程序有錯(cuò)，并不能證明程序是正確的。test對程序員的科學(xué)訓(xùn)練是十分重要的，有人曾做對程序員的科學(xué)訓(xùn)練是十分重要的，有人曾做過一個(gè)試驗(yàn)：一個(gè)題目由一批印度的程序員和過一個(gè)試驗(yàn)：一個(gè)題目由一批印度的程序員和中國的程序員來做，結(jié)果如何？中國的程序員來做，結(jié)果如何？n由一批印度程序員來做，其結(jié)

7、果驚人地相似；由一批印度程序員來做，其結(jié)果驚人地相似；n而由一批中國程序員來做，編出的程序五花八門。而由一批中國程序員來做，編出的程序五花八門。只有規(guī)范的科學(xué)的編程，一個(gè)大項(xiàng)目才能得到只有規(guī)范的科學(xué)的編程，一個(gè)大項(xiàng)目才能得到有效地管理，其質(zhì)量才有保證。創(chuàng)造性應(yīng)該發(fā)有效地管理，其質(zhì)量才有保證。創(chuàng)造性應(yīng)該發(fā)揮在適當(dāng)?shù)牡胤?。揮在適當(dāng)?shù)牡胤健?.1 程序設(shè)計(jì)的基本原則程序設(shè)計(jì)的基本原則 高效的程序員不應(yīng)該浪費(fèi)很多的時(shí)間用于程序調(diào)高效的程序員不應(yīng)該浪費(fèi)很多的時(shí)間用于程序調(diào)試，他們一開始就不要把缺陷引入試，他們一開始就不要把缺陷引入 “程序測試是表明故障的非常有效的方法，但對程序測試是表明故障的非常有效的

8、方法，但對于證明沒有故障，調(diào)試是很無能為力的于證明沒有故障，調(diào)試是很無能為力的”關(guān)于小程序的設(shè)計(jì)關(guān)于小程序的設(shè)計(jì)n70年代對小程序設(shè)計(jì)有很多的研究年代對小程序設(shè)計(jì)有很多的研究n小程序設(shè)計(jì)是大規(guī)模程序正確性的基礎(chǔ)。設(shè)一小程序設(shè)計(jì)是大規(guī)模程序正確性的基礎(chǔ)。設(shè)一個(gè)大程序是由個(gè)大程序是由n個(gè)小程序組成，每個(gè)程序正確個(gè)小程序組成，每個(gè)程序正確的概率是的概率是p，那么整個(gè)程序正確的概率，那么整個(gè)程序正確的概率p滿足：滿足： p0,尋找既尋找既 定值定值x. 若若x在在b中出現(xiàn)多次，任意找到一次即可。有：中出現(xiàn)多次，任意找到一次即可。有：解：解：p : n0 q : (0 i 0 q: s = i: 0in

9、: bi要求循環(huán)滿足下面的不變式和界函數(shù)要求循環(huán)滿足下面的不變式和界函數(shù)不變式不變式 : 0i n (s = j: 0j0 x20q: y1 = y2 = gcd(x1,x2)不變式不變式 ： 0y1 0y2 gcd(y1,y2)=gcd(x1,x2 )界函數(shù)界函數(shù) ：y1+y26.3循環(huán)語句的設(shè)計(jì)循環(huán)語句的設(shè)計(jì)解：解： 最大公約數(shù)的性質(zhì)：對任意的最大公約數(shù)的性質(zhì)：對任意的0y1y1 類似有類似有 ： y1 := y1-y2 條件：條件： y1y2得程序如下：得程序如下：6.3循環(huán)語句的設(shè)計(jì)循環(huán)語句的設(shè)計(jì)x10 x20y1,y2 := x1,x2 界函數(shù)界函數(shù) ：y1+y2do y1y2 y1

10、 := y1-y2od y1=y2q: y1 = y2 = gcd(x1,x2)x10 x20y1,y2 := x1,x2 界函數(shù)界函數(shù) ：y1+y2do y1 y2 y1 y2 if y1y2 y1 := y1-y2 fiod y1=y2q: y1 = y2 = gcd(x1,x2)6.3循環(huán)語句的設(shè)計(jì)循環(huán)語句的設(shè)計(jì)例例2：檢索一個(gè)二維數(shù)組：檢索一個(gè)二維數(shù)組：p: order(b0:m-1,0:n-1) n0 m 0q: (0im 0 jn x=bi,j x b) 即給出一個(gè)有序的二維數(shù)組（有可能為空）查找即給出一個(gè)有序的二維數(shù)組（有可能為空）查找x 0 j n-1 ： 0i m 0 j n

11、 x不在這里不在這里 i m-1 : (m-i)*n-j+m-i (他表明了未搜索的值的個(gè)數(shù)和行的他表明了未搜索的值的個(gè)數(shù)和行的個(gè)數(shù)之和個(gè)數(shù)之和) 思考：思考： 中沒有中沒有m-i 是否可以？是否可以？6.3循環(huán)語句的設(shè)計(jì)循環(huán)語句的設(shè)計(jì)解：初始化語句解：初始化語句 i,j :=0,0; 顯然顯然 j:=j+1, i:=i+1 都可以使得都可以使得 減小，由減小，由 c1 wp(“j:=j+1”, ) 可得：可得： im j n x bi,j j:=j+1 是相應(yīng)的條件是相應(yīng)的條件c1但：但： c1 q而：而： i:=i+1 只有在只有在 im j=n 時(shí)才能執(zhí)行，因此有：時(shí)才能執(zhí)行，因此有：

12、i m j=n i,j := i+1,0程序：程序： i,j :=0,0; do im j n x bi,j j:=j+1 im j=n i,j := i+1,0 od6.3循環(huán)語句的設(shè)計(jì)循環(huán)語句的設(shè)計(jì)討論：討論：n程序語句應(yīng)使界函數(shù)遞減，界函數(shù)以什程序語句應(yīng)使界函數(shù)遞減，界函數(shù)以什么樣的軌跡減小決定了該程序的設(shè)計(jì)，么樣的軌跡減小決定了該程序的設(shè)計(jì)，而界函數(shù)的軌跡早已蘊(yùn)涵在而界函數(shù)的軌跡早已蘊(yùn)涵在 中了。中了。n因此說，一個(gè)不變式代表了一個(gè)循環(huán)語因此說，一個(gè)不變式代表了一個(gè)循環(huán)語句，不同的不變式就可能得出不同的循句，不同的不變式就可能得出不同的循環(huán)語句。環(huán)語句。reviewdo循環(huán)的驗(yàn)證項(xiàng)目循

13、環(huán)的驗(yàn)證項(xiàng)目程序設(shè)計(jì)的基本原則程序設(shè)計(jì)的基本原則選擇語句的設(shè)計(jì)原則：語句選擇語句的設(shè)計(jì)原則：語句-條件條件循環(huán)語句的設(shè)計(jì)策略：衛(wèi)哨先行、走循環(huán)語句的設(shè)計(jì)策略：衛(wèi)哨先行、走向終止向終止6.4 不變式的構(gòu)造不變式的構(gòu)造構(gòu)造不變式有兩類方法：構(gòu)造不變式有兩類方法：1. 削弱削弱q構(gòu)造構(gòu)造 ：n刪除刪除 q 的一個(gè)合取分量的一個(gè)合取分量n替換替換 q 中的常量為變量中的常量為變量n擴(kuò)大擴(kuò)大 q 中變量的變化范圍等中變量的變化范圍等2. 聯(lián)合聯(lián)合p和和q構(gòu)造構(gòu)造 適合于輸入變適合于輸入變量的值不因程量的值不因程序的執(zhí)行而變序的執(zhí)行而變化的情況化的情況適用于輸入變適用于輸入變量的值因程序量的值因程序的執(zhí)行

14、而變化的執(zhí)行而變化的情況。的情況。6.4 不變式的構(gòu)造不變式的構(gòu)造1.氣球理論（氣球理論（the balloon theory）一般情況下，一般情況下， bb = q , 因此因此q . 把把q看成看成一個(gè)癟了氣的氣球。逐漸放寬對一個(gè)癟了氣的氣球。逐漸放寬對q的限制，即削弱的限制，即削弱q，即將氣球吹大，直至包含循環(huán)的初始狀態(tài)（這個(gè)初即將氣球吹大，直至包含循環(huán)的初始狀態(tài)（這個(gè)初始狀態(tài)頂多幾條簡單賦值和選擇語句可以得到）始狀態(tài)頂多幾條簡單賦值和選擇語句可以得到）isq初始狀態(tài)nn-110.6.4 不變式的構(gòu)造不變式的構(gòu)造 n， n-1，.， 1 ， 0描述了整個(gè)吹氣的過描述了整個(gè)吹氣的過程，一旦

15、到達(dá)邊界，就考慮如何泄氣使程，一旦到達(dá)邊界，就考慮如何泄氣使 回回到到q。這個(gè)過程就是設(shè)計(jì)一個(gè)循環(huán)，每迭代。這個(gè)過程就是設(shè)計(jì)一個(gè)循環(huán)，每迭代一步就漏氣一次，最后收縮到一步就漏氣一次，最后收縮到q的動(dòng)作。的動(dòng)作。吹氣的過程是設(shè)計(jì)吹氣的過程是設(shè)計(jì) 的過程，而漏氣的過程是的過程，而漏氣的過程是設(shè)計(jì)循環(huán)體的過程。因此，將設(shè)計(jì)不變式的設(shè)計(jì)循環(huán)體的過程。因此，將設(shè)計(jì)不變式的方法歸結(jié)為削弱謂詞方法歸結(jié)為削弱謂詞q的過程。的過程。6.4 不變式的構(gòu)造不變式的構(gòu)造2. 削弱削弱q就就 - 刪除刪除q的合取分量的合取分量 （ab c可以削弱為可以削弱為ab 或或ac ）策略：假定策略：假定q是一個(gè)合取式，可以試著

16、刪除其是一個(gè)合取式，可以試著刪除其某個(gè)合取分量而構(gòu)造某個(gè)合取分量而構(gòu)造 ，而被刪除的分量的否，而被刪除的分量的否定式作為循環(huán)條件（衛(wèi)哨）定式作為循環(huán)條件（衛(wèi)哨）c。例例1：寫一個(gè)程序，對給定的整數(shù)：寫一個(gè)程序，對給定的整數(shù)x0，求滿，求滿足如下的關(guān)系的足如下的關(guān)系的r： q： 0 r2 x (r+1) 2 即，即，r是不超過是不超過sqrt(x)的最大整數(shù)的最大整數(shù)。6.4 不變式的構(gòu)造不變式的構(gòu)造解：解：p ： x 0q可寫成：可寫成：0 r2 r2 x x (r+1) 2從從q中刪除中刪除x (r+1) 2，得一個(gè)可能得不變式，得一個(gè)可能得不變式 ： ： 0 r2 r2 x 由由p， 得初

17、始化語句：得初始化語句： r:=0, 使得使得p r:=0 成立。成立。循環(huán)條件：循環(huán)條件： c = （x (r+1) 2 ） c =（ x (r+1) 2 ) 得程序：得程序： r:=0 do (r+1) 2 x ? od界函數(shù)界函數(shù) ： sqrt（x）- r循環(huán)體語句：循環(huán)體語句： r:=r+1;6.4 不變式的構(gòu)造不變式的構(gòu)造3. 削弱削弱q就就 - 用變量替換常量用變量替換常量策略：策略：用變量替換用變量替換q中的有關(guān)常量，且給出此變量的適當(dāng)中的有關(guān)常量，且給出此變量的適當(dāng)變化范圍，以此削弱變化范圍，以此削弱q而構(gòu)造而構(gòu)造 。例例1：平臺(tái)問題：對給定的有序（平臺(tái)問題：對給定的有序（ ）

18、數(shù)組）數(shù)組b0:n-1,數(shù)組數(shù)組的平臺(tái)是一串相等值的序列，要求寫一個(gè)程序，存的平臺(tái)是一串相等值的序列，要求寫一個(gè)程序，存b的最的最長平臺(tái)的長度于變量長平臺(tái)的長度于變量l中。即此程序執(zhí)行后將確立中。即此程序執(zhí)行后將確立q： q: l 是是b0:n-1的最長平臺(tái)的長度的最長平臺(tái)的長度解：解：b是有序的，是有序的， 區(qū)間區(qū)間bj,k是平穩(wěn)的是平穩(wěn)的 (bj=bk) q: ( k:0 kn-l:bk=bk+l-1) ( i: 0 i0 ordered(b0:n-1) : 1 i n l 是是b0:i-1的最長平臺(tái)的長度的最長平臺(tái)的長度 界函數(shù)界函數(shù) ： n-i6.4 不變式的構(gòu)造不變式的構(gòu)造衛(wèi)哨：衛(wèi)哨

19、： i n循環(huán)初值：循環(huán)初值： i,l :=1,1; 可使可使p i,l :=1,1; 成立成立i:=i+1 可使可使 遞減，遞減， 條件：條件： bi bi-l反之，反之， 當(dāng)當(dāng)bi = bi-l時(shí)，時(shí)，l:=l+1;i:=i+1得程序：得程序： i,l :=1,1;do i n if bi bi-l i:=i+1 ; bi = bi-l l:=l+1;i:=i+1; fi od6.4 不變式的構(gòu)造不變式的構(gòu)造例例2：已知：已知 n0, 求整數(shù)數(shù)組求整數(shù)數(shù)組 b0:n-1的的和存于和存于s中。有：中。有：np: n0nq: s = j: 0jn : bj以變量替換常量：以變量替換常量： ：0

20、i n s =(j: 0ji : bj) : n-i6.4 不變式的構(gòu)造不變式的構(gòu)造例例3：寫一個(gè)程序，對給定的整數(shù)：寫一個(gè)程序，對給定的整數(shù)n0，求，求a，使，使r為真：為真： r： a2 n (a+1)2設(shè)計(jì)不變式：設(shè)計(jì)不變式： 用用b替換（替換（a+1），并令），并令ab, b n+1, : ab b n+1 a2 n b2 : b-a-1程序：程序： a, b := 0,n+1; do a+1 b d :=(a+b)/2; if d*d n b:=d; fi od6.4 不變式的構(gòu)造不變式的構(gòu)造4. 削弱削弱q就就 -擴(kuò)大變量的取值范圍擴(kuò)大變量的取值范圍 策略：策略： 擴(kuò)大擴(kuò)大q中某些

21、中某些變量的取值范圍變量的取值范圍 ，以次削弱，以次削弱q構(gòu)造構(gòu)造 。例：令例：令f0:n,g0:n,h0:n是三個(gè)固定的單調(diào)上升的整數(shù)是三個(gè)固定的單調(diào)上升的整數(shù)數(shù)組（數(shù)組（n0）。已知他們存在公共值。寫一程序，求最?。Ｒ阎麄兇嬖诠仓?。寫一程序，求最小公共值在公共值在f,g,h中的位置。中的位置。解：解：p: n0 令令i0,j0,k0滿足：滿足：fi0=gj0=hk0 i j k: ii0 jj0 k fi gj hk 即是最小公共值所處的位置，執(zhí)行后滿足：即是最小公共值所處的位置，執(zhí)行后滿足： q： i=i0 j=j0 k=k0 ：0 i i0 0 j j0 0 k k0 : i0-i+j0-j+k0-k 6.4 不變式的構(gòu)造不變式的構(gòu)造程序：程序：初始語句：初始語句： i,j,k:=0,0,0;