《結(jié)構(gòu)化程序設(shè)計(jì)》課件

第4章結(jié)構(gòu)化程序設(shè)計(jì)4.1關(guān)于結(jié)構(gòu)程序設(shè)計(jì)的基本概念4.2結(jié)構(gòu)化程序和結(jié)構(gòu)定理4.3結(jié)構(gòu)化程序設(shè)計(jì)的判別4.4結(jié)構(gòu)化程序設(shè)計(jì)的步驟和原理4.5逐步求精的程序設(shè)計(jì)4.6非結(jié)構(gòu)化向結(jié)構(gòu)化的轉(zhuǎn)化4.7結(jié)構(gòu)化程序的正確性驗(yàn)證小結(jié)習(xí)題第4章結(jié)構(gòu)化程序設(shè)計(jì)4.1關(guān)于結(jié)構(gòu)程序設(shè)計(jì)的基本概念4.1關(guān)于結(jié)構(gòu)程序設(shè)計(jì)1.定義結(jié)構(gòu)程序設(shè)計(jì)是避免使用GOTO語(yǔ)句的一種程序設(shè)計(jì)結(jié)構(gòu)程序設(shè)計(jì)是自頂向下的程序設(shè)計(jì)是一種組織和編制程序的方法,利用它編制的程序易于理解和修改程序結(jié)構(gòu)化的一個(gè)主要功能是使得正確性證明容易實(shí)現(xiàn)允許在設(shè)計(jì)過(guò)程中的每一步驗(yàn)證其正確性,即自動(dòng)導(dǎo)致自我說(shuō)明與自我捍衛(wèi)的程序風(fēng)格是討論如何將任何大規(guī)模的復(fù)雜的流程圖程序轉(zhuǎn)換成一種標(biāo)準(zhǔn)形式,使得它們用幾種標(biāo)準(zhǔn)的控制結(jié)構(gòu),通過(guò)重復(fù)和嵌套來(lái)表示.4.1關(guān)于結(jié)構(gòu)程序設(shè)計(jì)1.定義結(jié)構(gòu)程序設(shè)計(jì)的綜合描述結(jié)構(gòu)程序設(shè)計(jì)的綜合描述:結(jié)構(gòu)程序設(shè)計(jì)是一種進(jìn)行程序設(shè)計(jì)的原則和方法，按照這種原則和方法設(shè)計(jì)出的程序的特點(diǎn)是：結(jié)構(gòu)清晰、易閱讀、易修改、易驗(yàn)證。結(jié)構(gòu)程序設(shè)計(jì)語(yǔ)言：按照結(jié)構(gòu)程序設(shè)計(jì)的要求設(shè)計(jì)出的程序設(shè)計(jì)語(yǔ)言稱為結(jié)構(gòu)程序設(shè)計(jì)語(yǔ)言。結(jié)構(gòu)化程序：利用結(jié)構(gòu)程序設(shè)計(jì)語(yǔ)言，或按照結(jié)構(gòu)程序設(shè)計(jì)的思想編制的程序稱為“結(jié)構(gòu)化程序”。結(jié)構(gòu)程序設(shè)計(jì)的綜合描述結(jié)構(gòu)程序設(shè)計(jì)的綜合描述:關(guān)于GOTO語(yǔ)句的問(wèn)題4.關(guān)于GOTO語(yǔ)句的問(wèn)題取消GOTO語(yǔ)句，即GOTO有害。理由：GOTO語(yǔ)句使程序的靜態(tài)結(jié)構(gòu)與它的動(dòng)態(tài)執(zhí)行之間有很大的差別。這樣使程序難閱讀、難查錯(cuò)。去掉GOTO語(yǔ)句可以直接從程序結(jié)構(gòu)上反映出程序運(yùn)行的過(guò)程，結(jié)構(gòu)清晰、便于查錯(cuò)、易驗(yàn)證。保留GOTO語(yǔ)句GOTO語(yǔ)句使用起來(lái)比較靈活，而且有些情況下能夠提高程序的效率，若一味地強(qiáng)調(diào)刪除GOTO語(yǔ)句，有些情形會(huì)使程序過(guò)于復(fù)雜，增加不必要的計(jì)算量。折中派（Knuth）不加限制地使用GOTO語(yǔ)句，特別往回跳的GOTO語(yǔ)句，會(huì)使程序結(jié)構(gòu)難以理解，這種情形應(yīng)盡量避免使用GOTO語(yǔ)句。為提高效率，同時(shí)又不破壞程序的良好結(jié)構(gòu)，有控制地使用GOTO語(yǔ)句是有必要的。關(guān)于GOTO語(yǔ)句的問(wèn)題4.關(guān)于GOTO語(yǔ)句的問(wèn)題結(jié)構(gòu)程序設(shè)計(jì)結(jié)論結(jié)論：結(jié)構(gòu)程序設(shè)計(jì)討論的是一種程序設(shè)計(jì)的方法和風(fēng)格。關(guān)注的焦點(diǎn)是得到的程序的結(jié)構(gòu)的好壞，而有無(wú)GOTO語(yǔ)句并不是一個(gè)程序結(jié)構(gòu)好壞的標(biāo)志。避免和限制使用GOTO語(yǔ)句是得到結(jié)構(gòu)化程序的一種手段，而不是我們的目的。結(jié)構(gòu)化程序設(shè)計(jì)既著眼于程序設(shè)計(jì)的思路清晰，又著眼于程序的結(jié)構(gòu)清晰。即通過(guò)結(jié)構(gòu)化的設(shè)計(jì)方法獲得結(jié)構(gòu)化產(chǎn)品結(jié)構(gòu)程序設(shè)計(jì)結(jié)論結(jié)論：4.2結(jié)構(gòu)化程序和結(jié)構(gòu)定理一、結(jié)構(gòu)化程序下面給結(jié)構(gòu)化程序下一個(gè)精確的定義.4.2結(jié)構(gòu)化程序和結(jié)構(gòu)定理一、結(jié)構(gòu)化程序流程圖程序流程圖程序的組成：函數(shù)節(jié)點(diǎn)、謂詞節(jié)點(diǎn)和匯點(diǎn)。函數(shù)節(jié)點(diǎn)：只有一條入口線和一條出口線，一般與賦值語(yǔ)句相對(duì)應(yīng)。謂詞節(jié)點(diǎn)：有一條入口線和兩條出口線，它不改變程序的數(shù)據(jù)項(xiàng)的值。匯點(diǎn)：有兩條入口線和一條出口線，它不執(zhí)行任何運(yùn)算，只起到收集出口線的作用。fp1.流程圖程序定義：一個(gè)用流程圖的形式表示出來(lái)的程序，稱為流程圖程序。流程圖程序流程圖程序的組成：函數(shù)節(jié)點(diǎn)、謂詞節(jié)點(diǎn)和匯點(diǎn)。fp1流程圖程序舉例流程圖程序舉例:pqgf流程圖程序舉例流程圖程序舉例:pqgf正規(guī)程序4.正規(guī)程序定義：滿足以下兩個(gè)條件的流程圖程序稱為正規(guī)程序。條件：具有一條入口線和一條出口線，且對(duì)每個(gè)節(jié)點(diǎn)，都有一條從入口線到出口線的通路通過(guò)該節(jié)點(diǎn)。例：下面兩個(gè)流程圖程序不是正規(guī)程序pfgpf正規(guī)程序4.正規(guī)程序pfgpf正規(guī)子程序3.正規(guī)子程序一個(gè)正規(guī)程序的某些部分仍然可以是正規(guī)程序,這些部分稱為正規(guī)子程序.正規(guī)子程序3.正規(guī)子程序基本程序4.基本程序定義：一個(gè)正規(guī)程序，如果不包含多余一個(gè)節(jié)點(diǎn)的正規(guī)子程序，稱為基本程序。即基本程序是一種不可再分解的正規(guī)程序。例：fgfghfgf基本程序4.基本程序fgfghfgf七種重要的基本程序函數(shù):序列:If-thenIf-then-elsefgfpfgpf七種重要的基本程序fgfpfgpf七種重要的基本程序while-do:Do-until:Do-while-do:pfpgfpg七種重要的基本程序while-do:pfpgfpg復(fù)合程序和結(jié)構(gòu)化程序5.復(fù)合程序若一個(gè)基本程序的函數(shù)節(jié)點(diǎn)用另外一個(gè)基本程序替換,所產(chǎn)生的正規(guī)程序稱為復(fù)合程序。6.結(jié)構(gòu)化程序由基本程序的一個(gè)固定的基集合（例如，序列、IF-THEN-ELSE、While-DO）構(gòu)造出的復(fù)合程序稱為結(jié)構(gòu)化程序。復(fù)合程序和結(jié)構(gòu)化程序5.復(fù)合程序二、結(jié)構(gòu)化定理1.程序函數(shù)已知一正規(guī)程序P，對(duì)于每個(gè)初始的數(shù)據(jù)狀態(tài)X，若程序是終止的，那么有確定的最終數(shù)據(jù)狀態(tài)Y。如果對(duì)于每一個(gè)給定的X，值Y是唯一的，那么所有的有序?qū)Φ募蟵（X，Y）}定義了一個(gè)函數(shù)，稱這個(gè)函數(shù)為程序P的程序函數(shù)，記為[P]。例：設(shè)程序P由三條語(yǔ)句組成：t:=x;x:=y;y:=t;對(duì)任意的X=(x,y,t),程序P的執(zhí)行結(jié)果Y=（y,x,x）因此，程序函數(shù)是{（x,y,t）,(y,x,x)}本質(zhì)：計(jì)算輸入和輸出的關(guān)系二、結(jié)構(gòu)化定理1.程序函數(shù)二、結(jié)構(gòu)化定理2.七種基本程序的程序函數(shù)[f]={(x,y)|y=f(x)}[f;g]={(x,y)|y=g·f(x)}[if-then]={(x,y)|p(x)y=f(x)|?p(x)y=x}[if-then-else]={(x,y)|p(x)y=f(x)|?p(x)y=g(x)}二、結(jié)構(gòu)化定理2.七種基本程序的程序函數(shù)二、結(jié)構(gòu)化定理[while-do]={(x,y)|k0((j:0<=j<k:p·fj(x))|?p·fk(x)y=fk(x))}[do-until]={(x,y)|k>0(j:1<=j<k)(

?p·fj(x)|p·fk(x)y=fk(x))}[dofwhilepdogod]={(x,y)|k0(

j:0<=j<k:p·f·(g·f)j(x))|?p·f·(g·f)k(x)y=f·(g·f)k(x))}2.七種基本程序的程序函數(shù)(續(xù))二、結(jié)構(gòu)化定理[while-do]={(x,y)|k二、結(jié)構(gòu)化定理1）對(duì)于序列程序可使用跟蹤表的方法計(jì)算[p]例：語(yǔ)句段：x:=x+y;y:=x-y;x:=x-y;解：假設(shè)變量x,y的初值為x0,y0,…有跟蹤表：語(yǔ)句xyx:=x+yx1=x0+y0y1=y0y:=x-yy2=x1–y1x2=x1x:=x-yX3=x2-y2y3=y2X3=x2-y2=x1-(x1-y1)=y1=y0Y3=y2=x1-y1=x0+y0–y0=x0[P]={((x,y),(y,x)}3.程序函數(shù)的計(jì)算二、結(jié)構(gòu)化定理1）對(duì)于序列程序可使用跟蹤表的方法計(jì)算[p]語(yǔ)二、結(jié)構(gòu)化定理練習(xí)：計(jì)算下列語(yǔ)句序列的程序函數(shù)：y:=a;y:=x*y+b;y:=x*y+c;y:=x*y+d3.程序函數(shù)的計(jì)算二、結(jié)構(gòu)化定理練習(xí)：計(jì)算下列語(yǔ)句序列的程序函數(shù)：3.程序二、結(jié)構(gòu)化定理2)無(wú)循環(huán)程序的程序函數(shù)首先：構(gòu)造有窮的執(zhí)行樹然后：對(duì)每條路徑寫出相應(yīng)的表達(dá)式例：pfhrgq3.程序函數(shù)的計(jì)算二、結(jié)構(gòu)化定理2)無(wú)循環(huán)程序的程序函數(shù)pfhrgq3.程序二、結(jié)構(gòu)化定理執(zhí)行樹：pfhrqghrgg[p]={(x,y)|p(x)

q

f(x)y=gf(x)|p(x)

q

f(x)

r

h

f(x)y=ghf(x)|p(x)

q

f(x)

r

h

f(x)y=hf(x)|p(x)

…|…3.程序函數(shù)的計(jì)算二、結(jié)構(gòu)化定理執(zhí)行樹：pfhrqghrgg[p]={(二、結(jié)構(gòu)化定理3)循環(huán)程序的程序函數(shù)g1g3p1p2p3g2g4g51g12g3p1g213p2p3g53g42執(zhí)行樹：3.程序函數(shù)的計(jì)算二、結(jié)構(gòu)化定理3)循環(huán)程序的程序函數(shù)g1g3p1p2p3g2代換后的執(zhí)行樹：g1g3p1g2p2p3g5g4f1f3f1f2f2f3f1={(x,y)|y=f2g1(x)}F2={(x,y)|p1g3(x)y=f1g2g3(x)|p1g3(x)y=f3g3(x)}F3={(x,y)|p2(x)

p3(x)y=f3g5(x)|p2(x)

p3(x)y=x|

p2(x)y=f2

g4(x)}代換后的執(zhí)行樹：g1g3p1g2p2p3g5g4f1f3f1二、結(jié)構(gòu)化定理5.程序的函數(shù)等價(jià)如果程序P1和程序P2有相同的程序函數(shù)，稱它們是函數(shù)等價(jià)的，或簡(jiǎn)稱是等價(jià)的。5.結(jié)構(gòu)化定理定理：任一正規(guī)程序都可以函數(shù)等價(jià)與一個(gè)由基集合{序列，if-then-else，while-do}產(chǎn)生的結(jié)構(gòu)化程序。二、結(jié)構(gòu)化定理5.程序的函數(shù)等價(jià)5.結(jié)構(gòu)化定理結(jié)構(gòu)化定理-證明證明：考察任一正規(guī)程序:

首先，從程序的入口處開始給程序的函數(shù)節(jié)點(diǎn)和謂詞節(jié)點(diǎn)編號(hào)。編號(hào)為1，2，3，…，n（若入口處是匯點(diǎn)，那么宴會(huì)點(diǎn)的出口線繼續(xù)考察，直到找到第一個(gè)函數(shù)節(jié)點(diǎn)或謂詞節(jié)點(diǎn)）。同時(shí)將每一個(gè)函數(shù)節(jié)點(diǎn)及謂詞節(jié)點(diǎn)的出口線用它后面的節(jié)點(diǎn)的編號(hào)進(jìn)行編號(hào)。如果它后面沒(méi)有函數(shù)節(jié)點(diǎn)或謂詞節(jié)點(diǎn)，即該節(jié)點(diǎn)的出口線直接或通過(guò)匯點(diǎn)與程序的出口相連時(shí)，出口線的編號(hào)為0。peqh123400結(jié)構(gòu)化定理-證明證明：考察任一正規(guī)程序:peqh123400結(jié)構(gòu)化定理--證明對(duì)每一個(gè)編號(hào)為i，出口線編號(hào)為j、k的謂詞節(jié)點(diǎn)p，構(gòu)造一個(gè)新的IF-THEN-ELSE程序gi，如圖：h其次，對(duì)原程序種的每一個(gè)編號(hào)為i，出口線編號(hào)為J的函數(shù)節(jié)點(diǎn)h，構(gòu)造一個(gè)新的序列程序gi，如圖：ijhL:=jgi=pgi=pL:=jL:=kjik結(jié)構(gòu)化定理--證明對(duì)每一個(gè)編號(hào)為i，出口線編號(hào)為j、k的謂詞結(jié)構(gòu)化定理--證明最后，利用已經(jīng)得到的一些gi（I=1,2,3,…,n），按下圖形式構(gòu)造一個(gè)while-do循環(huán)。這個(gè)循環(huán)體是一個(gè)對(duì)L從1到n進(jìn)行測(cè)試的嵌套的IF-THEN-ELSE程序（最內(nèi)層的I表示恒等函數(shù)）：L:=1L>0L=1?g1L=2?g2L=n-1?gn-1L=n?gn???I???F=結(jié)構(gòu)化定理--證明最后，利用已經(jīng)得到的一些gi（I=1,2,結(jié)構(gòu)化定理--證明結(jié)論:顯然,上面程序的功能和原程序的功能是相同的,因而它和原程序是函數(shù)等價(jià)的。而且，該程序是由一個(gè)固定的基集合{序列，IF-THEN-ELSE，WHILE-DO}產(chǎn)生的結(jié)構(gòu)化程序，從而定理得證。結(jié)構(gòu)化定理--證明結(jié)論:結(jié)構(gòu)化定理舉例例：考察如下的流程圖程序：peqh123400第一步：編號(hào)，結(jié)果如上圖。結(jié)構(gòu)化定理舉例例：考察如下的流程圖程序：peqh123400結(jié)構(gòu)化定理舉例第二步：重新構(gòu)造函數(shù)節(jié)點(diǎn)和謂詞節(jié)點(diǎn)eL:=0g2=g1=pL:=2L:=3g3=qL:=0L:=4hL:=1g4=結(jié)構(gòu)化定理舉例第二步：重新構(gòu)造函數(shù)節(jié)點(diǎn)和謂詞節(jié)點(diǎn)eL:=0g結(jié)構(gòu)化定理舉例第三步：用IF-THEN-ELSE和WHILE-DO重新構(gòu)造程序：L:=1L>0L=1?L=2?pL:=2L:=3eL:=0L=3?qL:=0L:=4L=4?hL:=1I結(jié)構(gòu)化定理舉例第三步：用IF-THEN-ELSE和WHILE結(jié)構(gòu)化定理舉例第四步：化簡(jiǎn)：上面得到的結(jié)構(gòu)化程序比較龐大，且效率不高，還可以進(jìn)一步改進(jìn)，消除一些多余的對(duì)L的測(cè)試和賦值?；?jiǎn)的基本思想：對(duì)于某些j>0，如果gj中不包含賦值語(yǔ)句L:=j，則可以用gj代替所有的賦值L:=j。這樣代替后，由于j不再賦值給L，因而測(cè)試L=j可以從IF-THEN-ELSE結(jié)構(gòu)中去掉。這種替換直到以下情況出現(xiàn)為止：除了L:=0以外，所有給L賦值的語(yǔ)句均被消除；每個(gè)余下的gi’中都包含由相應(yīng)賦值L:=I（gi’是gi經(jīng)過(guò)一些替換以后得到的復(fù)合程序）例：結(jié)構(gòu)化定理舉例第四步：化簡(jiǎn)：結(jié)構(gòu)化定理轉(zhuǎn)換的化簡(jiǎn)用g4代替所有的L:=4的賦值語(yǔ)句，并刪除L=4的測(cè)試L:=1L>0L=1?L=2?pL:=2L:=3eL:=0L=3?qL:=0hL:=1I結(jié)構(gòu)化定理轉(zhuǎn)換的化簡(jiǎn)用g4代替所有的L:=4的賦值語(yǔ)句，并刪結(jié)構(gòu)化定理轉(zhuǎn)換的化簡(jiǎn)（續(xù)）用當(dāng)前的g3’替換L:=3的賦值語(yǔ)句，并刪除L=3的測(cè)試L:=1L>0L=1?L=2?pL:=2eL:=0qL:=0hL:=1I結(jié)構(gòu)化定理轉(zhuǎn)換的化簡(jiǎn)（續(xù)）用當(dāng)前的g3’替換L:=3的賦值語(yǔ)結(jié)構(gòu)化定理轉(zhuǎn)換的化簡(jiǎn)（續(xù)）用g2’替換L:=2的賦值。L:=1L>0L=1?pqL:=0hL:=1IeL:=0結(jié)構(gòu)化定理轉(zhuǎn)換的化簡(jiǎn)（續(xù)）用g2’替換L:=2的賦值。L:=結(jié)構(gòu)化定理轉(zhuǎn)換的化簡(jiǎn)（續(xù)）刪除循環(huán)中L:=1的賦值，因?yàn)槌薒:=0的賦值回改變L的取值外，都不會(huì)改變L的取值，進(jìn)而L=1的測(cè)試也可以刪除。L:=1L>0pqL:=0heL:=0結(jié)構(gòu)化定理轉(zhuǎn)換的化簡(jiǎn)（續(xù)）刪除循環(huán)中L:=1的賦值，因?yàn)槌私Y(jié)構(gòu)化程序的特點(diǎn)具有層次化結(jié)構(gòu)的程序，有很大的優(yōu)點(diǎn)：書寫時(shí)，自頂向下，逐步求精閱讀時(shí)，自底向上，逐步抽象驗(yàn)證時(shí)，分層逐步驗(yàn)證結(jié)構(gòu)化程序的特點(diǎn)具有層次化結(jié)構(gòu)的程序，有很大的優(yōu)點(diǎn)：4.3結(jié)構(gòu)化程序設(shè)計(jì)的判別一個(gè)軟件是否滿足結(jié)構(gòu)化標(biāo)準(zhǔn)可以用Mccabe關(guān)于軟件復(fù)雜性度量的理論判斷有關(guān)的定理和推論任何非結(jié)構(gòu)化的程序是由下列4中情況引起從循環(huán)中轉(zhuǎn)出從循環(huán)外轉(zhuǎn)入從判定內(nèi)轉(zhuǎn)出從判定外轉(zhuǎn)入4.3結(jié)構(gòu)化程序設(shè)計(jì)的判別一個(gè)軟件是否滿足結(jié)構(gòu)化標(biāo)準(zhǔn)可以用4.3結(jié)構(gòu)化程序設(shè)計(jì)的判別(續(xù))有關(guān)的定理和推論推論1：一個(gè)結(jié)構(gòu)化程序可以按照不轉(zhuǎn)入（出）循環(huán)或判定的原則編寫。程序控制結(jié)構(gòu)的表示用有向圖表示。每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于順序處理的代碼塊，弧線對(duì)應(yīng)程序中的轉(zhuǎn)移，箭頭代表轉(zhuǎn)移方向。假設(shè)只有一個(gè)入口和一個(gè)出口。如果從出口節(jié)點(diǎn)轉(zhuǎn)回到入口節(jié)點(diǎn)，則稱圖是強(qiáng)連通的。abcdef4.3結(jié)構(gòu)化程序設(shè)計(jì)的判別(續(xù))有關(guān)的定理和推論abcde4.3結(jié)構(gòu)化程序設(shè)計(jì)的判別(續(xù))定理1：在一個(gè)強(qiáng)連同圖G中，線性無(wú)關(guān)的環(huán)路數(shù)最大值V(G)＝e－n＋1，其中e是弧數(shù)，n是節(jié)點(diǎn)數(shù)。例如：V(G)=10-6+1=5V(G)的另一種計(jì)算方法V(G)＝

