学习了Python程序设计入门第0讲后，对Python有了一定的了解，接下来我们来学习程序设计里一个重要的技巧，那就是递归。

什么是递归呢？简单来说，就是函数自己调用自己，只不过调用参数不同。

一个经典的例子是求正整数的阶乘, 计算某个整数的阶乘，就是求所有小于等于这个数的正整数的和，例如3的阶乘等于6, 5的阶乘等于120。另外还特别规定, 0的阶乘是1

普通的循环写法如下

1
2
3
4
5
6
7
8
9
10
11
12
13

def factorial(n):
    s = 1
    for i in range(1, n + 1):
        s *= i
    return s
print(factorial(1))
print(factorial(3))
print(factorial(5))

1
6
120
40320

递归写法如下

1
2
3
4

def factorial(n):
    return n * factorial(n - 1)

print(factorial(3))

然而上面的写法会陷入死循环，因为它没有结束条件。加上结束条件后，递归求阶乘如下

1
2
3
4
5
6
7
8
9
10
11

def factorial(n):
    if n == 1 or n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(0))
print(factorial(3))
print(factorial(5))
1
6
120

如此我们知道递归程序的一个重要条件是要有结束条件

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …….., 写成公式就是 F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3)

接下来我们用写一个递归程序来计算斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(1, 10):
    print(i, fibonacci(i))
    
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34

如果仔细观察上面的fibonacci函数，会发现很多计算会重复了，例如求fibonacci(5)时，会计算fibonacci(4)和fibonacci(3), 而求fibonacci(4)时会计算fibonacci(3)和fibonacci(2), 这里fibonacci(3)就会重复计算了，这就导致这个递归函数会特别慢，下面我们测试下fibonacci(35)的速度, 可以看到计算fibonacci(35)差不多要2.82s，这是无法接受的，这种情况可以写成非递归的fibonacci函数

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

def fibonacci(n):
    a = 1
    b = 1
    i = 2
    while i < n:
        c = a + b
        a = b
        b = c
        i += 1
    return b
    
    
for i in range(1, 10):
    print(i, fibonacci(i))

1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34

此时再计算fibonacci(35)就会很快了

既然递归算法的执行效率不高，那为什么还要用递归？这是因为，一些很难的问题，有时候用递归会变得很简单。一个经典的例子是Hanoi塔问题

汉诺塔(Towers of Hanoi)是一个在入门书籍中常见的例题或习题, 它是说: 有3根柱子, 1、2与3,在柱子1上串了从上到下编号是1, 2, …, m的圆片, 号码小的圆片也小. 问题是, 请写一个程序, 把柱子1上的圆片搬到柱子3去。在搬的时候有3个要求: 第一, 每次只能搬一个圆片; 第二, 要搬的圆片得从某个柱子取出, 并且放到另一根柱子上; 第三, 任何时刻、任何柱子上的圆片, 从上到下都是从小到大排列。

要写出一个非递归算法，是相当有挑战的，参见非递归汉诺塔, 而用递归的话，却非常容易。

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

def hanoi_tower(n):
    return _hanoi_tower(n, 1, 2, 3)


def _hanoi_tower(n, start, mid, end):
    """
    把n块圆片从start柱子，借助mid柱子, 搬到end柱子
    """
    if n == 1:
        print("Move disk %d from %d to %d" % (n, start, end))
    else:
        _hanoi_tower(n - 1, start, end, mid)
        print("Move disk %d from %d to %d" % (n, start, end))
        _hanoi_tower(n - 1, mid, start, end)
        
hanoi_tower(3)

Move disk 1 from 1 to 3
Move disk 2 from 1 to 2
Move disk 1 from 3 to 2
Move disk 3 from 1 to 3
Move disk 1 from 2 to 1
Move disk 2 from 2 to 3
Move disk 1 from 1 to 3

总的来说，递归算法要满足以下两个条件

1. 要有结束条件，像factorial和fibonacci中的两个if判断
2. 递归的规模要越来越小，像factorial中，求factorial(n)是通过factorial(n-1)得到，fibonacci中求fibonacci(n)是通过求fibonacci(n-1)和fibonacci(n-2)得到，这里传入递归函数的参数都越来越小。

掌握了递归，就掌握了程序设计里非常强大武器之一。

读者可以找一本书, 研究一下快速排列法(Quick Sort)的概念, 并且写成程序

说明: 快速排列法是CAR. Hoare提出来的方法, 它需用到递归的技巧。它的概念是这样的, 有一个数组x[], 它有n个元素。如果能够在x[]中找出一个元素x[k], 使得在x[k]左边都比x[k]小或相等, 在x[k]右边的则大于或等于x[k].

因此, 只要把x[1]~x[k-1], x[k+1]~x[n]分别排列好, 两者合并, 就可以把整个x[]排好了

所以为x[1]…x[n]排序就分成两个部分, 第一部分是找出一个分界点x[k], 满足上述的条件, 第二部分是递归地去排x[1], … x[k-1], 与x[k+1], …, x[n], 排好后结果就出来了

所有快速排列法程序的差异都在第一步, 如何找出分界点x[k]

解答见quick_sort.py

汉诺塔(Towers of Hanoi)是一个在入门书籍中常见的例题或习题, 它是说: 有3根柱子, 1、2与3,在柱子1上串了从上到下编号是1, 2, …, m的圆片, 号码小的圆片包小. 问题是, 请写一个程序,把柱子1上的圆片搬到柱子3去。在搬的时候有3个要求:第一, 每次只能搬一个圆片; 第二, 要搬的圆片得从某个柱子取出, 并且放到另一根柱子上; 第三,任何时刻、任何柱子上的圆片, 从上到下都是从小到大排列。书上的解法都是递归的, 请写一个非递归且不用堆栈来仿真的程序.

