数学知识复习与递归简论

《数据结构与算法分析Java语言描述》第一章1.2与1.3节读书笔记

1. 数学知识复习

1.1 指数

$X^AX^B=X^{A+B}$

$\frac{X^A}{X^B}=X^{A-B}$

1.2对数

在计算机科学中，除非特别声明。否则所有对数都是以2为底。

定理1.1：

$log_AB=\frac{log_CB}{log_CA}; \quad A,B,C>0,A\ne1$

定理1.2:

$logAB=logA+logB; \quad A,B>0$

推导：

$logA/B=logA-logB$

$log(A^B)=BlogA$

$logX<X对所有的X>0成立$

1.3 级数

$\sum_{i=0}^n2^i=2^{N+1}-1$

$\sum_{i=0}^nA^i=\frac{A^{N+1}-1}{A-1}$

如果0<A<1 则

$\sum_{i=1}^N A^i \le \frac{1}{1-A}$

$\sum_{i=1}^N i = \frac{N(N+1)}{2} \approx \frac{N^2}{2}$

$\sum_{i=1}^N {i^2} = \frac{N(N+1)(2N+1)}{6} \approx \frac{N^3}{3}$

$\sum_{i=1}^N {i^k} \approx \frac{N^{k+1}}{|k+1|} \quad k \neq -1$

当k=-1时，上面的公式不成立，需要下面的公式。$H_N$为调和 和，下面近似式的误差$\gamma \approx 0.57721566$，称为欧拉常数

$H_N = \sum_{i=1}^N \frac{1}{i} \approx log_e^N$

以下一般代数运算：

$\sum _{i=1}^N f(N) = Nf(N)$

$\sum _{i=n_0}^N f(i) = \sum _{i=1}^Nf(i) - \sum _{i=1}^{n_0-1}f(i)$

1.4 模运算

如果A-B整除以N，那么A与B模N的余数是相同的。记作$A \equiv B$(mod N)。

1.5 证明方法

1. 归纳证明法

1. 第一步证明基准情形，确定定理对最基准的值的正确性。
2. 进行归纳假设，假设定理对直到有限数 k 的的所有情况都是成立的。
3. 依据这个假设证明定理对下一个值(k+1)成立。

1.1证明演示

  证明斐波那契数列，$F_0=1$, $F_1=1$, $F_2=2$, $F_3=3$, $F_4=5$, …, ,$F_i=F_{i-1}+F_{i-2}$, 满足对$i\ge1$，有$F_i < (5/3)^i$。

证明：

1. 基准情形：$F_1=1< {\frac{5}{3}}$，$F_2 = 2< {\frac{25}{9}}$
2. 归纳假设：假设定理对于i=1，2，…，k成立，则有$F_k < (5/3)^k$
3. 证明k+1成立：
   1. 由定义有： $F_{k+1} = F_k + F_{k-1}$
   2. 则有：$F_{k+1} < (5/3)^k + (5/3)^{k-1} =(3/5)(5/3)^{k+1} + {(3/5)^2}{(5/3)^{k+1}} = (3/5 + 9/25){(5/3)^{k+1}} < (5/3)^{k+1}$

2. 反证法

1. 假设某个定理不成立。
2. 证明该假设导致某个已知的性质不成立，证明原假设是错误的(定理成立)。

2.1 证明演示：

  证明存在无穷多个素数。

证明：

1.假设定理不成立：假设不存在无穷多个素数。

2.推导某个已知性质不成立：

1. 由1的假设有最大素数$P_k$，令$P_1,P_2,...,P_k$依序排列。
2. 考虑有 ： $N=P_1 P_2 P_3...P_k +1$
3. 显然，$N>P_k$，根据假设($P_k$为最大素数，则N比不为素数)。但是N不能整除以$P_1,P_2,...,P_k$。产生矛盾，因为每一个整数要么是素数，要么是素数的乘积。
4. 因此$P_k$是最大的素数假设不成立，意味定理成立。

2. 递归简论

2.1 递归四条基本法则：

1. 基准情形：必须包含某些基准情形，无需递归就能解出。(程序出栈条件)
2. 不断推进：每一次递归，必须朝着基准情形推进
3. 设计法则：假设所有递归调用都能运行
4. 合成效益法则：在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。(在计算F(n-1)时同时调用了F(n-2)，而同时原式也需要调用一次F(n-2)，重复)

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

public class RecurdiveTest {

    public static void main(String[] args) {
        // 静态方法里面不能调普通方法
        int res =  f(4); //计算f(4s)
        System.out.println(res);
    }

    public static int f(int x) {
        if (x == 0) {
            // 递归出口
            return 0;
        } else {
            return 2 * f(x-1) + x * x;
        }
    }
}
// 结果58