已知一个n列n行的矩阵M,它的元素满足一个很特殊的性质, 即任一元素M[i][j]都小
于在它右边与下方的元素(如果存在的话), 换言之,M[i][j] < M[i][j+1]且M[i][j] < M[i+1][j]. 现在有一个值K, 编写一个程序, 检查矩阵M中是否有K。

说明: 这个矩阵有了一种很特殊的结构, 换言之, 每一列与每一行都从小到大排列, 所以
做寻找的工作时就可以通过这个特殊的顺序来编写程序。注意, 虽然有n ^ 2个元素, 但理论上可以证明, 在最坏的情况下, 2n - 1就可以决定K在不在M中; 关键所在, 就是如何模仿二分查找法的技巧在一次比较之后就尽可能去掉多余的元素.

解答见matrix_search.py

已知一个整数数组x[], 其中的元素彼此都不相同,而且也已经从小到大排列好,请用
比较大小、相等的方式编写一个程序, 找出给定的数组中是否存在一个元素满足x[i] = i的关
系。举例而言, 如果x[]={-2,-1,3,7,8}, x[3] = 3, 因此 3 就是答案, 因为编程语言中数组是从0开始的，所以最终是检测是否存在一个元素满足x[i] = i + 1.

说明: 用笨方法, 一个循环就可以找出答案, 如下程序所示

1
2
3
4
5
6
7
8
9
10
11

def bad_index_search(x):
    index = -1
    for i in range(0, len(x)):
        if x[i] == i + 1:
            index = i + 1
            break
    return index

if __name__ == "__main__":
    x = [-2, -1, 3, 7, 8]
    print(bad_index_search(x))

这个程序在最坏的情况下, for一共绕了n圈, 作了n次比较, 但却没有用到x[]的元
素已经排列好的条件. 事实上, 如果输入有n个元素, 应该可以写出与log(n)次成正比的比较的程序,关键是x[]的元素是排好顺序的。

解答见index_search.py

对于一个正整数n而言，它的一个分割(Partition),就是把n写成若干个正整数的和，但不计较书写的顺序。编写一个程序，输入n，把n的所有分割显示出来。
说明: 如果n=7, 那么有如下的分割.

7

6 1

5 2

5 1 1

4 3

4 2 1

4 1 1 1

3 3 1

3 2 2

3 2 1 1

3 1 1 1 1

2 2 2 1

2 2 1 1 1

2 1 1 1 1 1

1 1 1 1 1 1 1

一共有15个，仔细观察在各个输出中前后两者的差异，并且自己做一做其他的结果(比如n=5时有7个，n = 6时有11个等),就不难写出程序了。

将整数的所有不同分割数目递归解稍加改变，就可以得到一个递归解，解答见integer_partition_method.py

所谓的整数的分割(Partition of an Integer), 指的就是把一个正整数写成若干个正整数的和，但这里只计较有多少种分割方式，而不计较它的内容。例如，4=3+1,2+2,2+1+1,1+1+1+1+1, 再加上自己，就一共有5种分割方式。编写一个程序，输入一个正整数，输出它有多少种分割方式。

说明: 以下是几点重要的提示

1. 要把n进行分割，其实不完全只针对n, 还要看分割中最大的值是什么。例如，要把10进行分割，若在分割中最大的值是6，即10=6+…, 那么”…”的部分充其量的值是4而已，不仅如此，和还须等于4；因此，如果知道”…”, 即4有多少种分割方式，也正是在分割10时，最大值为6的分割方式！
2. 应该分析一下n这个输入值，与在分割中的极大值(如1.中的6)之间有什么联系，找出来，问题就解决了。

在C语言名题精选百则之整数的所有不同分割数目中得到一个递归解，我们可以将它转换成非递归解

解答见iteration_integer_partition.py

所谓的整数的分割(Partition of an Integer), 指的就是把一个正整数写成若干个正整数的和，但这里只计较有多少种分割方式，而不计较它的内容。例如，4=3+1,2+2,2+1+1,1+1+1+1+1, 再加上自己，就一共有5种分割方式。编写一个程序，输入一个正整数，输出它有多少种分割方式。

说明: 以下是几点重要的提示

1. 要把n进行分割，其实不完全只针对n, 还要看分割中最大的值是什么。例如，要把10进行分割，若在分割中最大的值是6，即10=6+…, 那么”…”的部分充其量的值是4而已，不仅如此，和还须等于4；因此，如果知道”…”, 即4有多少种分割方式，也正是在分割10时，最大值为6的分割方式！
2. 应该分析一下n这个输入值，与在分割中的极大值(如1.中的6)之间有什么联系，找出来，问题就解决了。
3. 不要忘了，递归是非常有效的武器

解答见integer_partition.py

编写一个程序,列出{1, 2, 3, … , n}这个集合的所有子集, 包括空集合.

说明: 列出一个集合的所有子集有很多做法,题目中并没有要求依某个特定的次序来排列,
因此是不难做出来的。 因为集合中一共有n个元素,所以总共就会有2 ^ n 个子集; 例如{1, 2, 3} 有如下子集: {} {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}

这里没有要求顺序，所以方法很多，随便选一种. 解答见direct.py

在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