i＝1toQ(Ti－1)+p+1,

其中，p為程序中條件轉(zhuǎn)移語(yǔ)句的個(gè)數(shù)，Q是分支情況語(yǔ)句，Ti是第i個(gè)分情況語(yǔ)句的情況總數(shù)。abcdef4.3結(jié)構(gòu)化程序設(shè)計(jì)的判別(續(xù))定理1：在一個(gè)強(qiáng)連同圖G中4.3結(jié)構(gòu)化程序設(shè)計(jì)的判別(續(xù))推論2：一個(gè)結(jié)構(gòu)化程序課退化稱成最大環(huán)路數(shù)為1的程序。這種退化是對(duì)程序的逐漸抽象，形成只有一個(gè)入口和一個(gè)出口節(jié)點(diǎn)的子圖的過(guò)程。定義1：正規(guī)子圖是僅含順序、選擇和循環(huán)的子圖。假設(shè)m是有一個(gè)入口節(jié)點(diǎn)和一個(gè)出口節(jié)點(diǎn)的正規(guī)子圖，ev為程序的本質(zhì)復(fù)雜性，則ev＝V(G)－m，將反映程序結(jié)構(gòu)的復(fù)雜程度。vv越大，程序的結(jié)構(gòu)化程度越差。顯然，1<=ev<=V(G)推論3：一個(gè)結(jié)構(gòu)化程序的本質(zhì)復(fù)雜性ev為1。4.3結(jié)構(gòu)化程序設(shè)計(jì)的判別(續(xù))推論2：一個(gè)結(jié)構(gòu)化程序課退4.3結(jié)構(gòu)化程序設(shè)計(jì)的判別(續(xù))判別途徑判別一個(gè)程序是否滿足結(jié)構(gòu)化程序設(shè)計(jì)標(biāo)準(zhǔn)的要求：是否有一個(gè)入口和出口節(jié)點(diǎn)是否有轉(zhuǎn)入循環(huán)或判定的情形計(jì)算程序的本質(zhì)復(fù)雜性檢驗(yàn)結(jié)構(gòu)化程序設(shè)計(jì)標(biāo)準(zhǔn)的其他要求。4.3結(jié)構(gòu)化程序設(shè)計(jì)的判別(續(xù))判別途徑4.4結(jié)構(gòu)化程序設(shè)計(jì)的步驟和原理結(jié)構(gòu)化程序設(shè)計(jì)的步驟：Step1：需求分析Step2：系統(tǒng)設(shè)計(jì)：總體設(shè)計(jì)和模塊設(shè)計(jì)Step3：算法和程序?qū)崿F(xiàn)；Step4：驗(yàn)證和測(cè)試Step5：運(yùn)行程序和整理文檔4.4結(jié)構(gòu)化程序設(shè)計(jì)的步驟和原理結(jié)構(gòu)化程序設(shè)計(jì)的步驟：4.4結(jié)構(gòu)化程序設(shè)計(jì)的步驟和原理結(jié)構(gòu)化程序設(shè)計(jì)的原理抽象分解模塊化局部化和信息隱蔽一致性完整性：要求一個(gè)程序系統(tǒng)不丟失任何重要成分，系統(tǒng)無(wú)缺省且獨(dú)立。獨(dú)立意義的完整性指一個(gè)系統(tǒng)相對(duì)完備，除基本的運(yùn)行環(huán)境外，不涉及其他系統(tǒng)?？沈?yàn)證性：指分解系統(tǒng)和構(gòu)造模塊時(shí)應(yīng)使各模塊和整個(gè)系統(tǒng)都能方便測(cè)試，從而也利于維護(hù)和修改4.4結(jié)構(gòu)化程序設(shè)計(jì)的步驟和原理結(jié)構(gòu)化程序設(shè)計(jì)的原理4.5逐步求精的設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)規(guī)則不是使程序?qū)懲曛笤賮?lái)驗(yàn)證程序的正確性，而是在算法逐步細(xì)化為程序的過(guò)程中，確保每一步細(xì)化都正確地實(shí)現(xiàn)前一步的要求，因此逐步求精既是一種程序設(shè)計(jì)方法，同時(shí)也是驗(yàn)證程序正確性的方法。逐步求精的思想：先全局后局部，先整體后細(xì)節(jié)，先抽象后具體的過(guò)程組織人們的思維活動(dòng)，使得編寫的程序結(jié)構(gòu)清晰，容易閱讀，易修改。同時(shí)它可以實(shí)現(xiàn)邊設(shè)計(jì)邊驗(yàn)證的方式簡(jiǎn)化對(duì)程序的正確性驗(yàn)證過(guò)程。是一種自頂向下的程序設(shè)計(jì)方法舉例：4.5逐步求精的設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)規(guī)則不是使程序?qū)懲曛?.5逐步求精的設(shè)計(jì)方法（續(xù)）例：編寫一個(gè)程序，打印前n個(gè)素?cái)?shù)(n為給定的正整數(shù))Voidprime(intn){inti,x;x=1;for(i=1;i<n;i++){x=“下一個(gè)素?cái)?shù)”；printf(“%d”,x);}}對(duì)語(yǔ)句x=“下一個(gè)素?cái)?shù)”求精intprim；prim＝false；Do{ x++;}while(isprime(x))4.5逐步求精的設(shè)計(jì)方法（續(xù)）例：編寫一個(gè)程序，打印前n個(gè)4.5逐步求精的設(shè)計(jì)方法（續(xù)）對(duì)函數(shù)isprime(x)求精k=2;Prim=true;While(k<=lim&&prim){Prim=“x不能被k整除”;k++;}Lim的確定是k的上界，即lim＝x－1；“x不能被k整除”的求精xmodk<>0；Voidprime(intn){inti,x;x=1;for(i=1;i<n;i++){do{ x++;}while(isprime(x))printf(“%d”,x);}}4.5逐步求精的設(shè)計(jì)方法（續(xù)）對(duì)函數(shù)isprime(x)求4.5逐步求精的設(shè)計(jì)方法（續(xù)）intisprime(intx){k=2;Prim=true;While(k<=x-1&&prim){Prim=(xmodk)<>0;k++;}returnprim;}優(yōu)化：關(guān)于x++,x+=2;關(guān)于上限的確定：x-1是最大的上限；4.5逐步求精的設(shè)計(jì)方法（續(xù)）intisprime(in4.6非結(jié)構(gòu)化向結(jié)構(gòu)化的轉(zhuǎn)化法1：代碼復(fù)制法123412344方法2：布爾標(biāo)志法引入布爾變量,例：方法3：結(jié)構(gòu)化定理4.6非結(jié)構(gòu)化向結(jié)構(gòu)化的轉(zhuǎn)化法1：代碼復(fù)制法12341234.6非結(jié)構(gòu)化向結(jié)構(gòu)化的轉(zhuǎn)化(續(xù))例WhilePdoBegin…ifqthengotoL1A;B;EndL1:…轉(zhuǎn)化為：Bool:=True;WhilePandBooldoBegin…ifqthengotoBool:=falseelsebeginA;B;endEnd…4.6非結(jié)構(gòu)化向結(jié)構(gòu)化的轉(zhuǎn)化(續(xù))例轉(zhuǎn)化為：4.7結(jié)構(gòu)化程序的正確性證明－正確性定理1.正確性定理假設(shè)已知程序P和一個(gè)預(yù)期函數(shù)f，若有f＝[P]稱程序P正確地實(shí)現(xiàn)了函數(shù)f，或者說(shuō)程序P是正確的。根據(jù)結(jié)構(gòu)化定理，任何結(jié)構(gòu)化程序都可以用序列、條件和循環(huán)3種結(jié)構(gòu)表示出來(lái)。直接驗(yàn)證循環(huán)程序的正確性很麻煩，希望用序列和分支結(jié)構(gòu)表示循環(huán)結(jié)構(gòu)，以簡(jiǎn)化循環(huán)的正確性證明。4.7結(jié)構(gòu)化程序的正確性證明－正確性定理1.正確性定理4.7結(jié)構(gòu)化程序的正確性證明－引理引理1:已知函數(shù)f和循環(huán)程序P：whilepdogod，

則f＝[whilepdogod]的充要條件是：對(duì)所有xD(f)，程序P終止，且f＝[ifptheng;ffi]證明：（1）必要性。假設(shè)f＝[whilepdogod]，那么程序P終止是必然的，否則等式不成立。進(jìn)一步，考察程序

ifptheng；whilepdogodfi

顯然，它和程序P是等價(jià)的，因而有，

[whilepdogod]=[ifptheng;whilepdogodfi]

又已知f＝[whilepdogod]，用f替換程序P得，

f＝[ifptheng;ffi][ok]4.7結(jié)構(gòu)化程序的正確性證明－引理引理1:已知函數(shù)f和4.7結(jié)構(gòu)化程序的正確性證明－引理(續(xù))(2)充分性。假設(shè)程序P終止，且f＝[ifptheng;ffi]

考察下面一組等價(jià)的程序（逐次使用if-then替換f得到的）：

ifptheng;ffi

ifptheng;ifptheng;ffifi

……ifptheng;ifptheng;…;(ifptheng;ffi)fi…fifi

由于程序P終止，則這一組程序定是有限的，謂詞p在執(zhí)行有限次以后一定取值為false，這時(shí)的if-then語(yǔ)句等價(jià)于恒等函數(shù)I，即最后的程序?yàn)?/p>

