《结构化程序设计》课件

第4章结构化程序设计4.1关于结构程序设计的基本概念4.2结构化程序和结构定理4.3结构化程序设计的判别4.4结构化程序设计的步骤和原理4.5逐步求精的程序设计4.6非结构化向结构化的转化4.7结构化程序的正确性验证小结习题第4章结构化程序设计4.1关于结构程序设计的基本概念4.1关于结构程序设计1.定义结构程序设计是避免使用GOTO语句的一种程序设计结构程序设计是自顶向下的程序设计是一种组织和编制程序的方法,利用它编制的程序易于理解和修改程序结构化的一个主要功能是使得正确性证明容易实现允许在设计过程中的每一步验证其正确性,即自动导致自我说明与自我捍卫的程序风格是讨论如何将任何大规模的复杂的流程图程序转换成一种标准形式,使得它们用几种标准的控制结构,通过重复和嵌套来表示.4.1关于结构程序设计1.定义结构程序设计的综合描述结构程序设计的综合描述:结构程序设计是一种进行程序设计的原则和方法，按照这种原则和方法设计出的程序的特点是：结构清晰、易阅读、易修改、易验证。结构程序设计语言：按照结构程序设计的要求设计出的程序设计语言称为结构程序设计语言。结构化程序：利用结构程序设计语言，或按照结构程序设计的思想编制的程序称为“结构化程序”。结构程序设计的综合描述结构程序设计的综合描述:关于GOTO语句的问题4.关于GOTO语句的问题取消GOTO语句，即GOTO有害。理由：GOTO语句使程序的静态结构与它的动态执行之间有很大的差别。这样使程序难阅读、难查错。去掉GOTO语句可以直接从程序结构上反映出程序运行的过程，结构清晰、便于查错、易验证。保留GOTO语句GOTO语句使用起来比较灵活，而且有些情况下能够提高程序的效率，若一味地强调删除GOTO语句，有些情形会使程序过于复杂，增加不必要的计算量。折中派（Knuth）不加限制地使用GOTO语句，特别往回跳的GOTO语句，会使程序结构难以理解，这种情形应尽量避免使用GOTO语句。为提高效率，同时又不破坏程序的良好结构，有控制地使用GOTO语句是有必要的。关于GOTO语句的问题4.关于GOTO语句的问题结构程序设计结论结论：结构程序设计讨论的是一种程序设计的方法和风格。关注的焦点是得到的程序的结构的好坏，而有无GOTO语句并不是一个程序结构好坏的标志。避免和限制使用GOTO语句是得到结构化程序的一种手段，而不是我们的目的。结构化程序设计既着眼于程序设计的思路清晰，又着眼于程序的结构清晰。即通过结构化的设计方法获得结构化产品结构程序设计结论结论：4.2结构化程序和结构定理一、结构化程序下面给结构化程序下一个精确的定义.4.2结构化程序和结构定理一、结构化程序流程图程序流程图程序的组成：函数节点、谓词节点和汇点。函数节点：只有一条入口线和一条出口线，一般与赋值语句相对应。谓词节点：有一条入口线和两条出口线，它不改变程序的数据项的值。汇点：有两条入口线和一条出口线，它不执行任何运算，只起到收集出口线的作用。fp1.流程图程序定义：一个用流程图的形式表示出来的程序，称为流程图程序。流程图程序流程图程序的组成：函数节点、谓词节点和汇点。fp1流程图程序举例流程图程序举例:pqgf流程图程序举例流程图程序举例:pqgf正规程序4.正规程序定义：满足以下两个条件的流程图程序称为正规程序。条件：具有一条入口线和一条出口线，且对每个节点，都有一条从入口线到出口线的通路通过该节点。例：下面两个流程图程序不是正规程序pfgpf正规程序4.正规程序pfgpf正规子程序3.正规子程序一个正规程序的某些部分仍然可以是正规程序,这些部分称为正规子程序.正规子程序3.正规子程序基本程序4.基本程序定义：一个正规程序，如果不包含多余一个节点的正规子程序，称为基本程序。即基本程序是一种不可再分解的正规程序。例：fgfghfgf基本程序4.基本程序fgfghfgf七种重要的基本程序函数:序列:If-thenIf-then-elsefgfpfgpf七种重要的基本程序fgfpfgpf七种重要的基本程序while-do:Do-until:Do-while-do:pfpgfpg七种重要的基本程序while-do:pfpgfpg复合程序和结构化程序5.复合程序若一个基本程序的函数节点用另外一个基本程序替换,所产生的正规程序称为复合程序。6.结构化程序由基本程序的一个固定的基集合（例如，序列、IF-THEN-ELSE、While-DO）构造出的复合程序称为结构化程序。复合程序和结构化程序5.复合程序二、结构化定理1.程序函数已知一正规程序P，对于每个初始的数据状态X，若程序是终止的，那么有确定的最终数据状态Y。如果对于每一个给定的X，值Y是唯一的，那么所有的有序对的集合{（X，Y）}定义了一个函数，称这个函数为程序P的程序函数，记为[P]。例：设程序P由三条语句组成：t:=x;x:=y;y:=t;对任意的X=(x,y,t),程序P的执行结果Y=（y,x,x）因此，程序函数是{（x,y,t）,(y,x,x)}本质：计算输入和输出的关系二、结构化定理1.程序函数二、结构化定理2.七种基本程序的程序函数[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)}二、结构化定理2.七种基本程序的程序函数二、结构化定理[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.七种基本程序的程序函数(续)二、结构化定理[while-do]={(x,y)|k二、结构化定理1）对于序列程序可使用跟踪表的方法计算[p]例：语句段：x:=x+y;y:=x-y;x:=x-y;解：假设变量x,y的初值为x0,y0,…有跟踪表：语句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.程序函数的计算二、结构化定理1）对于序列程序可使用跟踪表的方法计算[p]语二、结构化定理练习：计算下列语句序列的程序函数：y:=a;y:=x*y+b;y:=x*y+c;y:=x*y+d3.程序函数的计算二、结构化定理练习：计算下列语句序列的程序函数：3.程序二、结构化定理2)无循环程序的程序函数首先：构造有穷的执行树然后：对每条路径写出相应的表达式例：pfhrgq3.程序函数的计算二、结构化定理2)无循环程序的程序函数pfhrgq3.程序二、结构化定理执行树：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.程序函数的计算二、结构化定理执行树：pfhrqghrgg[p]={(二、结构化定理3)循环程序的程序函数g1g3p1p2p3g2g4g51g12g3p1g213p2p3g53g42执行树：3.程序函数的计算二、结构化定理3)循环程序的程序函数g1g3p1p2p3g2代换后的执行树：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)}代换后的执行树：g1g3p1g2p2p3g5g4f1f3f1二、结构化定理5.程序的函数等价如果程序P1和程序P2有相同的程序函数，称它们是函数等价的，或简称是等价的。5.结构化定理定理：任一正规程序都可以函数等价与一个由基集合{序列，if-then-else，while-do}产生的结构化程序。二、结构化定理5.程序的函数等价5.结构化定理结构化定理-证明证明：考察任一正规程序:

