程序正确性证明(课堂ppt)课件.ppt

《程序正确性证明(课堂ppt)课件.ppt》由会员分享，可在线阅读，更多相关《程序正确性证明(课堂ppt)课件.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第5讲 程序正确性证明1经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 5.1 程序正确性概述n什么样的程序才是正确的？n如何来保证程序是正确的？2经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用关于程序正确性的认识u什么样的程序才是正确的？“测试测试”或或“调试调试”方法方法根据问题的特性和软件所要实

2、现的功能，选择一些具有代表性的数据，设计测试用例。通过用例程序执行，去发现被测试程序的错误。采用采用“测试测试”方法可以发现程序中的错误，方法可以发现程序中的错误，但却不能证明程序中没有错误！但却不能证明程序中没有错误！因此，为保证程序的正确性，必须从理论上因此，为保证程序的正确性，必须从理论上研究有关研究有关“程序正确性证明程序正确性证明”的方法。的方法。3经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用程序正确性证明发展历程u20世纪50年代 Turing开始研究。u1967年，Floyd和Naur提出不变式

3、断言法。u1969年，Hoare提出公理化方法。u1975年，Dijkstra提出最弱前置谓词和程序推导方法，解决了断言构造难的问题，可从程序规约推导出正确程序，使正确性证明变得实用。程序正确性理论是十分活跃的课题，不仅可程序正确性理论是十分活跃的课题，不仅可以证明顺序程序的正确性，而且还可以证明非确以证明顺序程序的正确性，而且还可以证明非确定性程序，以及并行程序的正确性。定性程序，以及并行程序的正确性。4经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用程序正确性理论u程序设计的一般过程5经营者提供商品或者服务有

4、欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用程序正确性理论u程序功能的精确描述1、程序规约程序规约：对程序所实现功能的精确描述，由程序的前置断言和后置断言两部分组成。2、前置断言前置断言：程序执行前的输入应满足的条件，又称为输入断言。3、后置断言后置断言：程序执行后的输出应满足的条件，又称为输出断言。程序设计过程：问题 程序规约 程序6经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用程序规约的基本分类u非形式化程序规约 非形式化程序规约采用自然语言描述

5、程序功能，简单、方便，但存在二义性，因此，不利于程序的正确性证明。u形式化程序规约 采用数学化的语言描述程序功能，描述精确，无二义性，便于程序的正确性证明。7经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用程序规约的实例u在书写程序规约时，使用Q表示前置断言，R表示后置断言，S表示问题求解的实现程序。在前置断言Q之前，还必须给出Q和R中所出现的标识符的必要说明。例例1：求数组：求数组b0:n-1中所有元素的最大值。中所有元素的最大值。in n:integer;in b0:n-1:array of integer;

