继续讨论Fibonacci 数列问题。在非递归的Fibonacci 程序中，在算f(n)时最多不超过n - 2个加法, 编写一个速度更快的程序，或许可以用乘法。如果每一个乘法用m单位时间, 每一个加法用p单位时间，于是非递归的写法因为最多有n - 2个加法，因此最多用(n-2)p时间。请问，改善的程序要用多少时间？假设只考虑加法与乘法而已。

说明: 解决这个问题的技巧不少，在此先提示一个很容易理解的方法。用矩阵来算，看下面的式子:

(f(n), f(n-1)) = ((1, 1), (1, 0)) * (f(n-1)), f(n-2)), n > 2
相信不难看出这个式子是对的，其实这只不过是把: f(n) = f(n-1) + f(n-2), f(n-1) = f(n-1)写成矩阵的形式而已。

将上式展开:
(f(n-1),f(n-2)) = ((1, 1), (1, 0))(((1, 1), (1, 0)) (f(n-2), f(n-3))) = ((1, 1), (1, 0)) ^ 2 * (f(n-2), f(n-3))

一般而言，有:
(f(n), f(n-1)) = ((1, 1),(1,0)) ^ i (f(n-i), f(n-i-1))
继续展开会得到:
(f(n), f(n-1))=((1,1),(1,0))^(n-2) (f(2), f(1)) = ((1,1),(1,0))^(n-2) * (1, 1)

可以用这个观点来编写程序。

解答见iteration_fibonacci.py

Fibonacci数列f(1),f(2),…,f(n)的定义是:

1. f(n) = 1 当 n = 1或n = 2时
2. f(n) = f(n-1) + f(n-2) 当n > 2时

不用递归的方法, 也不用数组, 编写一个函数, 它接收n的值, 返回f(n)。

说明: 用递归方法算 Fibonacci数列效率是很低的, 要计算很多个重复的加法, 这个题目要求不用递归, 不用数组, 把f(n)求出来。 不过应注意下面的事项:

1. 递归方式并非全然不好,但不能直接套用公式。
2. 因为当n > 2时,f(n) = f(n-1) + f(n-2),所以程序只保留f(n-1)与f(n-2)就可以算出f(n)。

解答见iteration_fibonacci.py

继续求m ^ n 问题(m与n是正整数)。前面的数值自乘递归解会得到一个递归的程序,请编制一个运算效率同样高的非递归的程序。

说明: 或许读者有自己独特的看法, 但在此提供一个简单的建议, 可以采用它来编写程序, 当然也可以把它化简。建议是把指数n用二进制来看, 比如若n=13, 那么13(10进制)=1101(2进制)=2 ^ 3 + 2 ^ 1 + 2 ^ 0, 所以求m ^ (2 ^ 3 + 2 ^ 1 + 2 ^ 0)时就相当于求m ^ (2 ^ 3) m ^ (2 ^ 2) m ^ (2 ^ 0);会发现二进制表示中对应那一位是1, 在m中就有那么一项。把这个观念编制成程序。

另外一个办法是可以把递归解法中每一个递归步骤的n提出来,看在什么时候用(m ^ k) ^ 2,什么时候用m(m ^ 2k),然后用非递归方式写出来。

了解了这些观点之后,编写这个程序就不难了。在编写完程序之后,还应该分析一下程序乘了多少次。

解答见iteration_power.py

如果n与m是正整数, 那么m ^ n 就是把m连乘n次, 这是一个效率很低的方法，请写一个计算效率高的程序 ，并且分析城中一共用了多少个乘法，应该以n - 1个乘法作为设计准则。

说明: 这是一个典型的递归设计题目，应该注意一下几点

1. 试用分而治之(Divide and Conquere)的策略
2. 注意到x ^ 4可以用x ^ 2自乘的关系，由此可以大量地降低乘法数目
3. 连乘n次要n - 1个乘法，能做到只要2log(n)个乘法吗？

解答见recursion_power.py

编写一个程序, 读入一个正整数, 把它的所有质因子找出来。例如, 如果输入的是72 = (2 ^ 3) (3 ^ 2),于是质因子就有 2 与 3, 如果输入的是181944, 181944 = (2 ^ 3) (3 ^ 2) 7 (19 ^ 2), 因子为2、3、7与19。为了方便起见,(2 ^ 3) (3 ^ 2) 7 * (19 ^ 2)可以用2(3)3(2)7(1)19(2)作为输出形式, 也就是说,如果分解开来有a ^ b,输出时就是a(b)。

说明: 传统的做法是把输入值(假设是n)用2去除,一直到除不尽为止。如果一共除了i次就有2 ^ i这一项,输出中就会出现2(i); 接着再用3去除、5去除、7去除等,直到商数变成1为止。以181944为例,第一次用2除得到93972, 再除一次是46896, 第三次得到23493,于是2就不能整除了。下来用3去除, 第一次得到7831, 第二次是2527, 第三次就不能整除。对于2527而言, 用7去除得到361, 再用7就除不尽了, 其次的11、13、15、17也都除不尽; 但19可以, 再用19去除得19; 最后用19除, 商为1, 不能再除了,因此就得到181944 = (2 ^ 3) (3 ^ 2) 7 * (19 ^ 2)的结果。试用这个概念来编写程序。