ifptheng;ifptheng;…;Ifi…fifi

顯然，該程序等價(jià)于whilepdogod

于是，f＝[ifptheng;ffi]【ok】4.7結(jié)構(gòu)化程序的正確性證明－引理(續(xù))(2)充分性。4.7結(jié)構(gòu)化程序的正確性證明－引理(續(xù))引理2：已知函數(shù)f和程序P：doguntilp，

則f=[doguntilp]的充分必要條件是：對(duì)所有的xD(f)，程序終止，且f＝[g；ifpthenf;fi]引理3：已知函數(shù)f和程序P：do1gwhilepdo2hod

則f=[do1gwhilepdo2hod]的充要條件是：對(duì)所有的xD(f)，程序終止，且f=[g；ifpthenh;f;fi]可知，循環(huán)程序的驗(yàn)證可以通過(guò)將循環(huán)化為遞歸的方法轉(zhuǎn)換為終止性和由序列和條件組成的無(wú)循環(huán)程序的驗(yàn)證。4.7結(jié)構(gòu)化程序的正確性證明－引理(續(xù))引理2：已知函數(shù)4.7結(jié)構(gòu)化程序的正確性證明－定理1定理1：已知預(yù)期函數(shù)f和基本程序P，則f=[P]的充要條件是：對(duì)所有的xD(f)，程序終止，且對(duì)不同的基本程序，函數(shù)f分別滿足下列關(guān)系：情形a：對(duì)序列程序，即P＝g;h，有

