第六章 程序设计基本方法w主要内容：n引言-程序设计的基本原则n选择语句的设计n循环语句的设计n循环不变式的设计n界函数的设计6.1 程序设计的基本原则wPrinciple 1: A program and its proof should be developed hand in hand, with the proof usually leading the way,一个程序和它的正确性证明应同时设计，并且最 好以考虑证明为先导。 wPrinciple 2：使用理论来提供正确性的理解，而 在适当的地方用常识和直观方法，但当出现困难 和复杂情况时，仍然依据形式理论作保证。当然 一个人只有既有常识又掌握理论才能有效地在形 式化和常识之间进行协调，前者是程序员一直在 使用。6.1 程序设计的基本原则wPrinciple 3：要了解将用程序来处理的 对象的性质。 w例：假设有一袋装有黑白两色棋子。每 次从袋中任取两粒子，若它们同色，则 丢掉这两粒子，然后再补进一只黑子， 否则丢掉黑子，放回白子。连续执行这 一步骤，直至袋中只剩下一子为止。试 问最后这一子是黑或白？编一程序回答 此问题。6.1 程序设计的基本原则wPrinciple 4：不要忽视任何看起来十分明显的原 则，只有通过有意识地运用这些原则才会获得成 功。 wPrinciple 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. wPrinciple 6:在着手编程之前，首先要弄清楚问 题是要求“做什么”的，并将其抽象化为前置条件 和后置条件，即给出精确的程序规范，且勿仓促 编码。6.1 程序设计的基本原则wPrinciple 7: 程序设计是一种面向目标的设计活动。 即程序设计是围绕着目标Q进行的，这意味着Q起着 比P更重要的作用。 w关于证明和测试数据分析n边进行程序设计，边写下有关的测试数据。关键在 于有效地选择和生成测试数据集；n从工程角度看，测试是重要的；n但从人员培训的角度看，应该训练程序员具有编制 正确程序的能力；n因此，学习和研究形式证明技术是培养能力的一种 有效的途径n测试只能证明程序有错，并不能证明程序是正确的 。Testw对程序员的科学训练是十分重要的，有人曾 做过一个试验：一个题目由一批印度的程序 员和中国的程序员来做，结果如何？n由一批印度程序员来做，其结果惊人地相似；n而由一批中国程序员来做，编出的程序五花八门 。w只有规范的科学的编程，一个大项目才能得 到有效地管理，其质量才有保证。创造性应 该发挥在适当的地方。6.1 程序设计的基本原则 高效的程序员不应该浪费很多的时间用于程序 调试，他们一开始就不要把缺陷引入 “程序测试是表明故障的非常有效的方法，但对 于证明没有故障，调试是很无能为力的”w关于小程序的设计n70年代对小程序设计有很多的研究n小程序设计是大规模程序正确性的基础。设 一个大程序是由n个小程序组成，每个程序正 确的概率是p，那么整个程序正确的概率P满 足： P0,寻找 既 定值x. 若x在b中出现多次，任意找到一次即可。有 ： w解：P : n0Q : (0 i 0Q: s = i: 0i0 x20 Q: y1 = y2 = gcd(x1,x2) 不变式： 0y1类似有 ： y1 := y1-y2 条件： y1y2 w得程序如下：6.3循环语句的设计x10 x20 y1,y2 := x1,x2 界函数：y1+y2 do y1y2 y1 := y1-y2 od y1=y2 Q: y1 = y2 = gcd(x1,x2)x10 x20 y1,y2 := x1,x2 界函数：y1+y2 do y1 y2 y1 y2 if y1y2 y1 := y1-y2fi od y1=y2 Q: y1 = y2 = gcd(x1,x2)6.3循环语句的设计w例2：检索一个二维数组： P: order(b0:m-1,0:n-1) n0 m 0 Q: (0i0 ordered(b0:n-1): 1 i n L 是b0:i-1的最长平台的长度界函数 ： n-i6.4 不变式的构造卫哨： i n循环初值： 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;fiod6.4 不变式的构造w例2：已知 n0, 求整数数组 b0:n-1的 和存于S中。有：nP: n0nQ: S = j: 0jn b:=d;fiod6.4 不变式的构造4. 削弱Q就-扩大变量的取值范围 策略： 扩大Q中某些变量的取值范围 ，以次削弱Q构造 。 例：令f0:n,g0:n,h0:n是三个固定的单调上升的整 数数组（n0）。已知他们存在公共值。写一程序，求 最小公共值在f,g,h中的位置。 解：P: n0令i0,j0,k0满足：fi0=gj0=hk0 ijk: i fi gj hk 即是最小公共值所处的位置，执行后满足：Q： i=i0 j=j0 k=k0 ：0 i i0 0 j j0 0 k k0 : i0-i+j0-j+k0-k 6.4 不变式的构造w程序： w初始语句： i,j,k:=0,0,0; w do fi0，把数组b0:n-1每个元素 的值变为m*i+bi,即：P： i: 0 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) w写一个程序把整数转换成二进制表示（不带打 头零），二进制表示用一个数组表示。写出规 范，不变式，界函数SummarywThe Principles for Programming wThe strategy for IF command design wThe strategies for Loop command design wThe techniques for constructing invariant