在C语言名题精选百则之产生所有排列字典顺序递归解说过，产生所有排列还有非递归解。

如何产生字典顺序的排列呢? 据Hall与 Knuth的考证, 200年(1812年)前Fischer与Kruse在他们的一本书中就已经提过这样的方法了。从1234…n开始,首先从右到左出第一对满足a(i) < a(i+1) 的a(i)与a(i+1),于是从a(i+1)起在它右边的就是越来越小的:有了a(i)之后再一次地从右到左查一次, 找出第一个满足a(i)< a(j)的a(j)。接着把a(i+1)到a(n)的各个元素反过来排, 就是字典顺序的下一个了。下面来看看如何找出153642的下一个:从右到左第一组满足a(i) < a(i+1)的是3与6,所以a(i),就是3。接着从右到左去找第一个a(j),使得a(i) < a(j),则是3 < 4; 把a(i)和a(j)换下位置，最后把a(i+1)与a(n)之间的元素反过来排,因此得到154236,这就是结果。

1. i = n - 1
2. 从右往左找，找到第一个i使得a(i) < a(i+1)
3. 从右往左找，找到第一个j使得a(i) < a(j)
4. 交换a(i)与a(j)
5. 将a(i+1),…a(n)反转
6. 回到第2步

如果找不到满足条件的i, 则结束程序。

例如153642, 从右往左找，找到第一个 i = 2 使得a(i) < a(i+1) 即3 < 6, 从右往左找，找到第一个 j = 3 使得a(i) < a(j) 即 3 < 4 交换a(i)和(j), 得到154632, 将a(i+1),..a(n)反转，即将632反转，得到154236, 所以154236就是153642的下一个排列。

解答见iteration_permutation.py

编写一个程序,用字典顺序列出n个元素的所有排列(Permutation)

说明:
下面是一个n = 4，用字典顺序列出来的所有排列，一共为4! = 24个。

1234 2134 3124 4123

1243 2143 3142 4132

1324 2314 3214 4213

1342 2341 3241 4231

1423 2413 3412 4312

1432 2431 3421 4321

字典顺序的先后是这样定义的, 如果a(1)a(2)…a(n)与b(1)b(2)…b(n)是n个元素的两个排列于是有a(1)=b(1), a(2)=b(2),…a(i)=b(i),但a(i+1)<b(i+1), 就是说a(1)a(2)a(n)。在b(1)b(2)b(n)的前面,或者说前者较”小”; 注意,自i+2个之后的各个元素是没有影响的。其实, 这就是用来决定字符串大小的方式。举例而言, 2314与2341,前两个元素相同,但第三个为1<4,所以2314在前, 2341在后; 同理, 1234与4321相比, 1234在前,4321在后。

如何产生字典顺序的排列呢? 据Hall与 Knuth的考证, 200年(1812年)前Fischer与Kruse在他们的一本书中就已经提过这样的方法了。从1234…n开始,首先从右到左出第一对满足a(i)<a(i+1)的a(i)与a(i+1),于是从a(i+1)起在它右边的就是越来越小的:有了a(i)之后再一次地从右到左查一次,找出第一个满足a(i)< a(j)的a(j)。接着把a(i+1)到a(n)的各个元素反过来排, 就是字典顺序的下一个了。下面来看看如何找出153642的下一个:从右到左第一组满足a(i) < a(i+1)的是3与6,所以a(i),就是3。接着从右到左去找第一个a(j),使得a(i) < a(j),则是3 < 4; 最后把3与4之间的元素反过来排,因此得到154632,这就是结果。

看另一个递归的做法。看上面4! = 24个排列的第一列，它们的第一个元素都是1，第一列的最后一个是以1开头，用字典顺序排出来的最后，自然是1432.事实上，如果是n个元素的排列，以1开头的最后一个应该是1n(n-1)…432。下一列是2开头，把n(n-1)…432中最小的一个与第一个互换，也就是把倒数第一个与第一个互换，得到2n(n-1)..431，但这不是1n(n-1)…432的下一个，但是如果把后面的n - 1个元素反过来，就会得到2134…(n-1)n，是正确的顺序，于是进入第二列。