解答见factor.py

求质数是一个很普遍的问题, 通常不外乎用数去除, 到除不尽时, 给定的数就是质数。但是早在2000年前人们就知道了一个不必用除法而找出2~N的质数的所有方法了。假设有一个很神奇的筛子, 可以给出一个数,例如 i,这个筛子有办法把 i 的所有倍数去掉。请用这个方法求出2~N之间的所有质数。这个方法称为 Eratosthenes(人名)筛法(Sieve Mothod)

说明:下面通过一个例子来加强对筛法的印象,求出2~40之间的质数。首先,把2~40这
些数一字排开:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

2是质数, 所以把2的倍数都筛掉

3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39

下一个数自然是质数3, 所以把3的倍数都筛掉

5 7 11 13 17 19 23 25 29 31 35 37

下一个是5, 把5的倍数筛掉

7 11 13 17 19 23 29 31 37

下一个是7, 把7的倍数筛掉(其实在此之前都已经筛掉了)

11 13 17 19 23 29 31 37

再下来是11, 比20/2大了, 所以工作停止, 没有被筛掉的就是质数, 它们是2,3.5,
7,11,13,17,19,23,29,31,37。

可以按照这一逻辑来编写程序,但是需注意下面几点:

1. 2是质数,所以2的倍数是一定会被删除的,所以在一开始时根本没有把2的倍
   数放到筛子中的必要,这就省下了一半的空间。

2. 如果要求2~N之间的质数,做到N/2就可以停下来,因为大过N/2的数都不可
   能整除N

3. 程序不可以使用乘法与除法,只能用加或减,以求加快速度。

请基于这3项要求来编制程序。

解答见sieve.py

试编写一个程序，找出前 N(如200)个质数。如果没有进一步要求，这不是难题。但再次希望从所知的、使用除法的方法中，用最快的办法来编写程序.

说明: 可能最先想到的办法，就是让某个变量 i 从 2 变到 N，然后检查它是不是质数，如果是就显示出来，如果不是，就检查下一个。这是正确的做法，但却没有注意到一个小细节，因而使程序运行速度变慢。当然，2是质数，但所有 2 的倍数都不是质数，如果令 i 从 2 变到 N, 不就很冤枉的测试了 4,6,8,10,…这些数? 所以第一点提示是测试 2,3,5,7,…,N, 即 2 与所有奇数就足够了。同理，3 是质数，但 6,9,12,…这些3的倍数却不是，因此，如果能把 2 与 3的倍数都跳过去而不测试，任意连续的 6个数中，就只会测试两个而已。以6n,6n + 1,6n + 2, 6n + 3, 6n + 4, 6n + 5为例，6n, 6n + 2, 6n + 4是偶数, 6n + 3是3的倍数, 所以如果把 2 与 3 的倍数都不理会，要测试的数就只留下6n + 1与6n + 5而已，因而工作量之时前述想法的2 / 6 = 1/3, 应该用这个办法去编写程序。

假如i 是如上述的一个数(不是2 与 3 的倍数), 如何测试 i 是个质数呢? 按照定义 i 如果是质数, 也就只有 1 与 i 可以除尽自己，所以可以用2, 3, 4, 5, 6, …, i - 1去除 i, 如果都除不尽(余数不是0), i 就是质数。观点也对，但却与上一点一样地笨拙。当 i > 2 时，有哪一个数 i 可以被 i - 1除尽的? 没有, 为什么? 如果 i 不是质数, 那么 i = a b, 此地 a 与 b 既不是 i 又不是 1; 正因为 a > 1, a 至少是2， 因此 b 最多是 i / 2而已，去除 i 的数用不着是 2,3,4,…,i - 1, 而用 2,3,4,…, i / 2就可以了。 不但如此，因为 i = a b, a 与 b 不能大于sqrt(i)(即i的平凡根), 为什么呢? 如果a > i 的平方根, b > i 的平方根, 于是a * b > i, 因此就都不能整除i了。如果 i 不是质数, 它的最大因子就是sqrt(i)； 换言之，用2,3,4,5,…,sqrt(i)去除 i 就行了。

但是, 用2,3,4,5,…,sqrt(i)去除i也是个浪费。就像前一段所说的，2除不尽，2的倍数也除不尽；同理 3 除不尽，3 的倍数也除不尽……最理想的方法就是用质数去除 i, 因为在前一段的提示， i 不是 2 与 3的倍数，所以就用5, 7, 11, 13, 17, 19,…这些比sqrt(i)小的质数去除 i 即可。

但问题是这些质数从何而来? 这比较简单，可以准备一个数组prime[], 用于存放找出来的质数, 一开始它应该有2 、3与5。于是当 i = 5,7,11,13,17,19,23,25,29,…这些不是 2 与 3 的倍数时，就用prime[]中小于 sqrt(i)的数去除 i 即可，如果都除不尽，i 就是质数，把它放入prime[]中，因此prime[]中的质数就会越来越多，直到满足所要的个数为止。