f={(x,y)|y=h?g(x)}情形b：對(duì)if-then程序，即P=ifpthengfi，有

f={(x,y)|p(x)

y=g(x)|p(x)

y=x}情形c：對(duì)if-then-else程序，即P=ifpthengelsehfi，有f={(x,y)|(p(x)

y=g(x)|p(x)

y=h(x))}4.7結(jié)構(gòu)化程序的正確性證明－定理1定理1：已知預(yù)期函數(shù)f4.7結(jié)構(gòu)化程序的正確性證明－定理1(續(xù))情形d：對(duì)while-do程序，即P=whilepdogod,有

f={(x,y)|(p(x)

y=f?g(x)|p(x)

y=x)}情形e：對(duì)do-until程序，即P=doguntilpod,有

f={(x,y)|(p?g(x)

y=g(x)|p?g(x)

y=f?g(x))}情形f：對(duì)do-while-do程序，即P=do1gwhilepdo2hod,有

f={(x,y)|(p?g(x)

y=f?h?g(x)|p?g(x)

y=g(x))}證明略。4.7結(jié)構(gòu)化程序的正確性證明－定理1(續(xù))情形d：對(duì)whi4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法1一個(gè)終止的循環(huán)程序的正確性證明可以轉(zhuǎn)化為序列和條件程序的正確性證明；跟蹤表和條件分離規(guī)則是序列和條件程序證明的基本方法；4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法1一個(gè)終止的循環(huán)程序4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法2一、跟蹤表例：有序列程序段：x:=x+y;y:=x-y;x:=x-y;解：假設(shè)變量x,y的初值為x0,y0,…有跟蹤表：語(yǔ)句xyx:=x+yx1=x0+y0y1=y0y:=x-yy2=x1–y1x2=x1x:=x-yX3=x2-y2y3=y2X3=x2-y2=x1-(x1-y1)=y1=y0Y3=y2=x1-y1=x0+y0–y0=x04.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法2一、跟蹤表語(yǔ)句xy4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法3二、分離規(guī)則條件語(yǔ)句ifpthengelsehfi的程序函數(shù)為

