遍写一个程序,读入一道正确的算术式, 把它转译成反向波兰形式(Reversed Polish), 为了方便起见, 假设整道算术式在同一列上, 并且变量只有一个英文字母,不含常数(换言之,所有运算都是一个字母的变量). 目前,只需要处理+, -, *, /, (, )即可, 没有正负号.

说明: 反向波兰形式是用来表示一道表达式的常见写法, 是由波兰学派的逻辑学家发展出来表示逻辑式子用的。它有一个很重要的特性,就是不会用到括号, 在寻常的算术式子中, 运算是写在两个操作数之间, 但反向波兰形式则是把运写在对应的操作数后方。例如a+b写成ab+, a+bc 写成abc+, ab+c写成abc+。对a+b而言, +的操作数是a与b, 所以写成ab+是很明显的; 再看a+bc, 最先算的是bc, 因而写成bc, +的两个操数是a与bc,因此就写成abc+; 同理,ab+c写成abc+就不必解说了

如果算术式子中有括号, 括号中的部分对某个运算而言就是一个完整的操作数。在(a+b)(c+d)中, a+b的写法是ab+, c+d的写法是cd+, 但ab+与cd+又是的操作数, 因此得到ab+cd+, 再看一例, a(b+c)-(e+f)/g, a与bc+是的操作数, 所以这一部分可以写成abc, 同理(c+f)/g可以写成ef+g/, 因此整个式子就是abc+*ef+g/-

从上面的说明可以看到, 一旦写成反向波兰形式, 括号就没有了, 这是它方便的地方. 但是如何把算术式转变成反波兰式呢? 如果仔细研究上述的结果可以有下面的结论:

  1. 反向波兰形式中变量的顺序与原来算术式中的顺序相同
  2. 运算永远出现在它的两个操作数后方

因为上述的第一点理由, 当读到一个操作数的时候, 就可以把它输出, 因为操作数在输入与输出中顺序相同。运算又如何呢? 运算是比较麻烦的, 先不管左、右括号, 因为在自左向右地读取输入时, 看到了一个+号, 此时不但还没有见到它的右边操作数, 更看不到下一个运算, 于是无法决定这个+号是不是可以计算。例如a+bc, 如果现在才读入+,就没有办法知道这个加法能不能计算, 一直到出现才能作决定(也就是不能算); 同样, 看到了也不表示它能够算, 为什么呢? 如果输入是a+b(x+y), 把x+y算出来之后才能算法。换句话说, 在下一个运算出现之前, 并不知道目前这个运算可不可以算; 回想一下先乘除后加减的规则, 如果下一个运算(例如+)的优先级比现在的(例如)低, 那么就可以算现在的这个。正因为如此, 用堆栈是个好方法, 把不能算的运算先推到堆栈中, 于是现在的这一个就在顶上, 当下一个运算出现了, 就看看顶上那一个与下一个的关系, 如果顶上(现在)的这一个可以算, 就把它输出。如果碰到左、右括号又怎么办呢?

以上就是个简单的提示。其实, 可以在其他的书中找到解答,但建议不要这样做,因为在计算机刚问世时这是个难题, 如果能够独立解决它而不求助外力的话, 是很值得自豪的, 但如果学过了这方面的知识, 就不妨跳过去, 做一做后面的习题。注意,以上的方法与提示并不是最好的,可以参看有关编译程序的专业书籍来寻求更好、更普遍性的解法

解答见polish.py

打赏作者

如果有n个对象, 它们的计量单位各为k1, k2, …, kn; 现在有一个可以容纳K单位的背包, 请写一个程序, 找出有没有办法在1, 2, …, n中选P个元素出来, 使得计量单位的总和为K, 可以刚好把背包装满。这就是有名的背包问题(Knapsack Problem)

说明:以计量单位分别是1, 2, 4, 7, 10, 12, 13, 15, 17这9个对象来看好了, 若背包的容量是27, 可以取4,10与13, 因为4 + 10 + 13 = 27; 但也可以取2, 12, 13, 因为27 = 2 + 12 + 13; 更可以取10与17, 因为27 = 10 + 17;当然还有其他的可能解答。不过,这个题目却是不一定有解的。例如, 若对象的计量单位是1, 5, 10, 15, 20; 而背包是14, 物件中比14小的有1, 5, 10, 无论如何选择, 都不可能加出一个14来的。

就像上一题找零钱的问题一样, 可以用动态规划的技巧来解这个问题, 不过会复杂, 但基本道理是完全相同的. 这里要求有解的时候,找出一个解。

解答见knapsack.py

打赏作者

Mac的磁盘空间真的是令人抓狂。每次不知道咋回事,就报磁盘空间将要爆满,我就赶紧去删掉一些没用的文件, 或者执行下clean_my_mac.sh, 过不了几天,又爆满。

今天已经想不到要删哪个没用的文件,使用du -sh *又太慢,于是只好上网找解决办法。上网查了之后,找到了OmniDiskSweeper这个清理磁盘空间,竟然很好用。 清理后,空间如下。