首先，从程序的入口处开始给程序的函数节点和谓词节点编号。编号为1，2，3，…，n（若入口处是汇点，那么宴会点的出口线继续考察，直到找到第一个函数节点或谓词节点）。同时将每一个函数节点及谓词节点的出口线用它后面的节点的编号进行编号。如果它后面没有函数节点或谓词节点，即该节点的出口线直接或通过汇点与程序的出口相连时，出口线的编号为0。peqh123400结构化定理-证明证明：考察任一正规程序:peqh123400结构化定理--证明对每一个编号为i，出口线编号为j、k的谓词节点p，构造一个新的IF-THEN-ELSE程序gi，如图：h其次，对原程序种的每一个编号为i，出口线编号为J的函数节点h，构造一个新的序列程序gi，如图：ijhL:=jgi=pgi=pL:=jL:=kjik结构化定理--证明对每一个编号为i，出口线编号为j、k的谓词结构化定理--证明最后，利用已经得到的一些gi（I=1,2,3,…,n），按下图形式构造一个while-do循环。这个循环体是一个对L从1到n进行测试的嵌套的IF-THEN-ELSE程序（最内层的I表示恒等函数）：L:=1L>0L=1?g1L=2?g2L=n-1?gn-1L=n?gn•••I•••F=结构化定理--证明最后，利用已经得到的一些gi（I=1,2,结构化定理--证明结论:显然,上面程序的功能和原程序的功能是相同的,因而它和原程序是函数等价的。而且，该程序是由一个固定的基集合{序列，IF-THEN-ELSE，WHILE-DO}产生的结构化程序，从而定理得证。结构化定理--证明结论:结构化定理举例例：考察如下的流程图程序：peqh123400第一步：编号，结果如上图。结构化定理举例例：考察如下的流程图程序：peqh123400结构化定理举例第二步：重新构造函数节点和谓词节点eL:=0g2=g1=pL:=2L:=3g3=qL:=0L:=4hL:=1g4=结构化定理举例第二步：重新构造函数节点和谓词节点eL:=0g结构化定理举例第三步：用IF-THEN-ELSE和WHILE-DO重新构造程序：L:=1L>0L=1?L=2?pL:=2L:=3eL:=0L=3?qL:=0L:=4L=4?hL:=1I结构化定理举例第三步：用IF-THEN-ELSE和WHILE结构化定理举例第四步：化简：上面得到的结构化程序比较庞大，且效率不高，还可以进一步改进，消除一些多余的对L的测试和赋值。化简的基本思想：对于某些j>0，如果gj中不包含赋值语句L:=j，则可以用gj代替所有的赋值L:=j。这样代替后，由于j不再赋值给L，因而测试L=j可以从IF-THEN-ELSE结构中去掉。这种替换直到以下情况出现为止：除了L:=0以外，所有给L赋值的语句均被消除；每个余下的gi’中都包含由相应赋值L:=I（gi’是gi经过一些替换以后得到的复合程序）例：结构化定理举例第四步：化简：结构化定理转换的化简用g4代替所有的L:=4的赋值语句，并删除L=4的测试L:=1L>0L=1?L=2?pL:=2L:=3eL:=0L=3?qL:=0hL:=1I结构化定理转换的化简用g4代替所有的L:=4的赋值语句，并删结构化定理转换的化简（续）用当前的g3’替换L:=3的赋值语句，并删除L=3的测试L:=1L>0L=1?L=2?pL:=2eL:=0qL:=0hL:=1I结构化定理转换的化简（续）用当前的g3’替换L:=3的赋值语结构化定理转换的化简（续）用g2’替换L:=2的赋值。L:=1L>0L=1?pqL:=0hL:=1IeL:=0结构化定理转换的化简（续）用g2’替换L:=2的赋值。L:=结构化定理转换的化简（续）删除循环中L:=1的赋值，因为除了L:=0的赋值回改变L的取值外，都不会改变L的取值，进而L=1的测试也可以删除。L:=1L>0pqL:=0heL:=0结构化定理转换的化简（续）删除循环中L:=1的赋值，因为除了结构化程序的特点具有层次化结构的程序，有很大的优点：书写时，自顶向下，逐步求精阅读时，自底向上，逐步抽象验证时，分层逐步验证结构化程序的特点具有层次化结构的程序，有很大的优点：4.3结构化程序设计的判别一个软件是否满足结构化标准可以用Mccabe关于软件复杂性度量的理论判断有关的定理和推论任何非结构化的程序是由下列4中情况引起从循环中转出从循环外转入从判定内转出从判定外转入4.3结构化程序设计的判别一个软件是否满足结构化标准可以用4.3结构化程序设计的判别(续)有关的定理和推论推论1：一个结构化程序可以按照不转入（出）循环或判定的原则编写。程序控制结构的表示用有向图表示。每个节点对应于顺序处理的代码块，弧线对应程序中的转移，箭头代表转移方向。假设只有一个入口和一个出口。如果从出口节点转回到入口节点，则称图是强连通的。abcdef4.3结构化程序设计的判别(续)有关的定理和推论abcde4.3结构化程序设计的判别(续)定理1：在一个强连同图G中，线性无关的环路数最大值V(G)＝e－n＋1，其中e是弧数，n是节点数。例如：V(G)=10-6+1=5V(G)的另一种计算方法V(G)＝

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

