《PMChap6小程序设计的基本方法》由会员分享，可在线阅读，更多相关《PMChap6小程序设计的基本方法（39页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 程序设计基本方法程序设计基本方法主要内容：主要内容：n引言引言-程序设计的基本原则程序设计的基本原则n选择语句的设计选择语句的设计n循环语句的设计循环语句的设计n循环不变式的设计循环不变式的设计n界函数的设计界函数的设计6.1 程序设计的基本原则程序设计的基本原则Principle 1: A program and its proof should be developed hand in hand, with the proof usually leading the way, 一个程序和它的正确性证明应同时设计，并且最一个程序和它的正确性证明应同时设计，并且最好以考虑证明为先
2、导。好以考虑证明为先导。Principle 2：使用理论来提供正确性的理解，而使用理论来提供正确性的理解，而在适当的地方用常识和直观方法，但当出现困难和在适当的地方用常识和直观方法，但当出现困难和复杂情况时，仍然依据形式理论作保证。当然一个复杂情况时，仍然依据形式理论作保证。当然一个人只有既有常识又掌握理论才能有效地在形式化和人只有既有常识又掌握理论才能有效地在形式化和常识之间进行协调，前者是程序员一直在使用。常识之间进行协调，前者是程序员一直在使用。6.1 程序设计的基本原则程序设计的基本原则Principle 3：要了解将用程序来处理的对要了解将用程序来处理的对象的性质。象的性质。例：假设
3、有一袋装有黑白两色棋子。每次例：假设有一袋装有黑白两色棋子。每次从袋中任取两粒子，若它们同色，则丢掉从袋中任取两粒子，若它们同色，则丢掉这两粒子，然后再补进一只黑子，否则丢这两粒子，然后再补进一只黑子，否则丢掉黑子，放回白子。连续执行这一步骤，掉黑子，放回白子。连续执行这一步骤，直至袋中只剩下一子为止。试问最后这一直至袋中只剩下一子为止。试问最后这一子是黑或白？编一程序回答此问题。子是黑或白？编一程序回答此问题。6.1 程序设计的基本原则程序设计的基本原则Principle 4：不要忽视任何看起来十分明显的原不要忽视任何看起来十分明显的原则，只有通过有意识地运用这些原则才会获得成功。则，只有通
4、过有意识地运用这些原则才会获得成功。Principle 5：认识一个原则和应用一个原则是两认识一个原则和应用一个原则是两回事。回事。 Ideas may be simple and easy to understand, but their application may require efforts. Recognizing a principle and applying it are two different things.Principle 6:在着手编程之前，首先要弄清楚问题在着手编程之前，首先要弄清楚问题是要求是要求“做什么做什么”的，并将其抽象化为前置条件和的，并将其抽象化为
5、前置条件和后置条件，即给出精确的程序规范，且勿仓促编码。后置条件，即给出精确的程序规范，且勿仓促编码。6.1 程序设计的基本原则程序设计的基本原则Principle 7: 程序设计是一种面向目标的设计活动。即程序设计是一种面向目标的设计活动。即程序设计是围绕着目标程序设计是围绕着目标Q进行的，这意味着进行的，这意味着Q起着比起着比P更更重要的作用。重要的作用。关于证明和测试数据分析关于证明和测试数据分析n边进行程序设计，边写下有关的测试数据。关键在边进行程序设计，边写下有关的测试数据。关键在于有效地选择和生成测试数据集；于有效地选择和生成测试数据集；n从工程角度看，测试是重要的；从工程角度看，
6、测试是重要的；n但从人员培训的角度看，应该训练程序员具有编制但从人员培训的角度看，应该训练程序员具有编制正确程序的能力；正确程序的能力；n因此，学习和研究形式证明技术是培养能力的一种因此，学习和研究形式证明技术是培养能力的一种有效的途径有效的途径n测试只能证明程序有错，并不能证明程序是正确的。测试只能证明程序有错，并不能证明程序是正确的。Test对程序员的科学训练是十分重要的，有人曾做对程序员的科学训练是十分重要的，有人曾做过一个试验：一个题目由一批印度的程序员和过一个试验：一个题目由一批印度的程序员和中国的程序员来做，结果如何？中国的程序员来做，结果如何？n由一批印度程序员来做，其结果惊人地
7、相似；由一批印度程序员来做，其结果惊人地相似；n而由一批中国程序员来做，编出的程序五花八门。而由一批中国程序员来做，编出的程序五花八门。只有规范的科学的编程，一个大项目才能得到只有规范的科学的编程，一个大项目才能得到有效地管理，其质量才有保证。创造性应该发有效地管理，其质量才有保证。创造性应该发挥在适当的地方。挥在适当的地方。6.1 程序设计的基本原则程序设计的基本原则高效的程序员不应该浪费很多的时间用于程序调高效的程序员不应该浪费很多的时间用于程序调试，他们一开始就不要把缺陷引入试，他们一开始就不要把缺陷引入“程序测试是表明故障的非常有效的方法，但对程序测试是表明故障的非常有效的方法，但对于
8、证明没有故障，调试是很无能为力的于证明没有故障，调试是很无能为力的”关于小程序的设计关于小程序的设计n70年代对小程序设计有很多的研究年代对小程序设计有很多的研究n小程序设计是大规模程序正确性的基础。设一小程序设计是大规模程序正确性的基础。设一个大程序是由个大程序是由n个小程序组成，每个程序正确个小程序组成，每个程序正确的概率是的概率是p，那么整个程序正确的概率那么整个程序正确的概率P满足：满足： P0,寻找既寻找既 定值定值x. 若若x在在b中出现多次，任意找到一次即可。有：中出现多次，任意找到一次即可。有：解：解：P : n0 Q : (0 i 0 Q: s = i: 0in: bi要求循
9、环满足下面的不变式和界函数要求循环满足下面的不变式和界函数不变式不变式 : 0i n (s = j: 0j0 x20Q: y1 = y2 = gcd(x1,x2)不变式不变式 ： 0y1 0y2 gcd(y1,y2)=gcd(x1,x2 )界函数界函数 ：y1+y26.3循环语句的设计循环语句的设计解：解： 最大公约数的性质：对任意的最大公约数的性质：对任意的0y1y1 类似有类似有 ： y1 := y1-y2 条件：条件： y1y2得程序如下：得程序如下：6.3循环语句的设计循环语句的设计x10 x20y1,y2 := x1,x2 界函数界函数 ：y1+y2do y1y2 y1 := y1-
10、y2od y1=y2Q: y1 = y2 = gcd(x1,x2)x10 x20y1,y2 := x1,x2 界函数界函数 ：y1+y2do y1 y2 y1 y2 if y1y2 y1 := y1-y2 fiod y1=y2Q: y1 = y2 = gcd(x1,x2)6.3循环语句的设计循环语句的设计例例2：检索一个二维数组：检索一个二维数组：P: order(b0:m-1,0:n-1) n0 m 0Q: (0im 0 jn x=bi,j x b) 即给出一个有序的二维数组（有可能为空）查找即给出一个有序的二维数组（有可能为空）查找x 0 j n-1 ： 0i m 0 j n x不在这里不
11、在这里 i m-1 : (m-i)*n-j+m-i (他表明了未搜索的值的个数和行的个他表明了未搜索的值的个数和行的个数之和数之和) 思考：思考： 中中没有没有m-i 是否可以？是否可以？6.3循环语句的设计循环语句的设计解：初始化语句解：初始化语句 i,j :=0,0; 显然显然 j:=j+1, i:=i+1 都可以使得都可以使得 减小，由减小，由 c1 wp(“j:=j+1”, ) 可得：可得： im j n x bi,j j:=j+1 是是相应的条件相应的条件c1但：但： c1 Q而：而： i:=i+1 只有在只有在 im j=n 时才能执行，因此有：时才能执行，因此有： i m j=n
12、 i,j := i+1,0程序：程序： i,j :=0,0; do im j n x bi,j j:=j+1 im j=n i,j := i+1,0 od6.3循环语句的设计循环语句的设计讨论：讨论：n程序语句应使界函数递减，界函数以什程序语句应使界函数递减，界函数以什么样的轨迹减小决定了该程序的设计，么样的轨迹减小决定了该程序的设计，而界函数的轨迹早已蕴涵在而界函数的轨迹早已蕴涵在 中中了。了。n因此说，一个不变式代表了一个循环语因此说，一个不变式代表了一个循环语句，不同的不变式就可能得出不同的循句，不同的不变式就可能得出不同的循环语句。环语句。ReviewDO循环的验证项目循环的验证项目程
13、序设计的基本原则程序设计的基本原则选择语句的设计原则：语句选择语句的设计原则：语句-条件条件循环语句的设计策略：卫哨先行、走循环语句的设计策略：卫哨先行、走向终止向终止6.4 不变式的构造不变式的构造构造不变式有两类方法：构造不变式有两类方法：1. 削弱削弱Q构造构造 ：n删除删除 Q 的一个合取分量的一个合取分量n替换替换 Q 中的常量为变量中的常量为变量n扩大扩大 Q 中变量的变化范围等中变量的变化范围等2. 联合联合P和和Q构造构造 适合于输入变适合于输入变量的值不因程量的值不因程序的执行而变序的执行而变化的情况化的情况适用于输入变适用于输入变量的值因程序量的值因程序的执行而变化的执行而
14、变化的情况。的情况。6.4 不变式的构造不变式的构造1.气球理论（气球理论（The Balloon Theory）一般情况下，一般情况下， BB = Q , 因此因此Q . 把把Q看成看成一个瘪了气的气球。逐渐放宽对一个瘪了气的气球。逐渐放宽对Q的限制，即削弱的限制，即削弱Q，即将气球吹大，直至包含循环的初始状态（这个即将气球吹大，直至包含循环的初始状态（这个初始状态顶多几条简单赋值和选择语句可以得到）初始状态顶多几条简单赋值和选择语句可以得到）ISQ初始状态nn-110.6.4 不变式的构造不变式的构造 n， n-1，.， 1 ， 0描述了整个吹气的描述了整个吹气的过程，一旦到达边界，就考虑
15、如何泄气使过程，一旦到达边界，就考虑如何泄气使 回到回到Q。这个过程就是设计一个循环，每迭这个过程就是设计一个循环，每迭代一步就漏气一次，最后收缩到代一步就漏气一次，最后收缩到Q的动作。的动作。吹气的过程是设计吹气的过程是设计 的过程，而漏气的过程是的过程，而漏气的过程是设计循环体的过程。因此，将设计不变式的设计循环体的过程。因此，将设计不变式的方法归结为削弱谓词方法归结为削弱谓词Q的过程。的过程。6.4 不变式的构造不变式的构造2. 削弱削弱Q就就 - 删除删除Q的合取分量的合取分量 （AB C可以削弱为可以削弱为AB 或或AC ）策略：假定策略：假定Q是一个合取式，可以试着删除其是一个合取
16、式，可以试着删除其某个合取分量而构造某个合取分量而构造 ，而被删除的分量的否，而被删除的分量的否定式作为循环条件（卫哨）定式作为循环条件（卫哨）c。例例1：写一个程序，对给定的整数：写一个程序，对给定的整数x0，求满求满足如下的关系的足如下的关系的r： Q： 0 r2 x (r+1) 2 即，即，r是不超过是不超过sqrt(x)的最大整数的最大整数。6.4 不变式的构造不变式的构造解：解：P ： x 0Q可写成：可写成：0 r2 r2 x x (r+1) 2从从Q中删除中删除x (r+1) 2，得，得一个可能得不变式一个可能得不变式 ： ： 0 r2 r2 x 由由P， 得初始化语句：得初始化
17、语句： r:=0, 使得使得P r:=0 成立。成立。循环条件：循环条件： c = （x (r+1) 2 ） c =（ x (r+1) 2 ) 得程序：得程序： r:=0 do (r+1) 2 x ? od界函数界函数 ： sqrt（x）- r循环体语句：循环体语句： r:=r+1;6.4 不变式的构造不变式的构造3. 削弱削弱Q就就 - 用变量替换常量用变量替换常量策略：策略：用变量替换用变量替换Q中的有关常量，且给出此变量的适当中的有关常量，且给出此变量的适当变化范围，以此削弱变化范围，以此削弱Q而构造而构造 。例例1：平台问题：对给定的有序（平台问题：对给定的有序（ ）数组）数组b0:n
18、-1,数组数组的平台是一串相等值的序列，要求写一个程序，存的平台是一串相等值的序列，要求写一个程序，存b的最的最长平台的长度于变量长平台的长度于变量L中。即此程序执行后将确立中。即此程序执行后将确立Q： Q: L 是是b0:n-1的最长平台的长度的最长平台的长度解：解：b是有序的，是有序的， 区间区间bj,k是平稳的是平稳的 (bj=bk) Q: ( k:0 kn-L:bk=bk+L-1) ( i: 0 i0 ordered(b0:n-1) : 1 i n L 是是b0:i-1的最长平台的长度的最长平台的长度 界函数界函数 ： n-i6.4 不变式的构造不变式的构造卫哨：卫哨： i n循环初值
19、：循环初值： i,L :=1,1; 可使可使P i,L :=1,1; 成立成立i:=i+1 可使可使 递减，递减， 条件：条件： bi bi-L反之，反之， 当当bi = bi-L时，时，L:=L+1;i:=i+1得程序：得程序： i,L :=1,1;do i n if bi bi-L i:=i+1 ; bi = bi-L L:=L+1;i:=i+1; fi od6.4 不变式的构造不变式的构造例例2：已知：已知 n0, 求整数数组求整数数组 b0:n-1的的和存于和存于S中。有：中。有：nP: n0nQ: S = j: 0jn : bj以变量替换常量：以变量替换常量： ：0i n S =(j
20、: 0ji : bj) : n-i6.4 不变式的构造不变式的构造例例3：写一个程序，对给定的整数：写一个程序，对给定的整数n0，求，求a，使，使R为真：为真： R： a2 n (a+1)2设计不变式：设计不变式： 用用b替换（替换（a+1），），并令并令ab, b n+1, : ab b n+1 a2 n b2 : b-a-1程序：程序： a, b := 0,n+1; do a+1 b d :=(a+b)/2; if d*d n b:=d; fi od6.4 不变式的构造不变式的构造4. 削弱削弱Q就就 -扩大变量的取值范围扩大变量的取值范围 策略：策略： 扩大扩大Q中某些中某些变量的取值范
21、围变量的取值范围 ，以次削弱，以次削弱Q构造构造 。例：令例：令f0:n,g0:n,h0:n是是三个固定的单调上升的整数三个固定的单调上升的整数数组（数组（n0）。）。已知他们存在公共值。写一程序，求最小已知他们存在公共值。写一程序，求最小公共值在公共值在f,g,h中的位置。中的位置。解：解：P: n0 令令i0,j0,k0满足：满足：fi0=gj0=hk0 i j k: ii0 jj0 k fi gj hk 即是最小公共值所处的位置，执行后满足：即是最小公共值所处的位置，执行后满足： Q： i=i0 j=j0 k=k0 ：0 i i0 0 j j0 0 k k0 : i0-i+j0-j+k0
22、-k 6.4 不变式的构造不变式的构造程序：程序：初始语句：初始语句： i,j,k:=0,0,0; do figj fihk i := i+1; gjhkgjfi j := j+1; hkfihkgj k := k+1; od6.4 不变式的构造不变式的构造讨论：讨论： BB = figj fihk gjhkgjfi hkfihkgj BB = （fi=gj=hk） 而而 （ figj gjhk hk0，把数组把数组b0:n-1每个元素每个元素的值变为的值变为m*i+bi,即：即： P： i: 0 in : bi = ui Q: i: 0 in : bi = ui+m*i : 0 j=n i:
23、 0ij : bi=ui+m*i i: j i0.2. 写一程序判断数组写一程序判断数组b0:n-1是否全为是否全为0。应用。应用一个布尔变量一个布尔变量s，结果条件为：结果条件为： Q: s = i: 0 in : bi = 03. 写一程序逆转数组写一程序逆转数组b0:n-1。即假定开始时即假定开始时b=(B0,B1,.,Bn-1),那么终止时那么终止时 b=(Bn-1,Bn-2,., B1,B0)4.写一个程序把整数转换成二进制表示（不带打写一个程序把整数转换成二进制表示（不带打头零），二进制表示用一个数组表示。写出规头零），二进制表示用一个数组表示。写出规范，不变式，界函数范，不变式，界函数SummaryThe Principles for ProgrammingThe strategy for IF command designThe strategies for Loop command designThe techniques for constructing invariant
