第2章结构化程序.ppt

* K为执行次数的计数器。 * * 作用2方向;作用3 方法 * * * * * * * * * * * * * * * * * … for i:=1 to m do if A[i]=x then goto 1 fi; m:=m+1; A[m]:=x; goto 2; 1: wirte(i,x); 2: … … for i=1 to m do if A[i]=x then exit k fi; k:write(i, x) ended: begin m:=m+1; A[m]=x; end … 变换为多 重出口循 环语句 J.T.与L.Presser提出的循环语句 loop S1 ; S2 ; ‥ ‥ ‥ Sn ; End-loop 其中 ，S1、 S2 …… Sn中至少有一个包含下面 两种跳出语句之一： (1) exit（无条件跳出） (2) exit when（条件跳出） 功能：重复执行loop和end-loop之间的诸语句，直到遇到无条件跳出或条件跳出的条件成立时，即离开此结构 Dijkstra－－推广的条件控制结构 if guard 1: action 1; guard 2: action 2; … … guard n: action n; fi 含义：检查条件guard 1，…，guard n，若guard i 成立，执行相应的语句action i ；如果均不成立，不执行任何语句，然后跳出此结构。 Dijkstra－－推广的循环控制结构 loop guard 1: action 1; guard 2: action 2; … … guard n: action n; pool 含义：重复执行loop和pool之间的部分，检查条件，若guard i 成立，则执行相应的语句action i；只有当所有guard 1，…，gudard n均不成立时，才跳出此结构。 作业 课本P38习题 1，2 请自学课本P29例2.2 * * * * * * * * * * * * * * * * * * * * * * * * * * * 判断：下述程序是否是结构化程序?(基集合为{序列，if-then-else，while-do}) 2.2 结构化定理 结构化定理: 任意一个正规程序，都可以函数等价于一个由基集合{序列,if-then-else,while-do} 产生的结构化程序。 2.2.1 程序函数 任何一个正规程序可以定义程序初始状态与程序最终状态之间的函数，这个函数称为程序函数，记为[P]。 X：程序初始状态； Y：程序最终状态。且： 对于每一个初始的数据状态X，程序是终止的 对于每一个给定的X，值Y是唯一的 P X Y {(X,Y)} 程序函数表示形式 有序对、条件规则、数据赋值等形式 例如：[if x ? y then z:=x else z:=y fi] 有序对：{((x,y,z),(x,y,min(x,y)))} 条件规则：{(x,y,z)|x ?y?z:=x ∨ xy?z:=y} 数据赋值：(z:=min(x,y)) 例子 写出下列程序的程序函数(x,y为整数) 1、[while x0 do x:=x-1 od] ={(x,min(0,x))}=(x:=min(0,x)) 2、[x:=x+y;y:=x-y] ={((x,y),(x+y,x))}=(x, y:=x+y,x) 3、[do x:=x+1 until xy od] ={((x,y),(max(x+1,y+1),y))}=(x:=max(x+1,y+1)) 基本程序所对应的程序函数 函数： [f]={(x,y)|y=f(x)} 序列： [f; g]={(x,y)|y=g ? f(x)} IF-THEN: [if-then]={(x,y)|p(x) →y=f(x) ∨ ?p(x) →y=x} IF-THEN-ELSE : [if-then-else]={(x,y)|p(x) →y=f(x) ∨ ?p(x) →y=g(x)} 基本程序所对应的程序函数 WHILE-DO: [while-do]={(x,y)| ? k≥ 0((?j,0?jk)(p ? fj(x)) ? ?p ? fk(x)→y= fk(x))} 分析 当k=0时，j不存在， ?p ? f0(x)为真，所以 y=x。 当k＝1时，j可取0，即p ? f0(x) ? ? p ? f1(x)为真，所以y= f1(x),即y= f(x)。 当k=2，j可取0,1，使p