已知一个整数数组x, 对于任何一个元素x[i]而言, 在x[i]右边, 而且值不比x[i]小的元素(亦即j > i而且x[j] >= x[i]的x[j])都叫做x[i]的右支配元素(Right Dominator). 在x[i]所有的右支配元素中最靠近x[i]的那一个, 就叫做最靠近的右支配元素(Right Nearest Dominator). 当然, 不见得每一个元素都有支配元素的, 如最大元素就没有,问题是, 编写一个程序, 接收一个数组, 把数组中每一个元素最靠近的右支配元素找出来

说明: 看个例子比较容易明了这个问题的要求。如果数组的内容是2, 1, 3, 5, 4那么3, 5, 4都是2的右支配元素, 但3是最靠近的一个, 所以3是2的最靠近右支配元素, 同理1与3的最靠近右支配元素分别是3与5, 5与4都没有最靠近右支配元素; 对5而言, 右边没有元素比它大;就4而言, 右边没有元素了。

看起来程序并不难写,因为可以x[1], x[2] …, x[i],…一个接一个查过去; 当查到x[i]时，就查x[i+1], x[i+2]…, 于是第一次找出比x[i]大或相等的元素, 就是x[i]的最靠近右支配元素了。但是这样的做法效率并不高。举例而言, 如果一个数组的元素是从大到小排好的但是最后一个元素是整个数组的极大值(例如,5, 4, 3, 2, 1, 6)。若数组有n个元素, 处理x[0]要比较n-1次, 处理x[1]时比较n-2次, 一般而言, 处理x[i]时要比较n - i次。所以就一共用了(n-1) + (n-2) + … + 3 + 2 + 1 =n (n-1)/2, 差不多是n ** 2次的比较.

因此, 挑战是, 能不能写出比较次数与n成正比的程序?

参考文献: 这个题目与解法来自 Hubert Wagener在1988年的一篇文章。Wagener是用这个观点来决一个计算几何(Computational Geometry)中的重要问题, 不过他的重点是平行式的算法,但是他的文章中两个解法都有。有兴趣的朋友可以参看

H Wagener. Triangulating a Monotone Polygon in Parallel. Computational Geometry and Its Applications, Lecture Notes in Computer Science, No 333, Springer-Verlag. 1988, Pp 136-147

解答见dominator.py

这个问题一般叫做过半数(Majority)问题, 也有人称为投票(Voting)问题, 但以前者说法居多。假设有1, 2, … n等n个人参加投票, 他们只能圈选一个人, 但是却可以选任何一人, 甚至于可以选不在这n个人中的另一个都行。例如, 如果5个人投票, 分别投1、8、1、100、1; 1、3、5都投给1, 2投给8, 4投给100。问题是, 写一个程序接收这些投票结果, 看看有没有人的得票过半数, 就以上例来看, 1的得票数就过半数了.

说明: 这是个名题, 也与其他问题一样有简单但效率低的解法, 但也有较有技巧且效率高的做法, 简单做法是, 把投票结果先从小到大排好, 把投给同一个人的票就收在一起, 接着从头查起, 看看一连串相同的值的个数, 如果有过半数的, 那个人就当选了。用上面的例来看, 从小到大排好是1, 1, 1, 8, 100, 很显然1有3个, 过半数了, 因此1会当选。

这是一个大家都会想到的想法, 但事实上, 排大小的这一步是不必要的, 能开发出这样的程序吗? 不过要记住一点, 不能对候选人的数目作任何假设, 因为如果假定候选人是1, 2, …, k, 那么这个题目就简单至极而不会变成名题了。为什么呢? 准备一个有k个元素的
数组, 然后……(一定马上就知道是怎么回事了吧!)。

参考文献: 这个题目起源于容错(Fault Tolerant)计算机系统中的一个问题, 是在1981年由 J. Moore(发现匹配字符串的 Boyer-Moore方法的那一个More)提出来的。1982年, J Misra与 David Gies两人合写了一篇深入探讨程序写作的文章, 同年 M.J.Fischer与S. L Salzberg提出了个比此例复杂的方法, 比较1.5n+1次就可以找出结果, 而且还证明了不管用什么办法,比较次数都不可能少于1.5n - 2次。推荐读读上述的文章, 以及所附的文献, 了解问题的来龙去脉。

1. M.J. Fischer and S L Salzberg. Solution to Problem 81-5, Journal of Algorithms, Vol3(1982), pp.375~379
2. Misra and D Gries. Finding Repeated Elements, Science of Computer Programming Vol2(1982), pp.143~152
3. J.Moore. Problem 81-5, Journal of Algorithms. Vol 2(1981), Pp 208-209