其中，p为程序中条件转移语句的个数，Q是分支情况语句，Ti是第i个分情况语句的情况总数。abcdef4.3结构化程序设计的判别(续)定理1：在一个强连同图G中4.3结构化程序设计的判别(续)推论2：一个结构化程序课退化称成最大环路数为1的程序。这种退化是对程序的逐渐抽象，形成只有一个入口和一个出口节点的子图的过程。定义1：正规子图是仅含顺序、选择和循环的子图。假设m是有一个入口节点和一个出口节点的正规子图，ev为程序的本质复杂性，则ev＝V(G)－m，将反映程序结构的复杂程度。vv越大，程序的结构化程度越差。显然，1<=ev<=V(G)推论3：一个结构化程序的本质复杂性ev为1。4.3结构化程序设计的判别(续)推论2：一个结构化程序课退4.3结构化程序设计的判别(续)判别途径判别一个程序是否满足结构化程序设计标准的要求：是否有一个入口和出口节点是否有转入循环或判定的情形计算程序的本质复杂性检验结构化程序设计标准的其他要求。4.3结构化程序设计的判别(续)判别途径4.4结构化程序设计的步骤和原理结构化程序设计的步骤：Step1：需求分析Step2：系统设计：总体设计和模块设计Step3：算法和程序实现；Step4：验证和测试Step5：运行程序和整理文档4.4结构化程序设计的步骤和原理结构化程序设计的步骤：4.4结构化程序设计的步骤和原理结构化程序设计的原理抽象分解模块化局部化和信息隐蔽一致性完整性：要求一个程序系统不丢失任何重要成分，系统无缺省且独立。独立意义的完整性指一个系统相对完备，除基本的运行环境外，不涉及其他系统。可验证性：指分解系统和构造模块时应使各模块和整个系统都能方便测试，从而也利于维护和修改4.4结构化程序设计的步骤和原理结构化程序设计的原理4.5逐步求精的设计方法结构化程序设计规则不是使程序写完之后再来验证程序的正确性，而是在算法逐步细化为程序的过程中，确保每一步细化都正确地实现前一步的要求，因此逐步求精既是一种程序设计方法，同时也是验证程序正确性的方法。逐步求精的思想：先全局后局部，先整体后细节，先抽象后具体的过程组织人们的思维活动，使得编写的程序结构清晰，容易阅读，易修改。同时它可以实现边设计边验证的方式简化对程序的正确性验证过程。是一种自顶向下的程序设计方法举例：4.5逐步求精的设计方法结构化程序设计规则不是使程序写完之4.5逐步求精的设计方法（续）例：编写一个程序，打印前n个素数(n为给定的正整数)Voidprime(intn){inti,x;x=1;for(i=1;i<n;i++){x=“下一个素数”；printf(“%d”,x);}}对语句x=“下一个素数”求精intprim；prim＝false；Do{ x++;}while(isprime(x))4.5逐步求精的设计方法（续）例：编写一个程序，打印前n个4.5逐步求精的设计方法（续）对函数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逐步求精的设计方法（续）对函数isprime(x)求4.5逐步求精的设计方法（续）intisprime(intx){k=2;Prim=true;While(k<=x-1&&prim){Prim=(xmodk)<>0;k++;}returnprim;}优化：关于x++,x+=2;关于上限的确定：x-1是最大的上限；4.5逐步求精的设计方法（续）intisprime(in4.6非结构化向结构化的转化法1：代码复制法123412344方法2：布尔标志法引入布尔变量,例：方法3：结构化定理4.6非结构化向结构化的转化法1：代码复制法12341234.6非结构化向结构化的转化(续)例WhilePdoBegin…ifqthengotoL1A;B;EndL1:…转化为：Bool:=True;WhilePandBooldoBegin…ifqthengotoBool:=falseelsebeginA;B;endEnd…4.6非结构化向结构化的转化(续)例转化为：4.7结构化程序的正确性证明－正确性定理1.正确性定理假设已知程序P和一个预期函数f，若有f＝[P]称程序P正确地实现了函数f，或者说程序P是正确的。根据结构化定理，任何结构化程序都可以用序列、条件和循环3种结构表示出来。直接验证循环程序的正确性很麻烦，希望用序列和分支结构表示循环结构，以简化循环的正确性证明。4.7结构化程序的正确性证明－正确性定理1.正确性定理4.7结构化程序的正确性证明－引理引理1:已知函数f和循环程序P：whilepdogod，

则f＝[whilepdogod]的充要条件是：对所有xD(f)，程序P终止，且f＝[ifptheng;ffi]证明：（1）必要性。假设f＝[whilepdogod]，那么程序P终止是必然的，否则等式不成立。进一步，考察程序

ifptheng；whilepdogodfi

显然，它和程序P是等价的，因而有，

[whilepdogod]=[ifptheng;whilepdogodfi]

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

f＝[ifptheng;ffi][ok]4.7结构化程序的正确性证明－引理引理1:已知函数f和4.7结构化程序的正确性证明－引理(续)(2)充分性。假设程序P终止，且f＝[ifptheng;ffi]

考察下面一组等价的程序（逐次使用if-then替换f得到的）：

ifptheng;ffi

ifptheng;ifptheng;ffifi

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

由于程序P终止，则这一组程序定是有限的，谓词p在执行有限次以后一定取值为false，这时的if-then语句等价于恒等函数I，即最后的程序为

ifptheng;ifptheng;…;Ifi…fifi

显然，该程序等价于whilepdogod

于是，f＝[ifptheng;ffi]【ok】4.7结构化程序的正确性证明－引理(续)(2)充分性。4.7结构化程序的正确性证明－引理(续)引理2：已知函数f和程序P：doguntilp，

则f=[doguntilp]的充分必要条件是：对所有的xD(f)，程序终止，且f＝[g；ifpthenf;fi]引理3：已知函数f和程序P：do1gwhilepdo2hod

则f=[do1gwhilepdo2hod]的充要条件是：对所有的xD(f)，程序终止，且f=[g；ifpthenh;f;fi]可知，循环程序的验证可以通过将循环化为递归的方法转换为终止性和由序列和条件组成的无循环程序的验证。4.7结构化程序的正确性证明－引理(续)引理2：已知函数4.7结构化程序的正确性证明－定理1定理1：已知预期函数f和基本程序P，则f=[P]的充要条件是：对所有的xD(f)，程序终止，且对不同的基本程序，函数f分别满足下列关系：情形a：对序列程序，即P＝g;h，有

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

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

y=g(x)|p(x)

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

y=g(x)|p(x)

y=h(x))}4.7结构化程序的正确性证明－定理1定理1：已知预期函数f4.7结构化程序的正确性证明－定理1(续)情形d：对while-do程序，即P=whilepdogod,有

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

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

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

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

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