1
2
3
➜  ~ df -h
Filesystem Size Used Avail Capacity iused ifree %iused Mounted on
/dev/disk1 233Gi 143Gi 90Gi 62% 37424607 23556639 61% /

需要注意的是,使用OmniDiskSweeper时,回到上层目录是用方向键中的向左方向键。

打赏作者

前些天,有个姑娘说想学Python,我一听,双眼放出万丈光芒,心想如果我教会她,万一姑娘一时高兴,以身相许,老妈就再也不用担心我了,那岂不是美滋滋。于是准备要怎么教她学编程,夜晚,躺在床上,回忆自己的编程经历,想起高一时与朝辉一起学习VBasic的点点滴滴,想起大一时为了考C语言二级的突击学习,真是岁月如梭。一顿感慨后,心中已有了大致的想法,于是有了这篇文章。

几乎所有的编程语言,都是由3种基本的程序结构组成,顺序,循环,选择,弄懂这三种后,就可以写程序了。下面且听我一一道来。

print

先来看看print语句

1
2
print('邓世龙')
输出 邓世龙
1
2
3
4
a = 1
b = 2
print(a, b)
输出 1 2

顺序结构

然后来看顺序结构, 顺序结构很容易理解,就是程序是一句句往下执行,

1
2
3
4
5
6
a = 1
b = 2
a = 3
b = 4
print(a, b)
输出 3 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
s = 0
print(s)
s = s + 1
print(s)
s = s + 2
print(s)
s = s + 3
print(s)
s = s + 4
print(s)

输出如下
0
1
3
6
10

接下来看看循环结构。现在我们要完成一个计算任务,计算1 + 2 + 3 + … + 10的和,我们可以从1一直加到10,这就需要循环。在绝大多数编程语言里,都提供for或者while来完成循环,这里先来看for, 而在这之前,先了解下list, 也就是列表。

list(列表)

list相当于其它编程语言里的数据,主要是用来存放统一类型的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
x = [1, 2, 3, 4, 5, 6]
print(type(x)) # 显示x的类型
print(len(x)) # 求列表的长度
print(x[0]) # 取第一个值
print(x[2]) # 取第三个值
print(dir(x)) # 显示列表的变量和方法

输出如下
<class 'list'>
6
1
3
['__add__', '__class__', '__contains__', '__delattr__', '__delitem__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'clear', 'copy', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']

range

1到6的列表手写问题也不大,但1到100,1到1000的列表如果手写会疯掉的,所以Python提供了range这个函数。

1
2
3
4
5
6
7
8
9
10
11
x = list(range(10))
print(x)
y = list(range(1, 10))
print(y)
z = list(range(1, 10, 2))
print(z)

输出如下
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 3, 5, 7, 9]

循环结构 for

下面就是for循环的语法,注意for循环后面有冒号,之后print还要缩进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# for循环 打印1到10
n = 10
for i in range(1, n + 1):
print(i)

输出如下:
1
2
3
4
5
6
7
8
9
10

现在我们就可以编写求1 + 2 + 3 … + 10的和的程序

1
2
3
4
5
6
7
8
9
10
# 循环,for循环求和, 求1 + 2 + ... + 10的和, 

s = 0
n = 10
for i in range(1, n + 1):
s = s + i
print(s)

输出
55

选择 if

现在我们要求1到10以内,所有偶数的和,这就会用到选择。

那么如何判断是偶数呢?对2取余就行了,如果余数是0,就是偶数

1
2
3
4
5
print(4 % 2 == 0)  # % 是求余操作
print(3 % 2 == 0)
输出
True
False

现在加上if判断,求1到10以内所有偶数的和

1
2
3
4
5
6
s = 0
n = 10
for i in range(1, n + 1):
if i % 2 == 0:
s = s + i
print(s)

选择 and

如果要求30以内,既能被3,又能被5整数的所有整数的和,这时候就会用到and操作

1
2
3
4
5
6
7
8
s = 0
n = 30
for i in range(1, n + 1):
if i % 3 == 0 and i % 5 == 0: # 有15,30
s = s + i
print(s)
输出
45

选择 or

如果要求10以内,能被3,或能被5整数的所有整数的和, 这时候就会用到or操作

1
2
3
4
5
6
s = 0
n = 10
for i in range(1, n + 1):
if i % 3 == 0 or i % 5 == 0: # 有 3,5,6,9,10
s = s + i
print(s)

continue 进入下一次循环

求10以内,能被3或能被5整数, 但不能被2整除的所有整数的和,这时候可以继续使用and和or的组合来判断,但更方便的,还是用continue,

1
2
3
4
5
6
7
8
9
10
s = 0
n = 10
for i in range(1, n + 1):
if i % 2 == 0:
continue
if i % 3 == 0 or i % 5 == 0: # 有 3,5,9
s = s + i
print(s)
输出
17

