《编程珠玑》读书笔记一

##编程珠玑
###**第一章 开篇**
> 正确的问题。
正确的问题是解决问题的第一步也是最重要的一步。
>位图。 多趟算法。 简单的设计。
程序设计的阶段：
>1. 定义问题（最好形式化为：**输入、输出和约束**）
>2. 程序设计
>3. 实现概要。
###**第二章 啊哈！算法**
>问题A：在一个很大的文件中搜索一个元素
首先介绍了用处非常广的“**二分搜索**”算法。二分搜索并不只用于查找有序数组中元素的位置，而是一种将处理范围缩小的思想。比如求根程序（对分法），比如程序调试（当有一段很长的代码需要调试的时候，显然从中间找更容易定位，当然，首先还是要确认输入无误）。
>问题B：左旋转数组。即对于"abcdefg"，左旋转3个位置，可得"defgabc"。
使用“翻手代码”，即通过下面的代码解决问题：
 
 reverse(0, i-1); // "cbadefg"
 reverse(i, n); // "cbagfed"
 reverse(0, n); // "defgabc"
作者Jon Bentley认为这可以作为一种“常识代码”。
> 问题C： 在一个字典中，找到所有的变位词。像"pots", "stop", "tops"互为变位词。
找到变位词，就需要将找到变位词的共同的东西，我们这里将其称为标记。然后根据标记，将相同标记的单词聚集在一起。
> 问题解决者的观点。优秀的程序员都有点懒，他们坐下来等待灵机一动的出现而不急于用最开始的想法编程。
最开始的很有可能并没有考虑周全，所以，当很快得到一个解决方案时，再花上15分钟来想想是不是有更好的方法是很值得的。
### 第三章 数据决定程序结构
>恰当的数据视图实际上决定了程序的结构。
关于数据结构还有一种说法（忘记是哪位大神了），给我看你的数据视图，而不是代码，我就知道这份代码做了什么事情。
> 能用小程序实现的，就不要用大程序
借助合适的数据结构，将大程序缩减为小程序。
>程序员在节省空间方面无计可施时，将自己从代码中解脱出来，退回起点并集中心力研究数据，常常有奇效。数据的表现形式是程序设计的根本。
退回起点思考的几条原则：
>1. 使用数组重新编写重复代码
>
>2. 封装复杂数据结构
>3. 尽可能使用高级工具如超文本、数据库等
>
>4. 从数据得出程序的结构。 在动手编写代码之前，优秀的程序员会彻底理解输入、输出和中间数据结构，并围绕这些结构创建程序。
### 第四章 编写正确的程序
编程珠玑共有两章留给我的印象最深，其一便是这章***编写正确的程序**。*
由于自己行业比较特殊，所以公司对程序的正确性要求较高。不仅需要开发者编写单元测试验证，还要有专门的测试人员对子系统测试，系统测试。不过尽管存在这么多测试，也无法保证通过测试的代码是正确无误的。所以脑袋里就一直会想，有什么方法可以保证程序一定是正确的？能不能像证明公式一样**证明**程序是正确的？不幸的是，现在并没有一种方法可以证明程序是无误的。不过这一章介绍了如何“*编写**正确**的程序*”，帮助我们更加接近“正确的程序”。
程序验证的一些基本原理：
> 断言，输入。
>
> 验证loop：
> >1. 确认由初始化得到的循环不变式
> >2. 每次迭代保持不变式为真
> >3. 无论循环合适终止， 所得的结果都是正确的。 当然，还要证明loop一定会终止。
> 验证函数： 首先使用两个断言陈述目的。前置条件是调用函数之前就应该成立的状态，后置条件的正确性由函数在终止执行时保证。 由于这些条件像函数跟调用者之间的契约，因此也被称为“***契约编程***”。
### 第五章 编程小事
明智的程序员会使用脚手架（scaffolding）来方便的访问函数。
> 编程：先用伪代码构建程序框架，再将伪代码转换为从程序。
> 通过手动测试来运行完成的函数。
> 通过断言保证函数的输入是正确的。
> 自动测试
> 计时脚手架
在平时工作中，已经需要这样做了，所以并没有太多的感触。