講義第三章上

Chapter3.結構化程序

設計方法(上）謝在鵬Email:zxiehhu@163.com本講義修改自葉楓老師去年的講義

1結構化程序設計特征有代表性的幾個特征有以下幾種：避免使用goto語句的程序設計；自頂向下、逐步求精、模塊化的程序設計；一種組織和編寫程序的方法，利用它編寫的程序容易理解和修改正確性的證明容易實現(xiàn)每一步驗證正確性，自動導致自我說明和自我捍衛(wèi)結構化程序設計把任意大而復雜的流程圖轉變?yōu)闃藴市问?，使得它們能夠用幾種標準的控制結構（通常是順序、分支和重復）來表示2例:編寫程序打印前N（N是正整數(shù)）個素數(shù)采用逐步求精的方法第一步：根據(jù)問題程序結構如下

functionF1(){ intn,number; cin>>n; number=2; while(number<n){ if(number是素數(shù)）//1和該數(shù)自身外，無法被其他自然數(shù)整除

cout<<number; number=下一個值；}}3第二步:對number是一個素數(shù)求精

intk=2;Boolprim=false; intlim=number-1; do{ if(number能被k整除）{

prim=false;} else{k++;prim=true;} }while(!prim||k達到上限值）第三步：對number能被k整除進一步求精，對k達到上限值求精

(number%k)==0k<=lim;第四步：補充完程序第五步：從所有的素數(shù)除了2意外都是奇數(shù)的角度優(yōu)化程序4結構化程序設計的思想-1結構化程序設計的思想：自頂向下，逐步求精。（1）程序的結構按照功能劃分若干個基本模塊，（2）這些模塊形成一個樹狀結構并按層次進行組織；（3）各模塊之間的關系盡可能簡單，在功能上相對獨立，順序、選擇和循環(huán)三種基本結構組成。結構化定理還進一步表明，任何一個復雜問題的程序設計都可以用順序、選擇和循環(huán)3種基本結構組成；5結構化程序設計的思想-2（4）并且它們都具有以下特點的：只有一個入口，只有一個出口，結構中無死循環(huán)，程序中3種基本結構之間形成順序執(zhí)行關系。其模塊化實現(xiàn)的具體方法是使用子程序。（5）在程序設計時應采用自頂向下、逐步細化的實施方法。6結構化程序設計的原則使用程序設計語言中的順序、選擇、循環(huán)有限的控制結構表示程序的控制邏輯；選用的控制結構只允許有一個入口和一個出口；復雜結構的程序設計時，僅用嵌套的基本控制結構進行組合嵌套來實現(xiàn)語言中沒有的控制結構，可用一段等價的程序段模擬，但要求該程序段在整個系統(tǒng)中應前后一致；嚴格控制goto語句的使用7結構化程序設計的步驟-1需求分析：需求分析是程序設計中必不可少的環(huán)節(jié)。分析以及該階段要解決什么問題，理解和表達用戶對程序功能的需求，明確程序的總任務。系統(tǒng)設計：這一部分可以分為兩步：一是總體設計，即按照程序的要求，把總任務分解成為一些功能相對獨立的子任務，最終達到每個子目標只專門完成某一單一的邏輯功能；二是模塊設計，即按照各獨立的子目標，給出其算法。算法和程序實現(xiàn)：算法要做到易讀、易動，自身必須具有良好的結構，而良好的結構是指僅用順序、分支和循環(huán)三種基本結構組合而成的。確定算法后，用特定的計算機語言將算法編制出來。8結構化程序設計的步驟-2調試運行：程序編好之后，難免會出現(xiàn)這樣那樣的錯誤，此時應認真檢查程序，找出錯誤加以改正，主要是排除語法錯誤邏輯錯誤編寫程序使用與維護的文檔：程序功能介紹、使用說明、參數(shù)含義9N-S圖根據(jù)程序的模塊結構圖和各模塊功能的詳細說明，程序的模塊結構圖確定了程序要“做什么”，接下來就要按算法編出程序。N-S圖尤其迎合結構化程序設計思想。不使用流線，即不允許流程任意轉移，而只能從上到下順序進行。這樣避免了流程轉來轉去而影響流程思路的理解；10N—S圖主要特點采用三種基本結構作為構造算法的基本單元:順序結構:按照先后順序執(zhí)行的，A模塊先于B模塊執(zhí)行，A與B模塊之間是順序關系選擇結構：程序按照給定的條件進行分析、比較和判斷，并根據(jù)判斷后的不同情況進行不同的處理循環(huán)結構：對同一個程序段重復執(zhí)行若干次，被重復執(zhí)行的部分成為循環(huán)體。循環(huán)結構就是根據(jù)給定條件成立與否，來決定是否執(zhí)行循環(huán)體11順序結構12選擇結構循環(huán)結構

13對含“中斷”語句的處理14對含“繼續(xù)”語句的處理15非結構化程序到結構化程序的轉化-1重復編碼法16條件復合技術非結構化程序到結構化程序的轉化-217K=0;L=0;T=0;redo:cin>>a;if(a==0)gotoprint;if(a>0)gotoupdate;L++;gotoredo;update:k++;T=T+a;if(T<=1000)gotoredo;print:cout<<k<<““<<L<<““<<T<<endl;18K=0;L=0;T=0;redo:cin>>a;While(T<=1000&&a!=0){ if(a>0){T=T+a;k++;}else{L++;}cin>>a;}print:cout<<k<<““<<L<<““<<T<<endl;非結構化程序到結構化程序的轉化-3布爾標志技術：這種方法一般用于將含有循環(huán)的非結構化程序轉化為結構化程序，常在循環(huán)中引進一個布爾量—“標志”，該布爾量在循環(huán)之前先被初始化，在程序段中利用對它的重新賦值來達到控制循環(huán)執(zhí)行的目的。19while(P){if(q)gotoL1;}L1:…….boolflag=true;while(P&&flag){if(q){flag=false;}}結構化程序的正確性驗證所謂一段程序是正確的，是指這段程序能準確無誤地完成編寫者所期望賦予它的功能。或者說，對任何一組允許的輸入信息，程序執(zhí)行后能得到一組和這組輸入信息相對應的正確的輸出信息一般來說，程序中含有錯誤是很難避免的錯誤可能有：（1）設計時的錯誤；（2）程序編寫時的錯誤；（3）運行時的錯誤等;1983年IEEE提出的軟件工程術語中給軟件測試下的定義是：“使用人工或者自動手段來運行或測定某個系統(tǒng)的過程，其目的在于檢驗它是否滿足規(guī)定的需求或是弄清預期結果與實際結果之間的差別。”20正確性證明的發(fā)展21程序正確性證明方法通過將任何一個程序用一系列邏輯斷言聯(lián)系在一起輸入斷言(Entryassertion)：滿足程序的輸入條件，Φ(x)指出輸入變量x的定義域，也即輸入變量應滿足的條件。輸出斷言(Exitassertion)：程序的運行結果，Ψ(x,z)指出輸出變量z和輸入變量x之間應滿足的關系。一段程序的正確性(Correctness)是指給定一個輸入斷言以及程序的程序函數(shù)，能夠導出程序的輸出斷言。22參考資料：/~raw/cps206/ProgramCorrectness.htm程序正確性定義嚴格意義上的程序正確性定義分為：部分正確性、終止性和完全正確性。假定給定一個程序P,謂詞Φ(x)為輸入斷言，Ψ(x,z)為輸出斷言。(1)若對每一個使Φ(x)為真，并且程序P計算終止,Ψ(x,P(x))為真，則稱程序P關于Φ和Ψ是部分正確的。(2)若對每一個使Φ(x)為真，程序P的計算都能終止，則稱程序P對Φ是終止的。(3)若對每一個使Φ(x)為真的輸入信息x，程序p的計算都能終止，并且Ψ(x,P(x))為真，則稱程序P關于Φ和Ψ是完全正確的。(3)等價于(1)和(2)的同時成立。23為了證明一個程序的完全正確性，通常采用的方法是分別證明該程序的部分正確性和終止性。部分正確并不保證程序可以終止，因此均需證明關于部分正確性證明的方法Floyd的不變式斷言法(*)Manna的子目標斷言法Hoare的公理化方法(*)關于終止性證明的方法Floyd的良序集方法(*)Manna等人的不動點方法Knuth的計數(shù)器方法關于完全正確性證明的方法Hoare的公理化方法的推廣（Manna，Pnueli）Burstall的間發(fā)斷言方法Dijkstra最弱前置謂詞變換方法以及強驗證方法程序正確性證明24quicksortFloyd部分正確性證明--流程圖方法25Floyd部分正確性證明-例：26S=0;J=0;while(J<N){ S=S+A(j); J++;}Floyd的不變式斷言法證明一個程序的部分正確性步驟(1)建立斷言前置斷言((x))：前提條件，初始狀態(tài)后置斷言((x,z))：最終結論，終止狀態(tài)滿足的條件循環(huán)不變式：在每次循環(huán)的前后均為真的謂詞(2)建立檢驗條件檢驗條件：程序運行通過該通路時應滿足的條件(3)證明檢驗條件適合對象：程序流程圖i(x,y)Ri(x,y)i(x,ri(x,y))輸入斷言輸出斷言y：一組中間變量x：輸入變量xy：蘊含符ri(x,y)：通過該通路后y的值通過此路徑的條件27實例設x1,x2是正整數(shù)，求他們的最大公約數(shù)z=gcd(x1,x2)。我們知道，對于任意正整數(shù)y1,y2，有下列關系：(1)若y1>y2，gcd(y1,y2)=gcd(y1-y2,y2)(2)若y2>y1，gcd(y1,y2)=gcd(y1,y2-y1)(3)若y1=y2，gcd(y1,y2)=y1=y2(x1,x2)(y1,y2)y1-y2y1y2-y1y2

A

…(x)

B

…P(x,y)y1zGC

…

(x,z)DETrueFalse

False

True28開始y1=y2y1>y2結束29y1=x1;y2=x2;z=1;while(y1>=0&&y2>=0){If(y1==y2){z=y1;}elsif(y1>y2){y1=y1-y2;}else{y2=y2-y1;}}設x1,x2是正整數(shù)，求他們的最大公約數(shù)z=gcd(x1,x2)。我們知道，對于任意正整數(shù)y1,y2，有下列關系：(x1,x2)(y1,y2)y1-y2y1y2-y1y2

A

…(x)

B

…P(x,y)y1zGC

…

(x,z)DETrueFalse

False

True開始y1=y2y1>y2結束(x)：x1>0x2>0

(x,z)：z=gcd(x1,x2)

在B點建立不變式斷言P(x,y)：x1>0x2>0y1>0y2>0gcd(y1,y2)=gcd(x1,x2)(1)建立斷言30(x1,x2)(y1,y2)y1-y2y1y2-y1y2

A

…(x)

B

…P(x,y)y1zGC

…

(x,z)DETrueFalse

False

True開始y1=y2y1>y2結束通路1：A-->B;通路2：B-->D-->B通路3：B-->E-->B;通路4：B-->G-->C為每一條通路，建立檢驗條件.通路1：A-->B無條件，即R1(x,y)恒真，結果y取值為x。

所以檢驗條件為：(x)P(x,y)即[x1>0x2>0]x1>0x2>0gcd(x1,x2)=gcd(x1,x2)(2)建立檢驗條件-131(x1,x2)(y1,y2)y1-y2y1y2-y1y2

A

…(x)

B

…P(x,y)y1zGC

…

(x,z)DETrueFalse

False

True開始y1=y2y1>y2結束通路條件(2)建立檢驗條件-2通路2：B-->D-->BR2(x,y)=[y1y2y1>y2]r2(x,y)=(y1-y2,y2)輸入輸出斷言均為P(x,y)所以檢驗條件為：[P(x,y)y1y2y1>y2]P(x,y1-y2,y2)將斷言P(x,y)代入，即得

[x1>0x2>0y1>0y2>0gcd(y1,y2)=gcd(x1,x2)y1y2y1>y2][x1>0x2>0y1-y2>0y2>0gcd(y1-y2,y2)=gcd(x1,x2)]32(x1,x2)(y1,y2)y1-y2y1y2-y1y2

A

…(x)

B

…P(x,y)y1zGC

…

(x,z)DETrueFalse

False

True開始y1=y2y1>y2結束通路條件通路后的y值(2)建立檢驗條件-3通路3：B-->E-->B與通路2類似地，得到[P(x,y)y1y2y1y2]P(x,y1,y2-y1)通路4：B-->G-->C類似地，得到[P(x,y)y1=y2](x1,x2)33(x1,x2)(y1,y2)y1-y2y1y2-y1y2

A

…(x)

B

…P(x,y)y1zGC

…

(x,z)DETrueFalse

False

True開始y1=y2y1>y2結束(3)證明檢驗條件-1通路1：[x1>0x2>0]x1>0x2>0gcd(x1,x2)=gcd(x1,x2)通路2：

[x1>0x2>0y1>0y2>0gcd(y1,y2)=gcd(x1,x2)y1y2y1>y2][x1>0x2>0y1-y2>0y2>0gcd(y1-y2,y2)=gcd(x1,x2)]檢驗條件前項成立時，y1>y2為真，則y1-y2>0為真且gcd(y1-y2,y2)=gcd(y1,y2)=gcd(x1,x2)所以檢驗條件為真

34(3)證明檢驗條件-2通路3：

[P(x,y)y1y2y1y2]P(x,y1-y2,y2-y1)

y1<y2為真,則y1-y2<0為真,gcd(y1,y2-y1)=gcd(y1,y2)=gcd(x1,x2)所以檢驗條件為真

通路4：

[P(x,y)y1=y2](x1,x2)y1=y2,gcd(y1,y2)=y1=y2,所以檢驗條件為真35不變式斷言法實例-2對任一給定的自然數(shù)x，計算，即計算x的平方根取整1＋3＋…(2n+1)=(n+1)2y1=n;y3=2*y1+1；y2=(y1+1)2;找到一個n，使得以下公式成立n2<x<(n+1)2(0,0,1)->(y1,y2,y3)y2+y3->y2(y1+1,y3+2)->(y1,y3)y1->zAI(x)BP(x,y1,y2,y3)DCO(x,z)TF·開始結束y2<x36y1=0;y2=0;y3=1;cin>>x;while(true){ y2=y2+y3; if(y2<x){ y1++; y3=2*y1+1; }else{z=y1;break;}}37(0,0,1)->(y1,y2,y3)y2+y3->y2(y1+1,2*y1+1)->(y1,y3)y1->zAI(x)BP(x,y1,y2,y3)DCO(x,z)TF·開始結束y2<xy1=n;y3=2*y1+1；y2=(y1+1)2;輸入斷言：

(x):x>0輸出斷言：

(x,z):z2≤x<(z+1)2通路1：A-->B賦值語句，即R1(x,y)恒真，結果y1,y2,y3取值為0,0,1。

所以檢驗條件為：(x)P(x,y)即[y1>0

y2>0

y3>0]x1>0x2>0gcd(x1,x2)=gcd(x1,x2)38(0,0,1)->(y1,y2,y3)y2+y3->y2(y1+1,2*y1+1)->(y1,y3)y1->zA

(x)BP(x,y1,y2,y3)DCO(x,z)