# 算法 · 深入理解 Fibonacci 数列计算及黄金分割

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

$$\begin{cases} F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n-1}+F_{n-2} &(n\geq2) \end{cases}$$

（歪个楼：列奥纳多·迪·塞尔·皮耶罗·达·芬奇，出生于1452年）

## ① Fibonacci_1(n)：定义式二分递归计算

$$fib(n)= \begin{cases} n & (if &n\leq1)\\ fib(n-1)+fib(n-2) & (if &n\geq2) \end{cases}$$

// C++
int fib1(int n){
return (2 > n) ? n : fib1(n - 1) + fib1(n - 2);
}

$$T(n)= \begin{cases} 1 & (if &n\leq1)\\ T(n-1)+T(n-2) + 1 & (if &n\geq2) \end{cases}$$

\begin{aligned} S(n)&= [T(n)+1]/2 \\ &= \begin{cases} (1+1)/2 \\ [T(n-1)+T(n-2)+1+1]/2 \\ \end{cases} \\ & = \begin{cases} (1+1)/2 \\ \{[2*S(n-1)-1] + [2*S(n-2)-1] +1 +1 ]\}/2 \end{cases} \\ & = \begin{cases} (1+1)/2 \\ [2*S(n-1) + 2*S(n-2)]/2 \\ \end{cases} \\ &= \begin{cases} 1 & (if &n\leq1)\\ S(n-1)+S(n-2) & (if &n\geq2) \end{cases} \\ \end{aligned}

$$\begin{cases} S(0) = (T(0)+1)/2 = 1 = fib(1) \\ S(1) = (T(1)+1)/2 = 1 = fib(2) \\ \end{cases}$$

\begin{aligned} & S(n)=fib(n+1)=(\phi^{n+1}-\hat{\phi}^{n+1})/\sqrt{5},\ \phi = (1+\sqrt{5})/2,\ \hat{\phi}=(1-\sqrt{5})/2 \\ & T(n) = 2*S(n)-1 = 2*fib(n+1)-1=O(\phi^{n+1})\approx O(2^n) \\ \end{aligned}

\begin{aligned} & 2^{100} = (2^{10})^{10} \approx (10^3)^{10} \\ & 2^{100}/10^9 \approx (10^3)^{10}/10^9 = 10^{21} \\ \end{aligned}

$$\begin{cases} 1 \ day = 24hr * 60min*60sec = 86400 sec \approx 25*4000 = 10^5 sec \\ 100 \ year \approx 100*365\ day \approx 3 * 10^4 day = 3* 10^9 sec \end{cases}$$

## ② Fibonacci_2(n)：线性递归计算

// C++
int fib2(int n, int& prev){
if (0 == n){
prev = 1;
return 0;
}
else {
int prevPrev;
prev = fib2(n - 1, prevPrev);
return prevPrev + prev;
}
}

## ③ Fibonacci_3(n)：迭代计算

// C++
int fib3(int n){
int f = 1, g = 0;
while (0 < n--) { g += f; f = g - f; }
return g;
}

## ④ Fibonacci_4(n)：通项公式求解

\begin{aligned} & a_1 = 1 \\ & a_2 = 1 \\ & a_n = a_{n-1} + a_{n-2} \\ \end{aligned}

$$a_n + \alpha*a_{n-1} = \beta*(a_{n-1}+\alpha*a_{n-2})$$

$$a_n = (\beta-\alpha)*a_{n-1}+\alpha*\beta*a_{n-2}$$

$$\begin{cases} a_n = a_{n-1} + a_{n-2} \\ a_n = (\beta-\alpha)*a_{n-1}+\alpha*\beta*a_{n-2} \\ \end{cases}$$

$$\begin{cases} \beta - \alpha = 1 \\ \alpha * \beta = 1 \\ \end{cases} => \begin{cases} \beta =1 + \alpha \\ \alpha*(1+\alpha)=1 \\ \end{cases} => \alpha^2+\alpha-1=0$$

\begin{aligned} \alpha_{1,2} &= \frac{-b\pm\sqrt{b^2-4ac}} {2a} \\ &= \frac{-1\pm\sqrt{1+4}}{2} \\ & = \frac{-1\pm\sqrt{5}}{2} \end{aligned}

