试编写一个程序,找出前 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

打赏作者

假设有一个数组x[ ], 它有n个元素,每一个都大于零,称x[0] + x[1] + … + x[i]为前置和(Prefix Sum),而 x[j] + x[j + 1] + … + x[n - 1]为后置和(Suffix Sum)。试编写一个程序,求出x[ ] 中有多少组相同的前置和与后置和。

说明: 如果x[ ] 的元素是3,6,2,1,4,5,2,则x[ ]的前置和有一下7个,即3,9,11,12,16,21,23;后置和则是2,7,11,12,14,20,23;于是11,12,与23这3对就是值相同的前置和与后置和,因为:

11 = 3 + 6 + 2(前置和) = 2 + 5 + 4 (后置和)

12 = 3 + 6 + 2 + 1(前置和) = 2 + 5 + 4 + 1 (后置和)

因为23是整个数组元素的和,因此前置和与后置和一定相同。

当然,也可以用上面的方法把前置和与后置和都算出来(两者都是从小到大的递增序列, 为什么?), 再进行比较, 但建议不要使用这种方法, 因为它需要额外的内存。

假设有一个数组x[ ], 它有n个元素,每一个都大于零,称x[0] + x[1] + … + x[i]为前置和(Prefix Sum),而 x[j] + x[j + 1] + … + x[n - 1]为后置和(Suffix Sum)。试编写一个程序,求出x[ ] 中有多少组相同的前置和与后置和。

说明: 如果x[ ] 的元素是3,6,2,1,4,5,2,则x[ ]的前置和有一下7个,即3,9,11,12,16,21,23;后置和则是2,7,11,12,14,20,23;于是11,12,与23这3对就是值相同的前置和与后置和,因为:

11 = 3 + 6 + 2(前置和) = 2 + 5 + 4 (后置和)

12 = 3 + 6 + 2 + 1(前置和) = 2 + 5 + 4 + 1 (后置和)

因为23是整个数组元素的和,因此前置和与后置和一定相同。

当然,也可以用上面的方法把前置和与后置和都算出来(两者都是从小到大的递增序列, 为什么?), 再进行比较, 但建议不要使用这种方法, 因为它需要额外的内存。

可以用变量prefix来表示前置和,用suffix来表示后置和,用i表示前置和累加元素的位置,i从前往后加,用j表示后置和累加元素的位置, j从后往前加。当prefix > suffix时,累加后置和,也就是j向前走;当prefix < suffix时,累加前置和,也就是i往后走;当prefix == suffix时,同时累加前置和与后置和,也就是i往后走,j往前走. 解答见head_tail.py

打赏作者

已知两个元素从小到大排列的数组x[]与y[],请编写一个程序算出两个数组元素彼此之间差的绝对值最小的一个树,此值称为数组的距离。

说明: 如果x[i]与y[i]是两个元素,那么 |x[i] - y[i]| 就是这两个元素之间的距离,所有这些距离的最小值,称为数组的距离。比如说x[]有1,3,5,7,9, y[]有2,6,8,那么最短距离就是1,因为x[0]与y[0]、 x[1]与y[0]、x[2]与y[1]、x[3]与y[1]、还有x[4]与y[2]的距离都是1。

注意,如果x[]与y[]各有m与n个元素,那么元素之间的距离就一共有m * n个; 事实上往往用不着这么多个值,应该活用x[]与y[]已经排列好的特性,不要把所有的距离都算出来。

依然是利用数组已经排好序的特性。解答见min_dist.py

打赏作者

已知两个整数数组f[]与g[],它们的元素都已经从小到大排列好,而且两个数组中的元素都各不相同。例如,f[]中有1,3,4,7,9,而g[]中有3,5,7,8,10。试编写程序算出这两个数组之间有多少组相同的元素。

就上例而言, f[2]和g[1]为3是一组; f[3]与g[2]为7是第二组

说明: 建议不要使用下面的方法来编程

  1. 固定f[i]
  2. 对于f[i]而言,检查g[]中是否有与f[i]相同的元素
  3. 处理下一个f[i], 即f[i + 1]

因为f[]与g[]都已经从小到大排列好,所以应该活用这一个很强的特性。一个好的程序员绝对不应用上面的笨拙方法来编写程序, 这样会做太多无意义的事。为什么呢?因为g[]的元素都相异,对于f[i]而言,最多只会找出一个与它相同的元素,最坏的情况时把g[]全部查完才找出相同元素(如果采用上面的方法), 如果g[]中有n个元素,需要查n次; 但是若f[]中也有n个元素,那么需要把g[]查n遍,一共作n ** 2(Python的记法,即n的2次方)次比较才能找出结果。

