某个国家一共发行了a1, a2, a3, …, ak种不同面额的钞票, 为了方便起见, 假设a1 < a2 < … < ak· 现在手上有n, 请问要如何把n兑换成a1, a2, a3, ……, ak这些钞票,使得所用钞票的量为最少

说明: 先说一个最常见的例子, 如果有1元、5元、10元3种, 而又有107元要兑换, 于是a1=1, a2=5, a3=10, n=107。兑换方式很简单, 用面额最大的去除, 那就是最大面额钞票的张数, 比如说n/a3 = 107/10 = 10,亦即10元的10张; 除过之后就会有余数7, 再用次大面额的钞票去除, 得商数1(7/5 = 1), 余数2, 所以5元的一张; 再把余数用第三大面额去除(2/1)得商数2, 余数0, 于是1元的两张, 但余数为0, 于是就没有剩下来的钱了, 因此最后结果是10元10张, 5元1张, 1元两张。假若n=78, 那就是10元7张, 5元1张, 1元3张, 一般书中就是这样讲的, 不过对1元、5元、10元这个例子而言, 倒也是正确。如果钞票的面额是1元、3元、4元(奇怪的数字,是吧?), 要兑换10元呢? 用上面的方法, 有4元两张(104=2,余2)、1元两张, 一共用了4张钞票。但若用两张3元、1张4元, 也兑出了10元, 却只用了3张钞票.

这个例子说明, 寻常所用的方法固然可以兑换钞票, 但钞票张数却不是最少的; 此外问题是, 请写一个程序, 输入a1,a2…, ak钞票面额, 以及n个欲兑换的钱数, 输出钞票张数最少的兑换方式。

解答见make_change.py

已知数组x[]储存了一组整数, 请写一个程序, 找出在数组中连续元素的和中最大的一个。举例而言, 如果有数组[1, 2, -6, 3, -2, 4, -1, 3, 2, -4], 那么连续的元素的和有1 + 2 = 3, 1 + 2 + (-6) = 3, 2 + (-6) = 4, …, 但值最大的就是3 + (-2) + 4 +(-1) + 3 + 2这一段, 值为9. 规定: 和为负值时就定成0, 所以结果永远不为负。这个题目通常叫做最大连续元素和(Maximum Consecutive Sum)问题

说明: 这个问题有个很简单的解法,但效率很低,一般采用效率很高的方法的程序比使用不好的方法的要长。一般人看到这个问题的自然反应就是用两个循环, 如程序所示。

1
2
3
4
5
6
7
8
9

def bad_method(x):
    max_sum = 0
    for i in range(len(x)):
        s = 0
        for j in range(i, 0, -1):
            s += x[j]
            if s > max_sum:
                max_sum = s
    return max_sum

想法是很简单的, 当固定在某个x[i]之后, 把x[i], x[i-1] + x[i], x[i-2] + x[i-1] + x[i], … x[0] + x[1] + … x[i]求出来, 一边算, 一边找出极大值, 这就是上面片段所隐含的意义。但是, 当处理到i时要查i个元素, 所以要把n个数都处理完,就要查1 + 2 + 3 + … + i + … + n = n(n+1)2、与n ** 2成正比的元素了。如果仔细看就会发现做了很多重复的工作, 为什么? 当i是2时,算了x[2], x[1] + x[2], x[0] + x[1] + x[2], 但当i进到下一个位置变成3时, 又算x[3], x[2] + x[3], x[1] + x[2] + x[3], x[O] + x[1] + x[2] + x[3], 于是x[1] + x[2] 与 x[O] + x[1] + x[2]不都是重复算了吗? 因此, 程序如果能够避免这些重复的部分, 就一定会非常快。

解答见maximum_consecutive_sum.py

假设有一个数组, 它有n个元素,每一个不外乎是红、白、蓝3种颜色之一的代号, 就说是R, W, B好了。这些元素在数组中并没有依同样颜色的元素排在一起的方式来排列, 请写一个程序把这些元素排成所有蓝色在前, 然后是白色, 最后是红色的排列方式, 不过在写程序时要满足下面的条件

1. 不能用到额外的内存,换句话说,只能在数组之内用互换的方式完成。
2. 互换两个元素的动作要越少越好
3. 对于每一个元素而言,测试它是红, 白, 还是蓝的工作, 每种颜色最多只能做一次测试

在这个限制之下,请编写一个最快的程序

说明: 有些人很自然地会想到把蓝色当成1、白色当成2、红色当成3, 然后用排大小的程序把次序排出来,自然地蓝色在前, 白色居中, 红色最后了; 完全正确, 不过却违背了规定。也就是说, 互换两个元素的动作是不是太多了呢? 对每一个元素测试它的颜色的行为是否违反了要求呢? 对前者而言,不同的排序方法会有不同数目的互换动作。比如说,如果用选择法, 每次找到计i+1 ~ n中最小的值, 与第i个元素互换, 那么排序的动作只不过用了n-1次互换。但是对第三个限制而言, 就很难保证对每一个元素、每一种颜色都最多只测试次了

第三个条件需要仔细地说明, x[i]表示第i个元素。第三个条件是说, x[i] == R, x[i] == W, x[i] == B 这3个比较的任何一个都最多只能做一次。举个例子, 如果在决定观应该放在什么地方时,上述3个比较都各做一次,是正确的。任取两个或任取一个各做一次,也是正确的。但x[i] == R、x[i] == W、x[i] == R就是错的了, 因为对R的测试做了两次。

其实这个题目并不难, 把数组从头到尾查一次就可以做出结果, 那3个繁琐的条件, 不过是防止去用排序或“不够快”的方法来解题而已。

解答见three_flag.py

请写一个程序, 输入一个正整数的值, 然后列出所有由n个左括号与n个右括号正确成的字符串; 当然, 正确的左, 右括号一定个数一样多, 所以输入的值要是个偶数

说明: 所谓由括号正确地组成的字符串, 指的是如果有一个左括号, 那么在它的右边就一定有一个与它相匹配的右括号。例如,()()、(()),就是仅有的两个有4个符号的, 由括号正确地组成的字符串:()()()、()(())、(())()、(()())、((()))则是5个有6个符号, 由括号正确地组成的字符串。正因为有一个左(或右)括号就一定有相对应的右(或左)括号, 左、右括号成双出现, 因此输入就一定要是偶数, 奇数是不可能的。当输入n之后, 在字符串中左、右括号的个数就各是n/2个。

如何产生这样的字符串呢？下面就是一个有用的想法：如果在产生的过程中已经产生了若干左、右括号，为了要把产生的行为完成，还欠R个左括号、L个右括号，那么有没有办法找出产生下一个括号时L与R的关系呢？记住，递归是一个不容忽视的利器。

解答见generate_parenthesis.py

已知一个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