$$\begin{cases} \alpha=\frac{\sqrt{5}-1}{2} \\ \beta=\frac{\sqrt{5}+1}{2} \\ \end{cases}$$

\begin{aligned} & T_n = a_{n}+\alpha*a_{n-1} \\ & T_{n-1} = a_{n-1}+\alpha*a_{n-2} \\ & T_{n}=\beta*T_{n-1} \end{aligned}

\begin{aligned} a_{n+1}+\alpha*a_{n}&=(a_2+\alpha*a_1)*\beta^{n-1} \\ &= (1+\alpha)*\beta^{n-1} \\ &= \beta^n \end{aligned}

\begin{aligned} & \frac{a_{n+1}+\alpha*a_{n}}{\beta^{n+1}}=\frac{\beta^{n}}{\beta^{n+1}} \\ & \frac{a_{n+1}}{\beta^{n+1}}+\frac{\alpha}{\beta}*\frac{a_n}{\beta^n}=\frac{1}{\beta} \\ \end{aligned}

$$b_n=\frac{a_n}{\beta^n}$$

$$b_{n+1}+\frac{\alpha}{\beta}b_n=\frac{1}{\beta}$$

$$b_{n+1}+\lambda = - \frac{\alpha}{\beta}(b_n+\lambda)$$

$$b_{n+1}+\frac{\alpha}{\beta}b_n=-\frac{\alpha}{\beta}\lambda-\lambda$$

$$\frac{1}{\beta} =-\frac{\alpha}{\beta}\lambda-\lambda$$

$$\lambda = -\frac{1}{\alpha+\beta}$$

$$\begin{cases} b_n+\lambda=(-\frac{\alpha}{\beta})^{n-1}(b_1+\lambda) \\ b_1 = \frac{\alpha_1}{\beta} = \frac{1}{\beta} \\ b_n = \frac{a_n}{\beta^n} \\ \alpha = \frac{\sqrt{5}-1}{2} \\ \beta = \frac{\sqrt{5}+1}{2} \\ \end{cases}$$

\begin{aligned} & \frac{a_n}{\beta^n}+\lambda = (-\frac{\alpha}{\beta})^{n-1}*(\frac{1}{\beta}+\lambda) \\ & a_n-\frac{1}{\sqrt{5}}*\beta^{n}=-1*(-\alpha)^{n-1}*\beta*(\frac{1}{\beta}-\frac{1}{\sqrt{5}}) \\ \end{aligned}

\begin{aligned} a_n &= -1*(-\alpha)^{n-1}*(1-\frac{\beta}{\sqrt{5}})+\frac{1}{\sqrt{5}}*\beta^n \\ & =-1*(\frac{-(\sqrt{5}-1)}{2})^{n-1}*(\frac{1}{2})*(\frac{2*\sqrt{5}}{\sqrt{5}}-\frac{\sqrt{5}+1}{\sqrt{5}})+\frac{1}{\sqrt{5}}*(\frac{\sqrt{5}+1}{2})^n \\ &= \frac{1}{\sqrt{5}}*[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n] \end{aligned}

$$fib(n)=(\phi^{n}-\hat{\phi}^{n})/\sqrt{5},\ \phi = (1+\sqrt{5})/2,\ \hat{\phi}=(1-\sqrt{5})/2$$

// C++
int fib4(int n)
{
float var1 = (1 + sqrt(5)) / 2;
float var2 = (1 - sqrt(5)) / 2;
float var3 = sqrt(5) / 5;
return var3 * (pow(var1, n) - pow(var2, n));
}

## ⑤ 黄金分割

$$\frac{a+b}{a}=\frac{a}{b}=\phi \ (a>b>0)$$

$$\frac{1}{1}, \frac{1}{2}, \frac{2}{3}, \frac{3}{5}, \frac{5}{8}, \frac{8}{13}, \frac{13}{21}, \frac{21}{34}, ...$$

n 趋于无穷大的时候，结果就是黄金分割比例了。

$$\lim_{n \rightarrow \infty}{\frac{fib_{n+1}}{fib_{n}}} = \frac{1}{2}(1+\sqrt5)=\phi \approx 1.618...$$

【此文原创，欢迎转发，禁止搬运】