y=f•g(x))}情形f：对do-while-do程序，即P=do1gwhilepdo2hod,有

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

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

y=g(x))}证明略。4.7结构化程序的正确性证明－定理1(续)情形d：对whi4.7结构化程序的正确性证明－代数方法1一个终止的循环程序的正确性证明可以转化为序列和条件程序的正确性证明；跟踪表和条件分离规则是序列和条件程序证明的基本方法；4.7结构化程序的正确性证明－代数方法1一个终止的循环程序4.7结构化程序的正确性证明－代数方法2一、跟踪表例：有序列程序段：x:=x+y;y:=x-y;x:=x-y;解：假设变量x,y的初值为x0,y0,…有跟踪表：语句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结构化程序的正确性证明－代数方法2一、跟踪表语句xy4.7结构化程序的正确性证明－代数方法3二、分离规则条件语句ifpthengelsehfi的程序函数为

（pg|

ph）

为验证条件语句的正确性，需要比较预期函数f和上面条件规则是否相等。1.复合条件规则的化简 如果g，h是条件语句，就会引入复合条件规则，为比较复合条件规则，需要首先对它进行化简。例如，4.7结构化程序的正确性证明－代数方法3二、分离规则4.7结构化程序的正确性证明－代数方法4(p1(q11r11|q12r12)|p2(q21r21|q22r22))形式上展开为，p1