试着找出一种方法,把f[]与g[]各查一次就可以得到答案(记住, 活用f[]与g[]已经从小到大排列的特性).

做完这一题后,建议继续作下一题。

依然是利用已经排好序的这个特性。解答见eq_count.py

打赏作者

支配值数目(GTCount)

已知f[]与g[]两个整数数组,元素已经从小到大排列,请写一个程序,算出f[]中比g[]元素大的对数。换句话说,f[0]比g[]中多少个元素大,f[1]比g[]中多少元素大等,这些值的总和就是要求的答案。

例如,如果f[]中有1,3,5,7,9,而g[]中有2,3,4,7,8,比g[0]大的有f[1]~f[4], 比g[1]大的有f[2]~f[4],比g[2]大的有f[2]~f[4],比g[3]大的有f[4],比g[4]大的有f[4],因此答案是4 + 3 + 3 + 1 + 1 = 12

说明: 与问题1.1一样,需要特别注意数组f[]与g[]已经排序。如果问题1.1能够做出完美的解答,那么本题也不难,相似的方法就可以得到高效率的程序。

利用数组已经排好序的这个特性,可以写出高效的程序. 解答见gt_count.py

打赏作者

冼镜光老师的《C语言名题精选百则》是我最喜欢的一本算法书, 因为它比较亲民些。大一的时候见到这本书,顿时爱不释手,只是当时水平有限,很多题目做的很吃力,就没有继续做下去了。比较意外的是,这本书印刷的次数竟然很少,有些可惜。还有书中都是用C语言写的,对于专注算法来说,并不是很好,于是决定抽空用Python重写。

已知一个已经从小到大排序的数组,这个数组中的一个平台(plateau) 就是连续的一串相同的元素,并且这一串元素不能再延伸。

例如,在1,2,2,3,3,3,4,5,5,6中1,2.2,3.3.3,4,5.5,6都是平台。试编写一个程序,接受一个数组,把这个数组中最长的平台找出来。

在上面的例子中,3.3.3就是该数组的最长平台。

说明:
这个程序十分简单,但是要编写号却不容易,因此在编写程序时应该考虑下面几点:

  1. 使用的变量越少越好
  2. 能否只把数组的元素每一个只查一次就得到结果?
  3. 程序语句越少越好。

这个问题曾经困扰过 David Gries这位知名的技术机科学家。本题与解答取自David Gries编写的有光程序设计的专著。

解答见pleateau.py

打赏作者

这题来自马丁加德纳的趣味数学,这个号称“无解的难题”的最初形式, 也是流传最广泛的形式如下. 某天, 老师召集了他最聪明的两个学生P和S, 递给每人一张纸条, 然后说, 有两个不小于2的整数x和y,满足x != y, 且x + y < 100. 给P的纸条上写有两个数的乘积p = x * y, 给S的纸条上写有两个数的和s = x + y, 请他们确定这两个数具体的值是多少. 于是P和S进行对话:

  1. P: 我无法确定这两个数是多少.
  2. S: 我知道你无法确定这两个数是多少.
  3. P: 既然这样, 那我知道这两个数是多少了.
  4. S: 既然这样, 那我也知道这两个数是多少了.

请读者根据以上信息确定这两个数是多少.

稍加分析后,可以写出程序用计算机来找答案,当然手算也是可以的。

  1. P: 我无法确定这两个数是多少. 这里说的是乘积p有多种分解,所以无法确定x和y是什么。如28有2 14, 4 7两种分解。
  2. S: 我知道你无法确定这两个数是多少.这里说的是s = x + y中的x和y的乘积都满足条件1,即有多种分解。如11等于2 + 9, 3 + 8, 4 + 7, 5 + 6, 而2 9等于18有2 9, 3 6两种分解 3 8等于24有2 12, 3 8, 4 6三种分解,4 7等于28有2 14, 4 7两种分解, 5 6等于30有2 15, 3 10, 5 6三中分解。
  3. P: 既然这样, 那我知道这两个数是多少了. 这里说的是,在p的所有分解x * y中只有一个x + y满足条件2
  4. S: 既然这样, 那我也知道这两个数是多少了. 这里说的是在s = x + y中,只有一个x * y满足条件3

于是写Python代码如下

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# coding:utf-8
from math import sqrt


def pone(p, u):
c = 0
for x in range(2, int(sqrt(p)) + 1):
if p % x == 0 and x + int(p / x) < u:
c += 1
return c >= 2


def sone(s, u):
for x in range(2, int(s / 2)):
y = s - x
if not pone(x * y, u):
return False
return True


def ptwo(p, u):
c = 0
for x in range(2, int(sqrt(p)) + 1):
if p % x == 0 and x + int(p / x) < u:
y = int(p / x)
if sone(x + y, u):
c += 1
return c == 1