解答见voting.py

已知一个整数数组, 在这个数组中的一个递增序列, 就是把若干元素删除后所留下的元素按从小到大的顺序排列。举例而言, 如果数组是1,3,5,7,8,2,9,4,10,6, 那么1,5,8,9,10是个递增序列, 3,5,8,9,10也是一个递增序列, 1,3,5,7,9,10 也是递增序列。简单地说, 可以依数组元素的次序选出若干元素, 使得从小到大排好 ,那么这就是个递增序列。例如3,8; 2,9; 7,10; 2,4,6; …。但是9,4,10; 5,7,8,2,9等却不是递增序列。 问题是, 写一个程序接收一个整数数组, 找出这个数组中最长的递增序列的长度。以上面的例子来看, 1,3,5,7,8,9,10是最长的递增序列, 所以程序输出7的结果。

说明: 递增序列的意义已如上述, 程序要如何写? 看起来似乎很难下手, 但总是有迹可寻的,为什么呢? 递增序列不会凭空出现, 一定是先有了几个, 然后又出现一个新元素, 看看这个新元素能不能加到已有的递增序列后面, 如果可以,已有的递增序列的长度就多了1; 但若不能添加, 那要做些什么事呢? 那就要自己想了. 先看个例子, 还是以1,2,4,3,6为例。假设目前已经发现了如下的几个递增序列:

1,2,4,6(长度为4)

1,2,3(长度为3)

现在新来的元素是5, 因此5可以补在1,2,3后面而得到1,2,3,5(长度为4); 那么5对1,2,4,6的关系又如何? 这就要自己想了。

这个问题的起源可能是组合数学(Combinatoric Mathematics)。组合数学中有一个定理, 它说n ** 2 + 1个数中一定有一个长度至少为n的递增或递降序列。此处不过是要求写一个程序把最长的递增序列的长度找出来而已, 会写这个程序之后, 递降序列也不过是同一回事。

解答见longest_increase_sequence.py

已知两个字符串s与t, 要研究如何把字符串s经由一连串编修动作变成t。能够使用的就是插入一个符号, 以及删除一个符号; 把某个符号换成另一个, 就可以通过先把它删除再在原地插入所需的符号来完成。编写一个程序, 接收s与t, 找出如何才能够在最少步骤之下把s改成t。

说明: 把一个字符串修改成第一个字符串在语汇分析(Lexical Analysis)与拼字分析(Spelling Check)中有很重要的地位。例如, 已知s这个字符串可能有问题, 而在s中应该会出现t[1],t[2]…t[k], 这几个字符串其中之一, 但是用哪一个比较好呢? 通常会选使用最少修动而能够把s改出来的那一个, 这一项技巧在化学中研究分子结构相当有用.

如果已知ABCD这个字符串,想把它改成XBYD,一看就知道可以把A换成X, C成Y就行了, 这就有了4个动作一删除A, 插入X, 删除C, 插入Y; 但也可以把ABCD全部删除,再插入XBYD, 这就要8个动作, 4个删除, 4个插入。当然, 两者相比, 自然是第一个方法好些。这是一个简单的例子, 但当s与t这两个字符串很长时就不那么容易看出结果了, 因此这个题目就是要求编写这样的一个程序.

前面的最长部分序列(Longest Common Sequence)的技巧对本题非常有帮助, 不妨先看看LCS这个程序

a[1]a[2]…a[i]与b[1]b[2]…b[j]相互变换可以分为以下几种情况

1. 如果a[i] = b[j], 于是a[1][2]…a[i]变成b[1]b[2]…b[j]的次数等于a[1]a[2]…a[i-1]变成b[1]b[2]…b[j-1]的次数
2. 如果a[i] != b[j], 分成三种情况讨论: 第一, 检查a[1]a[2]…a[i]变成b[1]…b[j-1]后，再插入一个b[j]; 第二, 检查a[1]…a[i-1]变成b[1]b[2]…b[j]后再插入一个a[i]; 第三: a[1]…a[i-1]变成b[1]b[2]…b[j-1]后，删除a[i], 插入b[j]

解答见string_edit.py

如果A=a[1]a[2]…a[m]是一个长度为m的字符串, 把其中的若干(可能是0个, 也可能是n)个符号去掉, 而得到一个新字符串, 这个新字符串就称为A的子序列(Subsequence). 例如, 若A=abc0123, 那么b02, abcl23, b3, c, ab0123, ab12等都是A的部分序列.

