推荐订阅源

最近在看编程珠玑这本书。觉得很不错。

第一章介绍的是位图算法。比较简单。就不记笔记了！呵呵偷个懒。

第2章里面有这样的一道题目：

    有一个字符串（这里命名为数组 N）。“abcdefghij”, 将字符串转换成 “defghjabc”。其实就是将 AB 转换成 BA 的过程 这里A =“abc” B=“defghij”。 书上把这个叫做向量旋转。
最常规的方法就是使用一个临时的数组。将 A暂存，将B copy到位后，将暂存的A copy到目标位置上去。 这里也说了这是个最常规的方法。如果A和B都相当巨大，
那在设备内存受限的情况下（比如只能使用几十个字节的而外空间），就没办法实现了。

   现在来说书上的方法。这个方法是由2分法引申来的。 先用文字描述下。

  如果 A 的长度小于 B的长度。 将B分解成 B1 和 B2 。 在上面的那个例子里面就是 B1=“defg” B2=“hij”。 然后使用一个临时变量 t 记录 N[0],
然后将N[i](这里i指AB分割的位置。)移动到N[0],将N[2i] 移动到 N[i], (所有的下标都要对数组的长度取模)。然后依次递归。 

  上面这个是书上的文字描述。我看的晕晕的，就又往下看了看。看到他画了个图才算明白。下面用图示的方法演示下算法的运行过程。

abc | defg | hij   //可以看到 hij 跟 abc 对于数组来说是中心对称的。将 a 跟 h交换 b跟i c跟j 。中间采用一个临时变量
hij | defg | abc  //这样 abc已经到了我们预定的位置了。我们来集中力量处理B的部分。这里其实已经比较明确了，我们将 B1 ,B2 看成 A 和B
hij | d | efg | abc // 好了，下面的就不说了，就是个递归调用的过程了。

整个过程中除了循环计数的变量外，就只使用了一个外部的临时变量。