q11r11|p1

q12r12|p2

q21r21|p2

q22r22一般情况下，这样展开可能是不成立的。例如，当p1为真，q11和q12为假，而p2为真，q21，q22有一个为真时，展开式有意义，而原复合规则无意义。但是如果p1和p2是分离的，即p1p2为假时，上述展开始终是成立的。4.7结构化程序的正确性证明－代数方法4(p1(q114.7结构化程序的正确性证明－代数方法5如果一个条件规则的所有谓词都是分离的，称它为分离规则。例如，

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

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

其复合条件规则是分离的，因而展开为，

(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结构化程序的正确性证明－代数方法5如果一个条件规则的4.7结构化程序的正确性证明－代数方法62.将条件规则化为分离规则原因：在化简和比较条件规则时，分离条件规则比一般的条件规则使用方便；一般条件规则的顺序是不能交换的，而分离的条件规则是可以交换的。因而，在讨论程序的正确性时，总是首先将条件规则化为分离规则4.7结构化程序的正确性证明－代数方法62.将条件规则化4.7结构化程序的正确性证明－代数方法72.将条件规则化为分离规则转换方法对任意的条件规则(p1r1|p2r2|p3r3|…)

可转化为

(p1r1|

p1

p2r2|

p1

p2p3r3|…)例如，条件规则

(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)),进一步展开

(x>0

x>y

z:=x|x>0

x<yz:=y|

x0y>0

x>yz:=y|x0y>0

x<yz:=x)4.7结构化程序的正确性证明－代数方法72.将条件规则化4.7结构化程序的正确性证明－代数方法83.条件语句的正确性证明 假设某一条件语句的程序函数是分离规则

(p1r1|p2r2|p3r3)

预期函数是f(x)。为证明条件语句的正确性，需证明两点：

（1）f(x)的定义域和分离规则的定义域相同 （2）利用分离规则的谓词将f(x)的定义域分解，并且有以下关系成立

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

另外，当f是以条件规则的形式给出时，如(q1s1|q2s2),这时要证明，4.7结构化程序的正确性证明－代数方法83.条件语句的正4.7结构化程序的正确性证明－代数方法93.条件语句的正确性证明(续)（1）两个分离规则的定义域相同的，即p1(x)p2(x)p3(x)=q1(x)q2(x)（2）两个分离规则中的谓词成对合取后，相应的结果是相同的，即

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结构化程序的正确性证明－代数方法93.条件语句的正4.7结构化程序的正确性证明－代数方法10例1：已知预期函数f=(x:=-x)，程序P为

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

证明P是正确的，即[P]=f(假设x是整数)。证明:f和P的定义域均为整数，因而相同，

又P的程序函数为

x>0

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

x:=x+2*abs(x)

它是分离规则，且

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

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

因而是正确的。4.7结构化程序的正确性证明－代数方法10例1：已知预期函4.7结构化程序的正确性证明－代数方法11例2：已知预期函数f是(x,y,a:=0,a*x+y,a)(x,y,a是整数，且x>0)。程序P是

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

证明程序P是正确的。证明：

由于已知x>0,且每循环一次x减1，因而通过有限次循环后，总有x=0,即对任何程序是终止的。另，

尚需证明：f=(p(x)y=f•g(x)|p(x)y=x)

对程序P来说，p(x)为x<>0，且已知x>0,因而

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

函数的复合y=f•g(x)可用跟踪表确定：4.7结构化程序的正确性证明－代数方法11例2：已知预期函4.7结构化程序的正确性证明－代数方法12这样， x2=0

y2=a0*(x0-1)+y0+a0=a0*x0+y0而当x>0时，有x,y,a:=0,a*x+y,a

而当x=0时，y=x,即x,y,a:=x,y,a

此时，预期函数为x,y,a:=0,a*0+y,a:=0,y,a

于是，两种情况下，预期函数均和条件规则中的相应的ri(x)相同，从而程序时正确的。语句xyx,y:=x-1,y+ax1=x0-1y1=y0+a0x,y,a:=0,a*x+y,ax2=0y2=a0*x1+y14.7结构化程序的正确性证明－代数方法12这样，语句xyx4.7结构化程序的正确性证明－代数方法13例3：已知预期函数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;

（续）4.7结构化程序的正确性证明－代数方法13例3：已知预期函4.7结构化程序的正确性证明－代数方法14证明(续)：这是一个由条件语句组成的序列，它可以看成是复制语句序列的推广。利用跟踪表方法确定这一序列的程序函数，然后与预期函数进行比较。可能有8种组合：(续)4.7结构化程序的正确性证明－代数方法14证明(续)：4.7结构化程序的正确性证明－代数方法15(1)执行通路条件为

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

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

=x0>y0y0>0

函数变换为：

x3=x2=x1+y1=x0+y0

y3=y2=x1-y1=x0-y0条件语句xyx0>y0x,y:=x,yx1=x0y1=y0y1>0x,y:=x+y,x-yx2=x1+y1y2=x1-y1x2>y2x,y:=x,yx3=x2y3=y24.7结构化程序的正确性证明－代数方法15(1)条件语句x4.7结构化程序的正确性证明－代数方法16(2)执行通路条件为

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