《编程珠玑》学习笔记-第3、4章

第三章 数据决定程序结构

几个案例：

1、一个调查程序

输入：某学院的学生所填写的近2万份调查表，共25页分别代表8大类，每条记录表示每份调查表；

输出：3页相似输出以及其他密切相关的表，例如拒绝回答每个问题的学生数目。

程序设计：（三视图方法）关键在于用数组来存储数据；数组按照其输出结构或者按照其输入结构来组织。

2、格式信函编程

编写基于格式信函模板的格式信函发生器；$i代表记录中的第i个字段，长字符串数组表示该模板。

发生器+模板程序实现。将数据从控制中分离出来：如果重新设计信函，那么模板可以使用文本编辑器来修改，从而第二个特定页的准备也会简单。

3、其他示例：菜单、出错信息、日期函数、单词分析。

小结：1、用于特殊数据的强大工具：超文本、键值对、电子表格、数据库、特定领域的编程语言。

2、数据结构对软件的贡献：将大程序缩减为小程序。

3、退回七点思考的原则：使用数组重新编写重复代码；封装复杂的结构；尽可能使用高级工具；从数据得出程序的结构。

第四章 编写正确的程序

1、对程序验证进行研究可以加深对计算机编程的基本理解，对于程序维护也至关重要。

2、关于二分搜索的论文在1946年发表，但一个没有错误的二分搜索程序在1962年才出现，可见正确编写二分搜索还是很有挑战的。

3、编写二分搜索程序：首先编写程序框架（引入断言），如下：

initialize range to 0..n-1

loop

{incariant:mustbe(range)}

if range is empty,

 break and report that t is not in the array

compute m,the middle of the range

use m as a probe to shrink the range

if t is found during the shrinking process,

 break and report its position

然后进行初始化l=0,u=n-1；接下来检查空范围([0,n-1])并计算新的中间点m；最后编写伪代码如下：

l=0;u=n-1

loop

{mustbe(l,u)}

if l>u

p=-1;break

m=(l+u)/2

case

x[m]<t:l=m+1

x[m]==t:p=m;break

x[m]>t:u=m-1

程序验证的基本技术：精确定义不变式并在编写每一行代码时随时保持不变式对的成立。

程序验证的基本技术在将算法框架转化为伪代码时起了很大作用。

4、理解程序：

【开发：自上而下；正确性分析：自下而上】

对二分程序进行验证分析，分为三段式：

a. 初始化：循环初次执行的时候不变式为真；

b. 保持：如果在某次迭***始的时候以及循环体执行的时候，不变式都为真，那么，循环体执行完毕的时候不变式依然为真。

c. 终止：循环能够终止，并且可得到期望的结果。

5、原理：

问题很重要，需要认真编写代码，程序开发新需要遵循验证思想，可使用一般性的工具进行程序正确性的分析。

a. 断言：输入、程序变量和输出之间的关系勾勒出程序的状态，断言可以准备阐述这些关系；

b. 顺序控制结构：分析每个分支说明结构的重要性，选择某个分支的事实使用断言来证明；

c. 迭代控制结构：上面提到的三段式；

d. 函数：使用两个断言陈述其目的，前置条件和后置条件。前置条件是在调用该函数之前就应该成立的状态，后置条件的正确性由函数在终止执行时保证。也就是通常说的“契约编程”：如果前置条件满足的情况下调用函数，那么函数的执行将确立后置条件。