不妨用这段说明来编写程序，不过应注意下面几点:

1. 不要处理2 与 3 的倍数(见第一段)
2. 用质数去除(见第二、三段).
3. 用i的平方根可能会有问题，为什么?有什么办法可以解决?

解答见prime_one.py

假设有一个数组x[ ], 它有n个元素，每一个都大于零，称x[0] + x[1] + … + x[i]为前置和(Prefix Sum),而 x[j] + x[j + 1] + … + x[n - 1]为后置和(Suffix Sum)。试编写一个程序，求出x[ ] 中有多少组相同的前置和与后置和。

说明: 如果x[ ] 的元素是3，6，2，1，4，5，2，则x[ ]的前置和有一下7个，即3，9，11，12，16，21，23；后置和则是2，7，11，12，14，20，23；于是11，12，与23这3对就是值相同的前置和与后置和，因为：

11 = 3 + 6 + 2(前置和) = 2 + 5 + 4 (后置和)

12 = 3 + 6 + 2 + 1(前置和) = 2 + 5 + 4 + 1 (后置和)

因为23是整个数组元素的和，因此前置和与后置和一定相同。

当然，也可以用上面的方法把前置和与后置和都算出来(两者都是从小到大的递增序列, 为什么?), 再进行比较, 但建议不要使用这种方法, 因为它需要额外的内存。

假设有一个数组x[ ], 它有n个元素，每一个都大于零，称x[0] + x[1] + … + x[i]为前置和(Prefix Sum),而 x[j] + x[j + 1] + … + x[n - 1]为后置和(Suffix Sum)。试编写一个程序，求出x[ ] 中有多少组相同的前置和与后置和。

说明: 如果x[ ] 的元素是3，6，2，1，4，5，2，则x[ ]的前置和有一下7个，即3，9，11，12，16，21，23；后置和则是2，7，11，12，14，20，23；于是11，12，与23这3对就是值相同的前置和与后置和，因为：

11 = 3 + 6 + 2(前置和) = 2 + 5 + 4 (后置和)

12 = 3 + 6 + 2 + 1(前置和) = 2 + 5 + 4 + 1 (后置和)

因为23是整个数组元素的和，因此前置和与后置和一定相同。

当然，也可以用上面的方法把前置和与后置和都算出来(两者都是从小到大的递增序列, 为什么?), 再进行比较, 但建议不要使用这种方法, 因为它需要额外的内存。

可以用变量prefix来表示前置和，用suffix来表示后置和，用i表示前置和累加元素的位置，i从前往后加，用j表示后置和累加元素的位置, j从后往前加。当prefix > suffix时，累加后置和，也就是j向前走；当prefix < suffix时，累加前置和，也就是i往后走；当prefix == suffix时，同时累加前置和与后置和，也就是i往后走，j往前走. 解答见head_tail.py

已知两个元素从小到大排列的数组x[]与y[],请编写一个程序算出两个数组元素彼此之间差的绝对值最小的一个树，此值称为数组的距离。

说明： 如果x[i]与y[i]是两个元素，那么 |x[i] - y[i]| 就是这两个元素之间的距离，所有这些距离的最小值，称为数组的距离。比如说x[]有1，3，5，7，9， y[]有2，6，8，那么最短距离就是1，因为x[0]与y[0]、 x[1]与y[0]、x[2]与y[1]、x[3]与y[1]、还有x[4]与y[2]的距离都是1。

注意，如果x[]与y[]各有m与n个元素，那么元素之间的距离就一共有m * n个; 事实上往往用不着这么多个值，应该活用x[]与y[]已经排列好的特性，不要把所有的距离都算出来。

依然是利用数组已经排好序的特性。解答见min_dist.py

已知两个整数数组f[]与g[]，它们的元素都已经从小到大排列好，而且两个数组中的元素都各不相同。例如，f[]中有1,3,4,7,9,而g[]中有3,5,7,8,10。试编写程序算出这两个数组之间有多少组相同的元素。

就上例而言, f[2]和g[1]为3是一组; f[3]与g[2]为7是第二组

说明: 建议不要使用下面的方法来编程

1. 固定f[i]
2. 对于f[i]而言，检查g[]中是否有与f[i]相同的元素
3. 处理下一个f[i], 即f[i + 1]

因为f[]与g[]都已经从小到大排列好，所以应该活用这一个很强的特性。一个好的程序员绝对不应用上面的笨拙方法来编写程序, 这样会做太多无意义的事。为什么呢？因为g[]的元素都相异，对于f[i]而言，最多只会找出一个与它相同的元素，最坏的情况时把g[]全部查完才找出相同元素(如果采用上面的方法), 如果g[]中有n个元素，需要查n次; 但是若f[]中也有n个元素，那么需要把g[]查n遍，一共作n ** 2(Python的记法，即n的2次方)次比较才能找出结果。

试着找出一种方法，把f[]与g[]各查一次就可以得到答案(记住, 活用f[]与g[]已经从小到大排列的特性).

做完这一题后，建议继续作下一题。

依然是利用已经排好序的这个特性。解答见eq_count.py