经典算法示例（一）

汉诺塔

汉诺塔示意图

代码：

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
public static void main(String[] args) {
    hnt('A','B','C', 3);  // 3层圆盘，移动 2^3-1 次
}

public static void hnt(char x ,char y, char z, int n) {
    if (n == 1) {
        System.out.printf("[圆盘%s] %s -> %s\n", n, x, z);
        return;
    }
    // 把前面n-1个，从x柱 借助z 移到y柱
    hnt(x, z, y,n-1);
    // 第n个移到z柱
    System.out.printf("[圆盘%s] %s -> %s\n", n, x, z);
    // 前面n-1个，从y柱 借助x 移到z柱
    hnt(y, x, z,n-1);
}

/*
[圆盘1] A -> C
[圆盘2] A -> B
[圆盘1] C -> B
[圆盘3] A -> C
[圆盘1] B -> A
[圆盘2] B -> C
[圆盘1] A -> C
*/


MR - 字符串转数字(py)

1
2
3
4
5
6
7
8
from functools import reduce

DIGESTS = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}

def str2int(s):
    return reduce(lambda x, y: 10 * x + y, map(lambda c: DIGESTS[c], s))
  
print('3432232010903249204202')


Filter - 计算所有素数(py)

计算素数的一个方法是埃氏筛法，它的算法理解起来非常简单：

首先，列出从2开始的所有自然数，构造一个序列：

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …

取序列的第一个数2，它一定是素数，然后用2把序列的2的倍数筛掉：

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …

取新序列的第一个数3，它一定是素数，然后用3把序列的3的倍数筛掉：

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …

取新序列的第一个数5，然后用5把序列的5的倍数筛掉：

7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, …

不断筛下去，就可以得到所有的素数。

用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
# 注意这是一个生成器，并且是一个无限序列
def _odd_iter():
    n = 1
    while True:
        n = n + 2
        yield n
        
# 然后定义一个筛选函数
def _not_divisible(n):
    return lambda x: x % n > 0
  
# 最后，定义一个生成器，不断返回下一个素数
# 这个生成器先返回第一个素数2，然后，利用filter()不断产生筛选后的新的序列
def primes():
    yield 2
    it = _odd_iter() # 初始序列
    while True:
        n = next(it) # 返回序列的第一个数
        yield n
        it = filter(_not_divisible(n), it) # 构造新序列
        
# 由于primes()也是一个无限序列，所以调用时需要设置一个退出循环的条件：
# 打印1000以内的素数:
for n in primes():
    if n < 1000:
        print(n)
    else:
        break


Gen - 斐氏数列和杨辉三角(py)

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
"""斐波那契数列
0 1 2 3 5 8 13 21 ...
"""
def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

for n in fib():
    if n < 100:
        print(n)
    else:
        break


"""杨辉三角
          1
         / \
        1   1
       / \ / \
      1   2   1
     / \ / \ / \
    1   3   3   1
""" 
def triangles():
    x = [1]
    while True:
        yield x
        x = [0] + x + [0]
        x = [x[index] + x[index + 1] for index in range(len(x) - 1)]

t = triangles()
for i in range(6):
    print(next(t))


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
48
49
50
class Fib(object):
    def __init__(self):
        self.a, self.b = 0, 1

    def __str__(self):
        return "<class Fib>"

    # Iterable
    def __iter__(self):
        return self

    def __next__(self):
        self.a, self.b = self.b, self.a + self.b
        if self.a > 10:
            raise StopIteration()
        return self.a

    # 鸭子模型，类list用法，Fib()[1:3]
    def __getitem__(self, n):
        if isinstance(n, int):  # n是索引
            a, b = 0, 1
            for x in range(n):
                a, b = b, a + b
            return a
        if isinstance(n, slice):  # n是切片
            start = n.start
            stop = n.stop
            if start is None:
                start = 0
            a, b = 0, 1
            L = []
            for x in range(stop):
                if x >= start:
                    L.append(a)
                a, b = b, a + b
            return L

    # 在没有找到属性的情况下调用该方法，默认返回None
    # 可以避免 AttributeError: 'Fib' object has no attribute 'xxx'
    # 可以返回本类对象，形成链式调用的形式
    def __getattr__(self, attr):
        pass

    # 直接对实例进行调用 fib()
    # 该方法可以定义参数，对实例进行直接调用就好比对一个函数进行调用一样
    # 所以你完全可以把对象看成函数把函数看成对象，因为这两者之间本来就没啥根本的区别
    # 可以使用 callable(xxx) 判断一个对象是否是可调用对象
    def __call__(self, *args, **kw):
        print('Call: %s, %s' % (args, kw))
        return self


计数器实现的几种思路(py)

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
# 闭包：简单的理解就是 "返回函数的函数，返回的函数直到被调用才会执行"

# 方式1：使用generator
def counter_closure():
    def count_generator():
        n = 1
        while True:
            yield n
            n += 1
    g = count_generator()
    def counter():
        return next(g)
    return counter


# 方式2：使用nonlocal关键字
def counter_closure():
    n = 0
    def do_count():
        nonlocal n  # nonlocal关键字用来在函数或其他作用域中使用外层(非全局)变量。
        n += 1
        return n
    return do_count

incr = counter_closure()
print(incr()) #1
print(incr()) #2
print(incr()) #2


装饰器(py)

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
import functools

def log(x):
    if callable(x):
        @functools.wraps(x)
        def wrapper(*args, **kw):
            print("call %s(): " % x.__name__)
            return x(*args, **kw)
        return wrapper
    else:
        def decorate(func):
            @functools.wraps(func)
            def wrapper2(*args, **kw):
                print("call %s %s(): " % (x, func.__name__))
                return func(*args, **kw)
            return wrapper2
        return decorate

@log
def f(x):
    return x ** 2
 
@log('execute')
def f2(x):
    return x ** 3
  
 
# 使用内置的 @property 给对象赋值（setter & getter）
class Student(object):
    @property  #内置
    def score(self):
        return self._score

    @score.setter
    def score(self, value):
        if not isinstance(value, int):
            raise ValueError('score must be an integer!')
        if value < 0 or value > 100:
            raise ValueError('score must between 0 ~ 100!')
        self._score = value