第二列的最后一个应该是2n(n-1)…431,把 n(n-1)…431中最小的与第一个互换，但因为1已经出现过了，所以把倒数第二个元素(自然是3)与第一个互换，得到3n(n-1)…421，再把后面的n - 1个元素反过来，得到3124…(n-1)n，就得到第三列的第一个。

第三列的最后一个是3n(n-1)…421, 把n(n-1)…421中最小的与第一个互换，但因为1，2已经出现过了，所以把倒数第3个元素(自然是4)与第一个互换，得到4n(n-1)…321，再将后面n - 1个反过来排，得到4123…(n - 1)n，正好是第4列的第一个元素。

于是我们可以得到一个递归的做法，从1234…n起，用一个递归的程序

1. i = n
2. 对后面n - 1个进行排列(递归的)
3. 把第i位与第1位互换
4. i减去1
5. 把后面的n - 1位反过来排
6. 回到第2步

当i到第一位时程序结束。

解答见recursion_permutation.py

编写一个程序, 读入一个正整数, 把所有那些连续的和为给定的正整数的正整数找出来。例如,如果输入27, 发现2~7、8~10、13与14的和是27, 这就是解答:如果输入的是10000, 应该有18~142、297~1328、388~412、1998~2002这4组。注意, 不见得一定会有答案,譬如说4、16就无解; 另外, 排除只有一个数的情况, 否则每一个输入就都至少有一个答案, 就是它自己.

说明: 任何人看到这个题目都会马上想到一个办法, 把所有的和算出来, 与输入比较。曾经看到过如下的一个解法, 如下程序所示

1
2
3
4
5
6
7
8
9
10

def bad_given_sum(n):
    result = []
    mid = int(n / 2)
    for i in range(1, mid + 1):
        s = i
        for j in range(i + 1, mid + 1 + 1):
            s += j
            if s == n:
                result.append((i, j))
    return result

它的做法是先固定一个i, sum变量, 接着令j 从i + 1起变化, 每次都把j的值加到sum 中，
因此sum中的值就是i, i + 1,…,这些连续整数的和. 因此令i 从1 编导n / 2(n是给定的数), 而j从计1变到n / 2 + 1, 如果有一个和与n相同, 就显示i与j,表示n的值是i到j这一串连续的正整数的和。为什么i要从1到n / 2? 很简单, 如果i是n / 2,下一个数就是n / 2 + 1, 于是这两个(连续的)数的和n / 2 + (n / 2 + 1) = n + 1就大于n, 所以i最多只能到n / 2; 同理可以说明j 不可以大过n / 2 + 1

这个程序当然是对的, 但运行太慢了! 用10000作为输入, 它一共执行了311.71秒, 也就是5分钟多: 但事实上, 这个题目可以在不到一秒之内得出答案, 而且当输入1000000(100万)时,也不过用178.12秒(3分钟)左右而已,相比之下bad_given_sum的效率实在太低了。(本书写于1988年，那时候计算机性能还不够好)

问题出在什么地方? 加法次数太多了。在上面的程序中, i与j的关系永远满足1 <= i <= n / 2, i + 1 <= j <= n / 2 + 1, i < j, 每一组i与j都会做一次加法,所以就一共做了大约n ^ 2 / 8个加法(这是个近似值); 当n = 10000时,就大约是1250万个。

不过, 一个好程序员应该研究是否有更好的方法存在, 事实上就有一个, 大约需要2n
个加法就足够了, 能想得出来吗? 下面是几点有用的提示:

1. 如果在求和时是用i + (i + 1) + … + j表示, 那么 i <= n / 2; 这是上面提过的。
2. 如果某个和i + (i + 1) + … + j比给定的值大, 那么把和变小, 但仍然维持是一串连
   续整数的和时, 拿掉j变成i + (i + 1) + … + (j - 1),不如拿掉i变成(i + 1) + … + j。为什么? 因为j比i大, 拿掉j, 和就下降太快了, 不如拿掉i, 再慢慢降低(能用数学来证明吗?)
3. 如果和i + (i + 1) + … + j比给定值小, 加上j + 1变成的i + … + j + j + 1; 道理同前。

有了这几点, 编程应该不会是件难事了。

解答见given_sum.py

继续讨论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