假设给出两个字符串A与B, 长度分别是m与n, 那么A与B就含有若干共同的子序列, 至少虚字符串(或说是空字符串)就是一个共同部分序列; 所谓C是A与B的公共子序列, 指的是C是A的子序列, C也是B的子序列。编写一个程序,把A与B的公共子序列中最长的那一个找出来。

这个同题一般都称为最长公共子序列(Longest Common Subsequence)问题, 简称为LCS

说明: 这是一个非常有名的题目, 而且是一个分支中的主要问题, 这个分支称为字符串匹配
(String Matching), 可以说是计算机科学研究领域中比较早开发的科目, 目前的应用很广, 从语音分析到生化都能看到这一支的踪迹, 参看下面参考文献中各篇文章的介绍. 写程序的熟手或了解算法理论的朋友是不难写这个程序的, 因为它不过是一个动态规划(Dynamic Programming)的应用而已。给一点提示, 如果两个字符串是A=a[1]a[2]…a[m], B=b[1]b[2]…b[n],考虑a[i]与b[j]

如果在a[1]a[2]…a[i-1]与b[1]b[2]…b[j-1]这两个字符串的前段中已经找到了一个长度是k的公共子序列, 那么会有两种可能:

1. 如果a[i] = b[j], 于是把原来长度为k的共同部分序列后面补上ai, 就会得到a[1]a[2]…a[i]与b[1]b[2]…b[j]的一个长度是k+1的公共子序列
2. 如果a[i] != b[j],分成两种情况讨论: 第一, 检查a[1]a[2]…a[i-1]与b[1]…b[j-1]b[j]的最长公共子序列的长度; 第二, 检查a[1]…a[i-1]a[i]与b[1]b[2]…b[j-1]的最长共同部分序列的长度。最后进行适当的处理。

有了这个观点在心中, 找出最长公共子序列应该不会十分困难, 但是要如何把那个序列找出来呢? 这或许要好好想一想。

下面推荐的这本书是论文集有许许多与编修字符串方面的文章可供参考, 自然也包含有最长共同序列这个问题:此外,书中还有不少这些方面的应用与说明。

R.A. Wagner and M.J. Fischer. The String-to-String Correction Problem, Joumal of ACM。Vol.21(1974) p168~173

解答见longest_common_subsequence.py

编写一个程序, 用Gray码(Gray Code)的顺序列出一个集合的所有子集。
说明: 这个问题其实是在看有没有办法把Gray(人名)码用程序编写出来, 有了Gray码，找出对应的集合是件简单的事。

什么是Gray码? nbit的Gray码是一连串共有2 ** n 个元素的数列, 每一个元素都有能nbit, 而且任何相邻的两个元素之间只有1的值不同, 例如,3个bit的Gray码:

000 001 011 010 110 111 101 100

是一组Gray码, 任何相邻两个元素都只有1bit值不同。但是，Gray码却并不是惟一的，把它循环排列或是用反过来的顺序写,也会得到一组Gray码; 比如说, 如果把最后3个素放到最前面去, 就会得到

111 101 100 000 001 011 010 110

也是一组Gray码。

产生Gray码的方法很多，这里这介绍其中一种。
将2bit Gray码列出
00
01
11
10
将3bit Gray码列出
000
001
011
010
110
111
101
100
观察3bit Gray码可以发现，它可以由2bit Gray码来得到。

解答见gray_code.py

8后问题(Eight Queen Problem)是指在一个8 8的西洋棋盘上要如何放置8个皇后棋, 且不会互相吃到对方; 皇后棋可以吃掉任何它所在的那一列、那一行, 以及那两条对角线(米字型)上的任何棋子。请写一个程序, 读入一个值n表示棋盘的大小, 然后求出n n格棋盘上放n个皇后棋且不会相互吃掉对方的所有解答。

说明: 这是广义的N后问题, 因为所要求的是“所有”解答, 而不单是其中的一组, 对大多数会运用递归的人来说,这个题目反而容易做些。这一类型题目的解法通常要用到回溯(Backtrack)的技巧, 不管用递归还是不用递归都是如此, 虽然会浪费时间,但多半会找到解答。

回溯的技巧通常都以下面的面目出现, 如下所示。

1
2
3
4
5
6
7
8
9
10

S = 目前可以用得到的位置;
当S非空: 
    取出S中一个元素, 令为s
    如果s可以安全使用，那么
        定出s已经使用
        如果还可以从S再进一步，那么
            用S调用自己
        如果已经有了答案，那么
           显示答案
        把s定成没有在使用

解答见n_queen.py

某个国家一共发行了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