其他

一些递归

汉诺塔：可以对比二叉树的中序遍历，分为三步:

1. 把A中的(n-1)个盘移动到B
2. 把A中最下面的盘子移动到C
3. 把B中(n-1)个盘移动到C

def hanoi(n, a, b, c):
    if n == 1:
        print a, "-->" ,c
    else:
        hanoi(n - 1, a, c, b)
        hanoi(1, a, b, c)
        hanoi(n - 1, b, a, c)

hanoi(3, 'A', 'B', 'C')

欧几里得算法(Euclidean algorithm)

最大公约数和最小公倍数

# iteration
def gcd(a, b):
    if a <= 0 or b <= 0: return
    while b > 0:
        factor = a / b
        c, d = b, a - factor * b
        print "{} / {} = {} x {} + {}".format(a, b, factor, c, d)
        a, b = c, d
    return a

# recursion
def gcd2(a, b):
    if a <= 0 or b < 0: return
    if b == 0: return a
    return gcd2(b, a % b)

def lcm(a, b):
    return a * b / gcd2(a, b) # lcm = a * b / gcd

# test
res1 = gcd(1251, 375)
print res1, (gcd2(1251, 375) == res1) # 3
# print gcd(1071, 462)
# print gcd(47, 30)

# a      b         a'    b'
# 1251 / 375 = 3 x 375 + 126
# 375 / 126 = 2 x 126 + 123
# 126 / 123 = 1 x 123 + 3
# 123 / 3 = 41 x 3 + 0
# 3 True

牛顿开方法(Newton's method)：原理是取一条曲线f(x)点x0处的切线，得到和x轴相交后新点x1，再取f(x)点x1处的切线....以此类推，得到递推公式

取二阶可导曲线f(x) = x^2 - num, x = xn带入以上公式, 得到迭代公式x(n+1)=(1/2)*(xn+ num/xn)

# iteration
def sqrt(num):
    x = 1.0  # 取初始值x0 = 1.0
    while abs(x * x - num) > 1e-9:
        x = 0.5 * (x + num / x) # 迭代公式x(n+1) = 1/2 * (x(n) + num / x(n))
    return x

# recursion
def sqrt2(x, num):
    assert x > 0 # 初值点x不为负数
    if abs(x**2 - num) < 1e-9:
        return x
    x = 0.5 * (x + num / x)
    return sqrt2(x, num)

print sqrt(4)
print sqrt(16)
print sqrt(100)
print sqrt2(-1.0, 4) # error
print sqrt2(1.0, 4)
print sqrt2(2.0, 16)
print sqrt2(5.0, 100) # 选取不同的初值点x

下面是sqrt(100)的迭代过程, x=1.0

50.5
26.2400990099
15.02553012
10.840434673
10.032578511
10.0000528956
10.0000000001
10.0
10.0

越靠近答案计算次数越少，比如说100的话是10只用计算一次，但是有些点可能没有答案如极值点如0

Pow:直接x * pow(x, n - 1)是O(n)的复杂度 ，会发生maximum recursion depth exceeded，所以对输入n进行减半+奇偶判断。

public double myPow(double x, int n) {
    if (n < 0) return 1/dfs(x, -n);
    return dfs(x, n);
}

public double dfs(double x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;  // 这个base case有时候可以减少一次递归
    double v = dfs(x, n/2);
    if (n % 2 == 0) {
        return v * v;
    } else {
        return v * v * x;
    }
}

约瑟夫环：k:数到的人消失，n:总人数，求最后剩下的人的位置

from collections import OrderedDict

def josephus(k, n):
    if k < 0 or n < 0: return -1  # 小于0时没有人消失
    if n == 1: return 0  # 只有一个人的时候必须不会消失
    res = josephus(k, n - 1) # n-1人中幸存者的位置
    return (res + k) % n # 迭代公式, 幸存者的位置+k也会幸存

d = OrderedDict()
for i in range(1, 1000):
    ans = josephus(2, i)
    if ans == 1:
        d[i] = ans
print d # [(1, 1), (2, 1), (4, 1), (8, 1), (16, 1), (32, 1), (64, 1), (128, 1), (256, 1), (512, 1)]
# 规律: k = 2时，人数为2^n的幸存者在位置0
print josephus(3, 5)  # 3
print josephus(100, 2)# 0

Scanner的用法

如第一行输入为行列数，然后输入该矩阵。

分为几步，1.定义scanner，2.使用分隔符号，3.注意next类型的区别。

2,3
0,1,1
1,0,1

import java.util.Scanner;
import java.util.Arrays;

class TestScanner {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        in.useDelimiter("[,\n]");
        int row = in.nextInt(), col = in.nextInt();

        char[][] board = new char[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                board[i][j] = in.next().charAt(0); // char,如果不按照格式输入这里会抛出异常
            }
        }
        System.out.println(Arrays.deepToString(board));
    }
}

好像还是会抛出异常啦...还不如直接用Integer.parseInt(in.nextLine())这种

python的读入问题: 牛客网测试地址 官方说明

将一个输入的字符串变成矩阵

3 3
2 3 4
-5 -9 -7
0 8 -4

import sys

row, col = sys.stdin.readline().split()
row = int(row)
matrix = []

for i in range(row):
    line = sys.stdin.readline().strip().split()
    if line == '':
        break
    matrix.append([int(i) for i in line])

# print matrix
sum = 0
for line in matrix:
    for j in line:
        if j > 0:
            sum += j
print sum