算法时空第一周笔记：fibonacci

$P_1$$quad$$P_2$$quad$$C$
$0 quad 1 quad 1$

$1 quad 1 quad 2$
$1 quad 2 quad 3$
$2 quad 3 quad 5$
$C = P_1+P_2, P_1=P_2, P_2=C tag{1}$

1
2
3

while(n>0)
    p1, p2 = p2, p1+p2
    n -= 1

$$left(begin{matrix} F_{n+1} \F_n end{matrix} right)
=
left(begin{matrix}1&1 \1&0 end{matrix} right)
left(begin{matrix}F_n \F_{n-1} end{matrix} right)
=
left(begin{matrix}F_n+F_{n-1} \F_{n} end{matrix} right)$$
$$=
left(begin{matrix}1&1 \1&0 end{matrix} right) ^2
left(begin{matrix}F_{n-1} \F_{n-2} end{matrix} right)$$

$$
……
$$
$$=
left(begin{matrix}1&1 \1&0 end{matrix} right) ^n
left(begin{matrix}F_1 \F_0 end{matrix} right)$$

$$left(begin{matrix} F_{n+1} \F_n end{matrix} right)
=
left(begin{matrix}1&1 \1&0 end{matrix} right) ^n
left(begin{matrix}F_1 \F_0 end{matrix} right)$$

Set:
$$A=left(begin{matrix}1&1\1&0 end{matrix} right),
A^n=left(begin{matrix}F_{n+1}&F_n \F_n&F_{n-1} end{matrix} right)$$
Prove:
$A^1=left(begin{matrix}1&1\1&0 end{matrix} right)= left(begin{matrix}F_2&F_1\F_1&F_0 end{matrix} right)$
$A^{n+1}=A^ncdot A^1,$

$A^{n+1}=left(begin{matrix}F_{n+1}&F_n \F_n&F_{n-1} end{matrix} right)left(begin{matrix}1&1\1&0 end{matrix} right)$
$$=left(begin{matrix}F_{n+1}+F_n&F_{n+1} \F_n+F_{n-1}&F_n end{matrix} right)
=left(begin{matrix}F_{n+2}&F_{n+1}\F_{n+1}&F_n end{matrix} right)$$

$$x^n=begin{cases}
n为奇数 , &x^{[n/2]}cdot x^{[n/2]} cdot x \
n为偶数 , &x^{n/2}cdot x^{n/2}
end{cases}$$
$$A=
left(begin{matrix}F_2&F_1\F_1&F_0 end{matrix} right)
A^n=left(begin{matrix}F_{n+1}&F_n \F_n&F_{n-1} end{matrix} right)$$
$$A^{2m}=
left(begin{matrix}F_{2m+1}&F_{2m}\F_{2m}&F_{2m-1} end{matrix} right)=A^mcdot A^m=left(begin{matrix}F_{m+1}&F_m \F_m&F_{m-1} end{matrix} right)left(begin{matrix}F_{m+1}&F_m \F_m&F_{m-1} end{matrix} right)$$
$left(begin{matrix}F_{m+1}^2+F_m^2&F_{m+1}F_m+F_mF_{m-1} \F_{m+1}F_m+F_mF_{m-1}&F_m^2+F_{m-1}^2 end{matrix} right)$
$$begin{cases}
F_{2m+1}=F_m^2+F_{m+1}^2 \
F_{2m}=(F_{m-1}+F_{m+1})F_m
end{cases}$$

当n为奇数： $n=2m+1, [n/2]=m$
$$left(begin{matrix} F_{n+1} \F_n end{matrix} right)
=left(begin{matrix} F_{2m+2} \F_{2m+1} end{matrix} right)
=left(begin{matrix} (F_m+F_{m+2})F_{m+1} \F_m^2+F_{m+1}^2 end{matrix} right)
=left(begin{matrix} (2F_m+F_{m+1})F_{m+1} \F_m^2+F_{m+1}^2 end{matrix} right)$$
当n为偶数： $n=2m, n/2=m$
$$left(begin{matrix} F_{n+1} \F_n end{matrix} right)
=left(begin{matrix} F_{2m+1} \F_{2m} end{matrix} right)
=left(begin{matrix}F_m^2+F_{m+1}^2\ (F_{m-1}+F_{m+1})F_{m} end{matrix} right)
=left(begin{matrix} F_m^2+F_{m+1}^2\(2F_{m+1}-F_m)F_{m} end{matrix} right)$$
$$
nrightarrow {nover2} rightarrow {nover4} rightarrow {nover8} cdots
$$

1
2
3
4
5
6
7
8
9
10

def fib_matrix(n):
    if n > 0:
        pf = fib_maxtrix(int(n/2))
        p1, p2 = pf[0], pf[1]
        if n % 2:
            return ((p1 ** 2 + p2 ** 2), (2 * p1 + p2) * p2)
        else:
            return ((2 * p2 - p1) * p1, (p1 ** 2 + p2 ** 2))
    else:
        return (0, 1)