说明: 如果用教科书中的解法, 那么递归是个非常好且效率非常高的技巧, 程序大致如程下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#coding: utf-8

def hanoi_tower(n):
    return _hanoi_tower(n, 1, 2, 3)


def _hanoi_tower(n, start, mid, end):
    if n == 1:
        print("Move disk %d from %d to %d" % (n, start, end))
    else:
        _hanoi_tower(n - 1, start, end, mid)
        print("Move disk %d from %d to %d" % (n, start, end))
        _hanoi_tower(n - 1, mid, start, end)


if __name__ == "__main__":
    hanoi_tower(3)

这个观点是, 先把在start柱子上的n-1个圆片搬到mid柱子上去(用end柱子作中继站), 于是在strt柱子上就留下3在最下方, 也就是最大的一个圆片, 即第n号, 把它从start搬到end去(见print); 现在的情况是, 最大的已经到了目的地, 但在上方的第1 ~ n－1号还停留在mid柱子上; 第三步就是把mid上的n-1个圆片搬到end柱子上, 用start柱作中继站。当然, start、mid、end就是题目中的3根柱子, n是要搬的圆片数目.

递归的解不但漂亮, 而且容易懂; 不过了解了递归解法之后产能够由它而发展出一个非递归的解吗? 当然, 用堆栈来仿真并不是所期望的, 应该把递归动作中在什么时候搬那个圆片, 从何处搬到何处这一层关系弄清楚, 那么问题就不难了。

参考文献: 河内之塔(Towers of Hanoi)是法国人 M. Claus( Lucas)在1883年从泰国带到法国的(越南那个时候是法国属地), 河内曾经是越战时北越的首都, 现在的胡志明市。有很多人译成“汉诺威塔”是不对的, 音虽相差不远, 但却显然地误解了Hanoi这个字。河内之塔有一个起源的故事, 这是De Parville在1884年讲的。在Benares地方有一座神庙,从天神创世起, 就在神庙地底、大地的中心处立了3根钻石的针, 一根针上串了64个用金子铸成的圆片,从上到下圆片愈来愈大,神庙的僧侣按照前面提过的方法把这64个金圆片搬到第三根钻石针上,一旦工作完成,这些针、圆片、神庙以及这个世界都会随之消失。这段时间有2-1长, 亦即18446744073709551615步,纵使僧侣毫不犯错,恐怕也得花几百亿年才能搬得完。以上的史料出自下面两本书:

1. W.W. Rouse Ball and H.S. M Coxeter. Mathematical Recreations and Essays. 13th ed, Dover, 1987
2. M. Kraitchik Mathematical Recreations. 2nd ed. Dover. 1953 不用递归法来解河内之塔,曾经是一个很热门的业余问题,文献相当多,本文不打算一列举,与Gay码的联系也陆续地被人们一再“发现”,本书方法是取自 H. Mayer(加州圣地亚哥州立大学教授)与 Don Perkins(美制四年级,等于中国的高一学生)在1985年的一篇文章, Mayer教授指出这是Perkins想出来的方法,但他们两位都不曾指出这个方法与Gray码的联系,不过 Perkins不知道Gray码是可以预见的
3. H Mayer and D. Perkins. Towers of Hanoi Revisited, A Nonrecursive Surprise, SIGPLAN Notices.Vol.19(1984),No.2,pp.80~84 这方面的中文文献并不多,前几年笔者在《Mcmo随笔》上一连写过3个月的介绍或许可以提供参考。那3篇文章入手比较浅,也不曾提到Gray码, 所以有些地方说得不很清楚,如果现在有机会重写, 一定可以做得更好。在那一系列的第三篇中, 还有另一个有的公式与进一步的参考文献, 有兴趣的朋友可以一看
4. 冼镜光.谈河内之塔《Micro随笔》,微电脑时代.1986年9月 pp.170~174; 1980年10月, pp156~163; 1986年11月, pp.159~163

解答见hanoi_tower.py

自从负责CMDB后，很多问题都得自己亲自去面对，于是就得开始动动大脑，这时就发现之前设计不合理的地方。

如下是之前设计的应用表

1
2
3
4

class Application(Model):
    '''应用信息'''
    name = models.CharField(max_length=100, unique=True, help_text='应用名')
    language = models.CharField(max_length=64, help_text='应用语言')

这里数据是同步自另外一个系统，同步的时候只是把语言当做一个字段，这样也看不出什么问题。但是当应用数据源迁移自CMDB后，问题就来了。此时如果要创建一个应用，要有个应用语言列表供选择，然而CMDB里表设计的时候没有考虑语言表，所以没法提供相应的API。

综合考虑后，添加了语言表，并且在应用表下添加应用语言外键

1
2
3
4
5
6
7
8
9
10

class Language(Model):
    '''应用语言'''
    name = models.CharField(max_length=50, help_text='语言', unique=True)  
    
    
class Application(Model):
    '''应用信息'''
    name = models.CharField(max_length=100, unique=True, help_text='应用名')
    language = models.CharField(max_length=64, help_text='应用语言')
    language_fk = models.ForeignKey(Language, on_delete=models.SET_NULL, null=True, db_constraint=False, help_text='语言')

最初的时候是考虑直接将应用表里的language改成外键，但想想这样修改会对之前提供出去的API有影响，所以还是决定添加language_fk外键。

这样修改后，需要创建应用时，写入language_fk的同时，也写入language即可，这个在Django里不难实现。

遍写一个程序,读入一道正确的算术式, 把它转译成反向波兰形式(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个为 3，5，6，9，10, 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个为 3，5，6，9，10, 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