循环 while

for循环也可以用while循环来代替, while后面跟着判断条件,如果条件为True, 也就是为真,就会一直执行while循环里的内容; 如果为False,就会跳出循环。例如求1 + 2 + … + 10的和,用for循环编写如下

1
2
3
4
5
s = 0
n = 10
for i in range(1, n + 1):
s = s + i
print(s)

改成while,如下

1
2
3
4
5
6
7
s = 0
i = 1
n = 10
while i <= n:
s = s + i
i = i + 1
print(s)

既然有了for循环, 为何还要有while循环呢?考虑这样一个问题,求前6个能被3或5整除的整数的和。这时如果用for循环,就不是很合适,因为你不知到要到什么时候才能结束, 这种情况用while循环就很方便。

1
2
3
4
5
6
7
8
9
10
11
12
s = 0
i = 1
count = 0
n = 6
while count < n:
if i % 3 == 0 or i % 5 == 0: # 前6个为 356910, 12
s = s + i
count = count + 1
i += 1
print(s)
输出
45

也就是说for循环主要用于确定循环次数的场合,而while循环主要用途循环次数不定的场合

循环 break

break用于跳出循环,上面的例子也可以修改为如下程序

1
2
3
4
5
6
7
8
9
10
11
12
s = 0
i = 1
count = 0
n = 6
while True:
if i % 3 == 0 or i % 5 == 0: # 前6个为 356910, 12
s = s + i
count = count + 1
if count == n:
break
i += 1
print(s)

下面再讲讲set, dict还有函数,就可以编写实际代码了。

set

set就是集合,主要用来提高查询速度

1
2
3
4
5
6
s = list(range(1, 100000000))
x = set(s)
print('#')
print(99999999 in s)
print('##')
print(99999999 in x)

在上面的例子中99999999 in s这里会有些卡顿,因为它要从s里的第一个数从前往后一个一个比较,而99999999 in x这里执行非常快,因为set是优化过的数据结构,底层实现是哈希表,可以很快的进行查询

dict

dict,也就是字典,和set类似,只不过多了个value值,也用来提高查询速度,应用广泛,例如查询身份证号对应的一些个人用户信息等等

1
2
3
4
d = {'a': 65, 'b': 66}
print(d['a'])
输出
65

函数

函数就是一些可以重复利用的代码段。例如要求1到10的所有整数的和,与求2到5所有整数的和,这是两个类似的问题,就可以编写求和函数来解决,求和函数如下。声明一个函数是用def关键字,然后是函数名,后面跟着参数。

1
2
3
4
5
6
7
8
9
10
11
def my_sum(a, b):
s = 0
for i in range(a, b + 1):
s = s + i
return s

print(my_sum(1, 10))
print(my_sum(2, 5))
输出
55
14

到了这里,三种程序结构就讲完了,弄懂这三种结构就可以编写更大一些的程序,解决实际问题。而实际上,绝大多数程序,都是由这三种基本结构构成的,无非就是更复杂的数据结构和算法,还有调用库函数。

最后问题来了,我在哪里输入这些代码呢?Jupyter notebook了解下。

打赏作者

本来觉得没必要写的,但是呢,少年看到这个用法觉得还是挺新奇的,竟然还可以这么玩,于是记录下。

前些天,监控系统那边提了需求,要求应用必须加上访问时长日志,并得知道是谁访问的,于是就想到了使用Django的Middleware. 请求进来的时候记下时间,返回的时候记下时间,两者相减,就是请求的时长。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import logging
import time
from datetime import datetime

from django.utils.deprecation import MiddlewareMixin

logger = logging.getLogger(__name__)


class LoggingMiddleware(MiddlewareMixin):
def process_request(self, request):
request.start_time = time.time()

def process_response(self, request, response):
execute_time = time.time() - request.start_time
path = request.path
username = '-'
method = request.method
if hasattr(request, 'user') and not request.user.is_anonymous:
username = request.user.username
code = response.status_code
now = datetime.now().strftime('%Y-%m-%d %H:%M:%S')
res = "{} {} {} {} {:.2f} {}".format(now, username, path, method, execute_time, code)
logger.info(res)
return response

之后在Django配置里,LOGGING->formatters里加上

1
2
very_simple:
format: '%(message)s'

LOGGING->handlers里加上

1
2
3
4
5
monitor:
level: 'INFO'
class: 'logging.handlers.RotatingFileHandler'
filename: 'monitor.log'
formatter: 'very_simple'

在LOGGING->loggers里加上

1
2
3
4
'helper.middleware.logging_middleware':
handlers: ['monitor']
level: 'INFO'
propagate: False

其中helper.middleware.logging_middleware是LoggingMiddleware这个类的存放位置,

最后在项目settings的MIDDLEWARE的最前面加上’helper.middleware.logging_middleware.LoggingMiddleware’

如此日志就会输出到monitor.log

打赏作者

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

打赏作者