def stwo(s, u):
c = 0
for x in range(2, int(s / 2)):
y = s - x
if ptwo(x * y, u):
c += 1
return c == 1


if __name__ == "__main__":
u = 100
for x in range(2, int(u / 2)):
for y in range(x + 1, u - x):
p = x * y
s = x + y
if pone(p, u) and sone(s, u) and ptwo(p, u) and stwo(s, u):
print("x: %d, y: %d, p: %d, s: %d " % (x, y, p, s))

打赏作者

想对show processlist命令的结果进行过滤,分组操作,不支持。在The INFORMATION_SCHEMA PROCESSLIST Table里可以看到SHOW FULL PROCESSLIST 和 SELECT * FROM INFORMATION_SCHEMA.PROCESSLIST效果是相等的,于是可以在PROCESSLIST表上进行过滤分组操作。

  • 需要对host进行统计 select substring_index(host,’:’ ,1) as server, count(*) from information_schema.processlist group by server;
  • 查询执行时间超过2分钟的线程,然后拼接成 kill 语句 select concat(‘kill ‘, id, ‘;’) from information_schema.processlist where command != ‘Sleep’ and time > 2*60 order by time desc

参考资料

打赏作者

在安装Python包时,报如下错误

1
2
3
4
from Crypto.PublicKey import RSA
from Crypto.Util.asn1 import (DerSequence, DerInteger, DerBitString,

ImportError: cannot import name 'DerBitString' from 'Crypto.Util.asn1'

在网上只找到ImportError: cannot import name ‘DerBitString’, 评论里说 Could you please try in a new virtualenv? It seems related to your virtualenv.

我使用的是pyenv搭建的Python3.6.2, 报错, 后来同事用virtualenv搭了个Python3.7.0的环境,不会报错。于是试了用pyenv搭建个Python3.7.0的环境,还是报错。于是可以确定是pyenv的原因,用virtualenvwarpper搭了个Python3.6.5的环境,这次没有报错。

用了这么久pyenv, 第一次遇到这种问题,莫名奇妙。

2018年11月23日更新: 发现原因了,是因为PyCrypto包和PyCryptodome有冲突,当只安装PyCrypto时就没有这个问题。事实上,最好使用PyCryptodome这个包,因为它是PyCrypto的替代者,只是这里应用依赖PyCrypto包,所以才用它。

打赏作者

有些时候,需要用到嵌套过滤,例如如果要求数据都只是逻辑删除时,此时就会用到。例如有一个应用表,还有一个应用成员表, 如果显示应用详情时,想在一个接口把应用成员一起显示出来,此时就需要过滤掉那些被逻辑删除的成员。

如下定义的application和member

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Application(models.Model):
"""应用"""

name = models.CharField(max_length=32, help_text='应用名称')
is_deleted = models.BooleanField(default=False, help_text='是否已删除')
gmt_create = models.DateTimeField(auto_now_add=True)
gmt_modify = models.DateTimeField(auto_now=True)

class Member(models.Model):
"""应用成员"""

application = models.ForeignKey(Application, help_text='应用', related_name='members', on_delete=models.PROTECT, db_constraint=False)
user = models.ForeignKey(User, help_text='成员', on_delete=models.PROTECT, db_constraint=False)
is_deleted = models.BooleanField(default=False, help_text='是否已删除')
gmt_create = models.DateTimeField(auto_now_add=True)
gmt_modify = models.DateTimeField(auto_now=True)

序列化如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class MemberSerializer(Serializer):
'''应用成员 序列化器'''

class Meta:
model = Member
fields = '__all__'
read_only_fields = ('gmt_create', 'gmt_modify', 'is_deleted')


class ApplicationDetailSerializer(Serializer):
members = MemberSerializer(many=True)

class Meta:
model = Application
fields = '__all__'
read_only_fields = ('gmt_create', 'gmt_modify', 'is_deleted')

此时会把应用中逻辑删除掉的用户也查出来,查看How do you filter a nested serializer in Django Rest Framework?得到解答。需要在Meta中添加list_serializer_class, 修改后如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class DeletedFilterListSerializer(ListSerializer):

def to_representation(self, data):
data = data.filter(is_deleted=False)
return super(DeletedFilterListSerializer, self).to_representation(data)


class MemberSerializer(Serializer):
'''应用成员 序列化器'''

class Meta:
list_serializer_class = DeletedFilterListSerializer
model = Member
fields = '__all__'
read_only_fields = ('gmt_create', 'gmt_modify', 'is_deleted')

如此序列化应用时,就不会把删除掉的应用成员查出来

打赏作者