（pg|

ph）

為驗(yàn)證條件語(yǔ)句的正確性，需要比較預(yù)期函數(shù)f和上面條件規(guī)則是否相等。1.復(fù)合條件規(guī)則的化簡(jiǎn) 如果g，h是條件語(yǔ)句，就會(huì)引入復(fù)合條件規(guī)則，為比較復(fù)合條件規(guī)則，需要首先對(duì)它進(jìn)行化簡(jiǎn)。例如，4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法3二、分離規(guī)則4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法4(p1(q11r11|q12r12)|p2(q21r21|q22r22))形式上展開為，p1

q11r11|p1

q12r12|p2

q21r21|p2

q22r22一般情況下，這樣展開可能是不成立的。例如，當(dāng)p1為真，q11和q12為假，而p2為真，q21，q22有一個(gè)為真時(shí)，展開式有意義，而原復(fù)合規(guī)則無(wú)意義。但是如果p1和p2是分離的，即p1p2為假時(shí)，上述展開始終是成立的。4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法4(p1(q114.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法5如果一個(gè)條件規(guī)則的所有謂詞都是分離的，稱它為分離規(guī)則。例如，

(x>0(y>0z:=x*y|y<0z:=-x*y)

x<0(y>0z:=-x*y|y<0z:=x*y))

其復(fù)合條件規(guī)則是分離的，因而展開為，

(x>0y>0z:=x*y|

x>0

y<0z:=-x*y|

x<0

y>0z:=-x*y|

x<0

y<0z:=x*y)4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法5如果一個(gè)條件規(guī)則的4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法62.將條件規(guī)則化為分離規(guī)則原因：在化簡(jiǎn)和比較條件規(guī)則時(shí)，分離條件規(guī)則比一般的條件規(guī)則使用方便；一般條件規(guī)則的順序是不能交換的，而分離的條件規(guī)則是可以交換的。因而，在討論程序的正確性時(shí)，總是首先將條件規(guī)則化為分離規(guī)則4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法62.將條件規(guī)則化4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法72.將條件規(guī)則化為分離規(guī)則轉(zhuǎn)換方法對(duì)任意的條件規(guī)則(p1r1|p2r2|p3r3|…)

可轉(zhuǎn)化為

(p1r1|

p1

p2r2|

p1

p2p3r3|…)例如，條件規(guī)則

(x>0z:=max(x,y|y>0z:=min(x,y))

可以表示為，

(x>0z:=max(x,y)|x0y>0z:=min(x,y)),或

(x>0(x>yz:=x|x<yz:=y)|

x0y>0(x>yz:=y)|x<yz:=x)),進(jìn)一步展開

(x>0

x>y

z:=x|x>0

x<yz:=y|

x0y>0

x>yz:=y|x0y>0

x<yz:=x)4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法72.將條件規(guī)則化4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法83.條件語(yǔ)句的正確性證明 假設(shè)某一條件語(yǔ)句的程序函數(shù)是分離規(guī)則

(p1r1|p2r2|p3r3)

預(yù)期函數(shù)是f(x)。為證明條件語(yǔ)句的正確性，需證明兩點(diǎn)：

（1）f(x)的定義域和分離規(guī)則的定義域相同 （2）利用分離規(guī)則的謂詞將f(x)的定義域分解，并且有以下關(guān)系成立

p1(x)r1(x)=f(x) p2(x)r2(x)=f(x) p3(x)r3(x)=f(x)

另外，當(dāng)f是以條件規(guī)則的形式給出時(shí)，如(q1s1|q2s2),這時(shí)要證明，4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法83.條件語(yǔ)句的正4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法93.條件語(yǔ)句的正確性證明(續(xù))（1）兩個(gè)分離規(guī)則的定義域相同的，即p1(x)p2(x)p3(x)=q1(x)q2(x)（2）兩個(gè)分離規(guī)則中的謂詞成對(duì)合取后，相應(yīng)的結(jié)果是相同的，即

p1(x)

q1(x)

r1(x)=s1(x) p1(x)

q2(x)r1(x)=s2(x) …… p3(x)

q1(x)r3(x)=s1(x)

p3(x)

q2(x)r3(x)=s2(x)

4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法93.條件語(yǔ)句的正4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法10例1：已知預(yù)期函數(shù)f=(x:=-x)，程序P為

ifx>0thenx:=x-2*xelsex:=x+2*abs(x)fi

證明P是正確的，即[P]=f(假設(shè)x是整數(shù))。證明:f和P的定義域均為整數(shù)，因而相同，

又P的程序函數(shù)為

x>0

x:=x-2*x|x<0

x:=x+2*abs(x)

它是分離規(guī)則，且

x>0(x:=x-2*x)=(x:=-x)

x<0(x:=x+2*abs(x)=(x:=x+2*(-x))=(x:=-x)

因而是正確的。4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法10例1：已知預(yù)期函4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法11例2：已知預(yù)期函數(shù)f是(x,y,a:=0,a*x+y,a)(x,y,a是整數(shù)，且x>0)。程序P是

whilex<>0dox,y:=x-1,y+aod

證明程序P是正確的。證明：

由于已知x>0,且每循環(huán)一次x減1，因而通過(guò)有限次循環(huán)后，總有x=0,即對(duì)任何程序是終止的。另，

尚需證明：f=(p(x)y=f?g(x)|p(x)y=x)

對(duì)程序P來(lái)說(shuō)，p(x)為x<>0，且已知x>0,因而

p(x)=(x>0),p(x)=(x=0)

函數(shù)的復(fù)合y=f?g(x)可用跟蹤表確定：4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法11例2：已知預(yù)期函4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法12這樣， x2=0

y2=a0*(x0-1)+y0+a0=a0*x0+y0而當(dāng)x>0時(shí)，有x,y,a:=0,a*x+y,a

而當(dāng)x=0時(shí)，y=x,即x,y,a:=x,y,a

此時(shí)，預(yù)期函數(shù)為x,y,a:=0,a*0+y,a:=0,y,a

于是，兩種情況下，預(yù)期函數(shù)均和條件規(guī)則中的相應(yīng)的ri(x)相同，從而程序時(shí)正確的。語(yǔ)句xyx,y:=x-1,y+ax1=x0-1y1=y0+a0x,y,a:=0,a*x+y,ax2=0y2=a0*x1+y14.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法12這樣，語(yǔ)句xyx4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法13例3：已知預(yù)期函數(shù)f為

(x>yx,y=x+|y|,x-|y||x<yx,y=y+|x|,y-|x|

證明下面的序列程序是正確的：

x,y:=max(x,y),min(x,y);

x,y:=max(x-y,x+y),min(x-y,x+y);

x,y:=max(x,y),min(x,y)證明：程序序列可以展開為

ifx>yx,y:=x,yelsex,y:=y,xfi;

ifx-y>x+y

(或y<0)x,y:=x-y,x+yelsex,y:=x+y,x-yfi;

ifx>yx,y:=x,yelsex,y:=y,xfi;

（續(xù)）4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法13例3：已知預(yù)期函4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法14證明(續(xù))：這是一個(gè)由條件語(yǔ)句組成的序列，它可以看成是復(fù)制語(yǔ)句序列的推廣。利用跟蹤表方法確定這一序列的程序函數(shù)，然后與預(yù)期函數(shù)進(jìn)行比較?？赡苡?種組合：(續(xù))4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法14證明(續(xù))：4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法15(1)執(zhí)行通路條件為

x0>y0y1>0x2>y2=x0>y0y0>0x1+y1>x1-y1

=x0>y0y0>0x0+y0>x0-y0

=x0>y0y0>0

函數(shù)變換為：

x3=x2=x1+y1=x0+y0

y3=y2=x1-y1=x0-y0條件語(yǔ)句xyx0>y0x,y:=x,yx1=x0y1=y0y1>0x,y:=x+y,x-yx2=x1+y1y2=x1-y1x2>y2x,y:=x,yx3=x2y3=y24.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法15(1)條件語(yǔ)句x4.7結(jié)構(gòu)化程序的正確性證明－代數(shù)方法16(2)執(zhí)行通路條件為

x0>y0y1>0x2<y2=x0>y0y0>0x1+y1<x1-y1