编程珠玑 笔记

《编程珠玑》这本书无需多说,他的价值不在于这里摘录的只言片语,而在于阅读过程中思维上的学习,在解答习题时思维上的锻炼过程。

第一部分 基础

第一章 开篇

准确的问题描述:输入、输出、约束。在尝试解决问题之前,先将已知条件组织成一种更客观、更易用的形式。

确定用户的真实需求是程序设计的根本。

对小问题的仔细分析有时可以得到明显的实际益处。

简单的设计。法国作家兼飞机设计师 Antoine de Saint-Exupery:设计者确定其设计已经达到了完美的标准不是不能再增加任何东西,而是不能再减少任何东西。

第二章 啊哈!算法

Martin Gardner:看起来很困难的问题也可以有一个简单的、意想不到的答案。

优秀程序员都有点懒:他们坐下来等待灵机一动的出现而不急于使用最开始的想法编程。当然,这必须通过在适当时候开始写代码来加以平衡。真正的技能就在于对这个适当时候的把握,这只能来源于解决问题和反思答案说获得的经验。

第三章 数据决定程序结构

恰当的数据视图实际上决定了程序的结构。

将数据从控制结构中分离会获得许多好处。

能用小程序实现的,就不要编写大程序。

发明家悖论:更一般性的问题也许更容易解决。

程序员在节省空间方面无计可施时,将自己从代码中解脱出来,退回起点并集中心力研究数据,常常能有奇效。(数据的)表示形式上程序设计的根本。

退回起点进行思考时的几条原则:

  • 使用数组重新编写重复代码。冗长的相似代码常常可以使用最简单的数据结构–数组来更好地表述。
  • 封装复杂结构。
  • 尽可能使用高级工具。
  • 从数据得出程序的结构。通过使用恰当的数据结构来替代复杂的代码,从数据可以得出程序的结构。万变不离其宗:在动手编写代码之前,优秀的程序员会彻底理解输入、输出和中间数据结构,并围绕这些结构创建程序。

继续阅读

向量旋转

向量旋转

题目均来自《编程珠玑》。

将一个n元一维向量向左旋转(循环移位)i个位置。例如,当n=8时且i=3时,向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。能否仅用数十个额外直接的存储空间,在正比于n的时间内完成向量的旋转?

旋转操作对应于交换相邻的不同大小的内存块:每当拖动文件中的一块文件到其他地方时,就要求程序交换两块内存中的内容。

两个简单直接的方法

方法一:首先将 x 的前 i 个元素复制到一个临时数组中,然后将余下的 n-i 个元素向左移动 i 个位置,最好将最初的 i 个元素从临时数组中复制到 x 中余下的位置。这种办法使用 i 个额外的位置产生了过大的存储空间的消耗。

方法二:定义一个函数将 i 向左旋转一个位置(其时间正比于 n),然后调用该函数 i 次。该方法产生了过多的运行时间消耗。

下面介绍三种更好的方法。

继续阅读