




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
Chapter
3.结构化程序设计方法(下)谢在鹏EMAIL:
ZXIEHHU@163.COM本讲义修改自叶枫老师去年的讲义知识点回顾:结构化程序设计特征1.2.3.知识点回顾:结构化程序设计的原则1.顺序、选择、循环2.3.4.5.Floyd部分正确性证明--流程图方法Floyd部分正确性证明-例:N
-1s
=
A(i
)i=0Floyd的不变式断言法输入断言输出断言y:一组中间变量
x:输入变量
xy:蕴含符ri(x,y):通过该通路后y的值通过此路径的条件实例1
21
2(x1,x2)fi
(y1,y2)y1-y2fi
y1y2-y1fi
y2DB
…
P(x,y)
Tru(1)若y1>y2,gcd(y1,y2)=gcd(y1-y2,y2)(2)若y2>y1,gcd(y1,y2)=gcd(y1,y2
-y1)(3)若y=y,gcd(y
,y
)=y1=y2ey1fi
zC…y(x,z)GFalseETrue开始A
…
j(x)y1=y2Falsey1>y2结束设x1,x2是正整数,求他们的最大公约数z=gcd(x1,x2)。我们知道,对于任意正整数y1,y2,有下列关系:(x1,x2)fi
(y1,y2)y1-y2fi
y1y2-y1fi
y2y1fi
zC…y(x,z)DB
…
P(x,y)
TrueGFalseETrue开始A
…
j(x)y1=y2Falsey1>y2结束(1)建立断言(x1,x2)fi
(y1,y2)y1-y2fi
y1y2-y1fi
y2A
…
j(x)y1fi
zC…y(x,z)DB
…
P(x,y)
TrueGFalseETrue开始y1=y2Falsey1>y2结束通路1:A-->B所以(2)建立检验条件-1(x1,x2)fi
(y1,y2)y1-y2fi
y1y2-y1fi
y2A
…
j(x)y1fi
zC…y(x,z)DB
…
P(x,y)
TrueGFalseETrue开始y1=y2Falsey1>y2结束通路条件(2)建立检验条件-2所以检验条件为:(x1,x2)fi
(y1,y2)y1-y2fi
y1y2-y1fi
y2A
…
j(x)y1fi
zC…y(x,z)DB
…
P(x,y)
TrueGFalseETrue开始y1=y2Falsey1>y2结束通路条件通路2:B-->D-->B通路后的y值(2)建立检验条件-3(x1,x2)fi
(y1,y2)y1-y2fi
y1y2-y1fi
y2A
…
j(x)y1fi
zC…y(x,z)DB
…
P(x,y)
TrueGFalseETrue开始y1=y2Falsey1>y2结束(3)
证明检验条件-1通路1:通路2:(3)
证明检验条件-2通路3:通路4:不变式断言法实例-2n2<x<(n+1)2(0,0,1)->(y1,y2,y3)y2+y3->y2y1->zABDx
Z
=
开始C(y1+1,y3+2)->(y1,y3)结束y2<x(0,0,1)->(y1,y2,y3)y2+y3->y2y1->zADC开始(y1+1,2*y1+1)->(y1,y3)结束By2<xy1=n;y3=2*y1+1;y2=
(y1+1)2;通路1:A-->B(2)建立检验条件-1(0,0,1)->(y1,y2,y3)y2+y3->y2y1->zABDC开始(y1+1,2*y1+1)->(y1,y3)结束y2<xy1=n;y3=2*y1+1;y2=
(y1+1)2;(2)建立检验条件-2通路2:B-->D-->B(0,0,1)->(y1,y2,y3)y2+y3->y2y1->zABD开始C(y1+1,2*y1+1)->(y1,y3)结束y2<xy1=n;y3=2*y1+1;y2=
(y1+1)2;(2)建立检验条件-2通路2:B-->C(0,0,1)->(y1,y2,y3)y2+y3->y2y1->zABD开始C(y1+1,2*y1+1)->(y1,y3)结束y2<xy1=n;y3=2*y1+1;y2=
(y1+1)2;(3)
证明检验条件-1通路1:通路2:(3)
证明检验条件-2通路3:良序集方法证明程序终止性实例
x
(0,0,1)
(y1,y2,y3)(y1+1,y3+2)(y1,y3)y1
zB’y2+y3
y2B…
p(x,y)y2<x开始结束Dy2
<xy3>0终止表达式
x-y2循环结构终止的条件表达式(0,0,1)
(y1,y2,y3)y2+y3
y2(y1+1,y3+2)(y1,y3)y1
zB’
…q(x,y1,y2,y3)A…φ(x)B…
p(x,y)y2<x开始结束D终止表达式(0,0,1)
(y1,y2,y3)y2+y3
y2(y1+1,y3+2)(y1,y3)y1
zB’
…q(x,y1,y2,y3)A…φ(x)B…
p(x,y)y2<x开始结束D终止表达式y2
<xy3>0(0,0,1)
(y1,y2,y3)(y1+1,y3+2)(y1,y3)y1
zB’
…q(x,y1,y2,y3)y2+y3
y2B…
p(x,y)A…φ(x)2y
<x开始结束D
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 教育机器人技术在特殊教育中的运用
- 教育技术中的交互设计-以包容性为核心
- 公交优先战略下2025年城市交通拥堵治理成本效益分析报告
- 福建省泉州市2024-2025学年九上化学期末经典模拟试题含解析
- 嵩山少林武术职业学院《企业文化建设》2023-2024学年第一学期期末试卷
- 承德护理职业学院《汽车造型设计2》2023-2024学年第一学期期末试卷
- 宿迁职业技术学院《网页设计与制作实验》2023-2024学年第一学期期末试卷
- 陕西科技大学镐京学院《建筑火灾防治与风险评估》2023-2024学年第一学期期末试卷
- 云南弥勒市2024年化学九上期末综合测试模拟试题含解析
- 藁城舒卿培训课件
- 暑假社会实践安全教育
- 2025年自考有效沟通技巧试题及答案
- 2025年教育管理与政策研究考试试题及答案
- 商场物业外包合同协议
- 义务教育《艺术课程标准》2022年修订版(原版)
- 2025民宿租赁合同标准范本
- 云仓公司规章管理制度
- 落实责任制整体护理总结
- 汽车返利协议书范本
- 植物营养学测试试题及答案
- 2025年小学数学新教材培训
评论
0/150
提交评论