6、out y:integer Q:n 1 S R:y MAX(i:0 i n;bi)例例2：求两个非负整数的最大公约数。：求两个非负整数的最大公约数。in a,b:integer;out y:integer8经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用程序规约的实例例例2：求两个非负整数的最大公约数。：求两个非负整数的最大公约数。in a,b:integer;out y:integer Q:a 0 b 0 S R:y MAX(i:1 i min(a,b)(a mod i 0)(b mod i 0)9经营者提供商

7、品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用程序正确性定义u衡量一个程序的正确性，主要看程序是否实现了问题所要求的功能。若程序实现了问题所要求的功能，则称它为正确的，否则是不正确的。u对程序的正确性理解，可以分为两个层次：从广义来说，一个程序的正确性取决于该程序满足问题实际需求的程度。从狭义而言，如果一个程序满足了它的程序规约就是正确的。程序设计过程：问题 程序规约 程序10经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用程序正确性定义u程

8、序规约QSR是一个逻辑表达式，其取值为真或假。其中取值为真的含义是指：给定一段程序S，若程序开始执行之前Q为真，S的执行将终止，且终止时R为真，则称为“程序S，关于前置断言Q和后置断言R是完全正确的”。11经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用程序正确性定义u部分正确部分正确：若对于每个使得Q(i)为真，并且程序S计算终止的输入信息i，R(i,S(i)都为真，则称程序S关于Q和R是部分正确的。u程序终止程序终止：若对于每个使得Q(i)为真的输入i，程序S的计算都终止，则称程序S关于Q是终止的。u完全正确

9、完全正确：若对于每个使得Q(i)为真的输入信息i，程序S的计算都将终止，并且R(i,S(i)都为真，则称程序S关于Q和R是完全正确的。u一个程序的完全正确，等价于该程序是部分正确，同时又是终止的。12经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用程序正确性的证明方法分类u证明部分正确性的方法 A.Floyd的不变式断言法的不变式断言法 B.Manna的子目标断言法的子目标断言法 C.Hoare的公理化方法的公理化方法u终止性证明的方法 A.Floyd的良序集方法的良序集方法 B.Knuth的计数器方法的计数器方

10、法 C.Manna等人的不动点方法u完全正确性的方法 A.Hoare公理化方法的推广 B.Burstall的间发断言法 C.Dijkstra的弱谓词变换方法以及强验证方法13经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用循环不变式断言u把反映循环变量的变化规律变化规律，且在每次循环体的执行前后均为真的逻辑表达式称为该循环的不变式断不变式断言言。例例 带余整数除法问题：设带余整数除法问题：设x为非负整数，为非负整数，y为正整数，求为正整数，求 x除以除以y的商的商q，以及余数以及余数r。程序：程序：q0；rx；w

11、hile(r y)/该循环不变式断言：该循环不变式断言：r ry；q q1；/(xyqr)r 014经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用5.2 不变式断言法u证明步骤：1、建立断言建立断言建立程序的输入、输出断言输入、输出断言，如果程序中有循环出现的话，在循环中选取一个断点，在断点处建立一个循循环不变式断言。环不变式断言。2、建立检验条件建立检验条件将程序分解为不同的通路，为每一个通路建立一个检验条件，该检验条件为如下形式：I R=O 其中I为输入断言，R为进入通路的条件，O为输出断言。3、证明检验条

12、件证明检验条件运用数学工具证明步骤2得到的所有检验条件，如果每一条通路检验条件都为真，则该程序为部分正确的。15经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用不变式断言法实例1u例：设x,y为正整数，求x,y的最大公约数z的程序，即z=gcd(x,y)。Function gcd(x1,x2:integer);var y1,y2,z:Integer;Beginy1:=x1;y2:=x2;while(y1y2)do if(y1y2)y1:=y1-y2 else y2:=y2-y1 z:=y1;write(z);En

13、dSTART(x1,x2)(y1,y2)y1y2y1y2y1:=y1-y2y2:=y2-y1z:=y1STOPTFTF16不变式断言法实例1(建立断言)u输入断言：输入断言：I(x1,x2):x10 x20u输出断言：输出断言：O(x1,x2,z):z=gcd(x1,x2)u循环不变式断言：循环不变式断言：P(x1,x2,y1,y2):x10 x20 y10 y20 gcd(y1,y2)=gcd(x1,x2)通路划分：通路划分：通路1：a-b通路2：b-d-b通路3：b-e-b通路4：b-g-cSTART(x1,x2)-(y1,y2)y1y2y1y2y1:=y1-y2y2:=y2-y1z:=y

14、1STOPTFTFI(x1,x2)aP(x1,x2,y1,y2)bcO(x1,x2,z)deg17经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用不变式断言法实例1(建立检验条件)u检验条件：I R=Ou通路1：I(x1,x2)=P(x1,x2,y1,y2)x10 x20=x10 x20 y10 Y20 gcd(y1,y2)=gcd(x1,x2)u通路2：P(x1,x2,y1,y2)y1y2 y1y2=P(x1,x2,y1-y2,y2)x10 x20 y10 y20 gcd(y1,y2)=gcd(x1,x2)y1

15、y2 y1y2=x10 x20 y1-y20 y20 gcd(y1-y2,y2)=gcd(x1,x2)18经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用不变式断言法实例1(建立检验条件)u通路3：P(x1,x2,y1,y2)y1y2 y1 P(x1,x2,y1,y2-y1)x10 x20 y10 y20 gcd(y1,y2)=gcd(x1,x2)y1y2 y1x10 x20 y10 y2-y10 gcd(y1,y2-y1)=gcd(x1,x2)u通路4：P(x1,x2,y1,y2)y1=y2=O(x1,x2,z

16、)x10 x20 y10 y20 gcd(y1,y2)=gcd(x1,x2)y1=y2 =z=gcd(x1,x2)19经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用不变式断言法实例1(证明检验条件)u通路1：x10 x20 x1=y1 x2=y2=u通路2：若y1y2,gcd(y1-y2,y2)=gcd(y1,y2)=gcd(x1,x2)u通路3:若y2y1,gcd(y1,y2)=gcd(y1,y2-y1)=gcd(x1,x2)u通路4:若y1=y2,gcd(y1,y2)=gcd(x1,x2)=y1=y2=z

17、P(x1,x2,y1,y2)y1=y2=O(x1,x2,z)20经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用不变式断言法实例2u对任一给定的自然数对任一给定的自然数x，计算计算z ，即计算即计算x的平方根取整。的平方根取整。13(2n+1)=(n+1)2 y1=n;y3=2y1+1;y2=(y1+1)2输入断言：I(x):x0输出断言：O(x,z):z2 x(y1,y2,y3)y2+y3y2y2x(y1+1,y3+2)(y1,y3)y1z结束A I(x)B P(x,y1,y2,y3)DC O(x,z)TF21

18、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用不变式断言法实例2u检验条件：I R=Ou通路1：A-BI(x)=P(x,0,1,1)x0=0 x 1=(0+1)2 1=2*0+1u通路2：B-D-BP(x,y1,y2,y3)y2x=p(x,y1+1,y2+y3+2,y3+2)y12x y2=(y1+1)2 y3=2y1+1 y2x=(y1+1)2 x y2+y3+2=(y1+1+1)2 y3+2=2(y1+1)+1u通路3：B-CP(x,y1,y2,y3)y2x=O(x,y1)y12 x y2=(y1+1)2

19、y3=2y1+1 y2x=y12 x (y1+1)2 x y2+y3+2=(y1+1+1)2 y3+2=2(y1+1)+1证明：x(y1+1)2(y2 x,y2=(y1+1)2)y2+y3+2=(y1+1)2+2y1+1+2=(y1+1)2+2(y1+1)+1=(y1+1+1)2 y3+2=2y1+1+2=2(y1+1)+1u检验条件3y12 x y2=(y1+1)2 y3=2y1+1 y2x=y12 x(y1+1)2 证明：y12 x xx=0 y0=0 u输出断言：O(x,y,z):z=gcd(x,y)u循环不变式断言：P(x,y):x=0 y=0 gcd(x,y)=gcd(x0,y0)n

20、例：设x,y为非负整数，求x,y的最大公约数z的程序，即z=gcd(x,y)。STARTRead(x,y)x0y=xy:=y-xx yz:=ySTOPTFTFI(x,y)aP(x,y)bcO(x,y,z)deg26经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用子目标断言法(建立断言)u输入断言 I(x,y):x0=0 y0=0(x00 y00)u输出断言 O(x,y,z):z=gcd(x,y)u子目标断言 P(x,y,yend):x=0 y=0(x0 y0)=yend=gcd(x,y)STARTRead(x,y

21、)x0y=xy:=y-xx yz:=ySTOPTFTFI(x,y)aP(x,y,yend)bcO(x,y,z)deg27经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用子目标断言法(建立检验条件)u通路1：b-c 检验条件1 x=0=P(x,y,yend)x=0=x=0 y=0 (x0 y0)=yend=gcd(x,y)u通路2：b-d-b 检验条件2P(x,y-x,yend)x0 y=x=P(x,y,yend)x=0 y-x=0 (x0 y-x0)=yend=gcd(x,y-x)x0 y=x=x=0 y=0(x

22、0 y0)=yend=gcd(x,y)u通路3：b-e-b 检验条件3P(y,x,yend)x0 y P(x,y,yend)u通路4：a-b 检验条件4x0=0 y0=0 (x0 0 y0 0)P(x0,y0,yend)=yend=gcd(x0,y0)28经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用子目标断言法(建立检验条件)u通路1：控制转出循环时，子目标断言成立。u通路2、通路3：如果在通过循环之后，子目标断言在断点处成立，那么，在通过循环之前，断言也成立。u通路4：如果输入断言为真，且控制第一次通过断点

23、B时子目标断言为真，则输出断言为真。29经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用子目标断言法(证明检验条件)u检验条件1：x=0=x=0 y=0=yend=gcd(x,y)证明：因为有 x=0,yend=y所以 yend=y=gcd(0,y)=gcd(x,y)u检验条件2：P(x,y-x,yend)x0 yx=P(x,y,yend)即证明：x=0 y-x=0(x0 y-x0)=yend=gcd(x,y-x)x0 y=x=x=0 y=0(x0 y0)=yend=gcd(x,y)30经营者提供商品或者服务有欺

24、诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用5.4 公理化方法u公理化方法公理化方法是由C.A.R.Hoare于1969年提出的一种形式化的证明程序部分正确性的方法。uWHILE型程序WHILE型程序由一个有限的语句序列组成，每个语句之间以分号隔开，即：B0;B1;Bn其中B0是程序中唯一的开始语句STARTy f(x)Bi(1i n)是下列语句之一：31经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用(1)赋值语句 yg(x,y)(2)条件语句 If

25、R then F1 else F2If R do F1(3)循环语句While R do F1(4)复合语句Begin F1;F2;Fkend(5)停机语句zh(x,y)HALT其中，R是逻辑表达式，F1,F2,Fk是上列五种语句中的任何语句。公理化方法32经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用WHILE型程序例子u不变式断言法实例2中计算z=的程序START(y1,y2,y3)(0,1,1);while y2x do(y1,y2,y3)(y1+1,y2+y3+2,y3+2);zy1;HALT33经营者

26、提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用不变式演绎系统u不变式语句不变式语句PFQ其中，P和Q是逻辑表达式，F是一个程序段。含义是：如果执行F前P成立，且执行终止，则执行F后Q成立。这时，不变式语句为真。不变式语句有时也称为归纳表达式归纳表达式。u推理规则推理规则 其中，B是一个不变式语句，Ai是一个逻辑表达式或者是其他的不变式语句。含义是：为了推论后项B为真，只需证明前项A1,An为真。34经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受

27、服务的费用程序部分正确但不终止实例n例：求两个非负整数x、y的最大公约数z的程序。Program A var x,y,z,s:integer;begin read(x,y);while x 0 do if y x then y=y x;else x=x y;z=y;write(z);end.STARTRead(x,y)x0yxy:=y-xx:=x-yz:=ySTOPTFTFI(x,y)aP(x,y)bcO(x,y,z)deg 可以利用不变式断言等方法证明该程序的部分正确性，但无法证明它是终止的。因为当y0时，程序循环将不终止！35经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿

28、其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用5.5良序集方法证明程序终止性u1.基本概念偏序集良序集u2.采用良序集方法证明程序终止性36经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用偏序集的概念u偏序集偏序集设有一个非空集合设有一个非空集合W和一个定义在和一个定义在W上的二元关系上的二元关系，且，且这个关系满足下列性质：这个关系满足下列性质：1 1）传递性，即对于一切）传递性，即对于一切a,b,cW,W,如果如果a ab,bb,bc c，则则a ac c2 2）反对称性，即对于反对称性，

29、即对于a ab,b,则有则有baba3 3）反自反性，即对于一切反自反性，即对于一切aWaW，aaaa称称W W为具有关系的偏序集，记做（为具有关系的偏序集，记做（W,W,）。）。例如：（1）具有小于关系（）的，位于01之间的实数集合A1。（2）具有小于关系（）的全体整数集合B1。但将 换成 就不是偏序集。（1）具有小于等于关系（）的，位于01之间的实数集合A1。（2）具有小于等于关系（）的全体整数集合B1。37经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用良序集的概念u良序集良序集设（设（W,）是偏序集，如果

30、不存在由）是偏序集，如果不存在由W中的元素构成的中的元素构成的无限递减序列无限递减序列:a2 a1 a0，则称（则称（W,）是良序）是良序集。集。例如：（1）若N是自然数集合，那么（N，）是良序集。（2）具有通常序A B C Z的字母表=A,B,Z是良序集。下述集合A1和B1是偏序集，但不是良序集。（1）具有小于关系（）的，位于01之间的实数集合A1。（2）具有小于关系（Qj(x,raj(x,y)证明对每一个从截断点i到截断点j的通路aij，有 Qi(x,y)R a i j(x,y)=Q j(x,r a i j(x,y)即证明中间断言是“正确的”，是“良断言”；u4.证明 Qi(x,y)=E

31、i(x,y)W，即终止表达式是良函数；终止表达式是良函数；u5.证明对于每一个从截断点i到截断点j的通路aij，有 Qi(x,y)Raj(x,y)=E j (x,y)E i(x,y)。40经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用良序集方法证明程序终止性实例u例子：对任一给定的自然数x，计算z ，即计算x的平方根取整。开始(0,0,1)(y1,y2,y3)y2+y3y2y2 x(y1+1,y3+2)(y1,y3)y1z结束BTF41经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失

32、，增加赔偿的金额为消费者购买商品的价款或接受服务的费用良序集方法证明程序终止性实例u1.选取断点B，建立中间断言 Q(x,y1,y2,y3):y2 0u2.取良序集（N,B：I(x)=Q(x,y1,y2,y3)，即：x0=0 0 从截断点B-B：Q(x,y1,y2,y3)y2+y3 Q(x,y1+1,y2+y3,y3+2)即：y2 0 y2+y3 y2+y3 042经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用良序集方法证明程序终止性实例u4.证明E(x,y)是良函数，即证明Q(x,y)=E(x,y)N，即 y

33、2 0=x-y20 Nu5.证明终止条件成立 Q(x,y)y2+y3 E(x,y1+1,y2+y3,y3+2)E(x,y1,y2,y3)即：y20 y2+y3 x-y2-y3 bx00y00=x00y002x0+y0+02x0+y0检验条件2：b-d-bx0y0(2x+y+I2x0+y0)x0yx=x0y-x0(2x+(y-x)+I+12x0+y0)证明：x0=(x-10)2x+(y-x)+I+1=2x+y+I-(x-1)2x+y+I 2x0+y0检验条件3：b-e-bx0y0(2x+y+I2x0+y0)x0yy0 x0(2y+x+I+1 2x0+y0)证明：(y yx-1)2y+x+I+1y

34、+x-1+x+I+1=y+2x+I 2x0+y0 由于2x+y+I2x0+y0是不变式断言，因此，I（循环次数）必定小于常量2x0+y0，也就是循环只能执行有限次，即程序终止。采用计数器方法证明程序终止性和利用不变式断言法证明部分正确性步骤完全类似，只要再添加输出断言部分检验条件并证明，即可完成程序部分正确性证明。因此，可以把上述两者联合起来，完成程序的完全正确性证明。48经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用另一种计数器方法证明程序终止性u证明思路：对程序中的每一个循环，构造一个和该循环中变量有关的整

35、数函数N(x,y)，若N(x,y)满足以下两个条件：当循环条件成立时，N(x,y)0；每次循环，N(x,y)都减小。由N(x,y)的值构成一个单调递减的整数序列，N(x,y)0，因而，循环只能执行有限次。49经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用另一种计数器方法证明程序终止性实例u例：设x,y为正整数，求x,y的最大公约数z的程序，即z=gcd(x,y)。START(x1,x2)(y1,y2)y1y2y1y2y1:=y1y2y2:=y2y1z:=y1STOPTFTF50经营者提供商品或者服务有欺诈行为的

36、，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用另一种计数器方法证明程序终止性实例选取 N(y1,y2)=max(y1,y2)输入断言：I(x1,x2):x10 x20当第一次进入循环时有y10y20 有算法得y1y2,则y1-y2y1,y2不变；y1y2,y1不变。始终有y10y20 于是就有N(y1,y2)0;每执行一次循环，N(y1,y2)是递减的。START(x1,x2)(y1,y2)y1y2y1y2y1:=y1y2y2:=y2y1z:=y1STOPTFTF51经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，

37、增加赔偿的金额为消费者购买商品的价款或接受服务的费用采用计数器方法证明程序终止性难点u采用计数器方法证明程序终止性关键在于确定采用计数器方法证明程序终止性关键在于确定一个合适的中间断言（或选取一个合适的函数一个合适的中间断言（或选取一个合适的函数N N（x,yx,y），尤其对于一些循环次数事先难以），尤其对于一些循环次数事先难以估计的程序，要找出循环次数的上限更为困难。估计的程序，要找出循环次数的上限更为困难。52经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用正整数的一个性质u对于任意正整数，满足下列关系：若y

38、1y2,gcd(y1,y2)=gcd(y1-y2,y2)若y2y1,gcd(y1,y2)=gcd(y1,y2-y1)若y1=y2,gcd(y1,y2)=y1=y253经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用实验安排u实验二：验证并使用应用框架的设计方法内容：课本P69(ex04-01.h);P7072(4);(5);(6);(7)部分的程序);P73;P7475;P8485(两个程序);P86(上半部分的程序);P90(下半部分的程序);P9192。时间：13周，星期二晚18：0022：00。u实验三：应用框架的使用内容：五子棋程序，实现两人互弈。时间：15周，星期二晚18：0022：00。54