斐波那契数列.md

斐波那契数列

求斐波那契数列第n项的值，斐波那契数列定义如下 $$ F(n) = F(n-1) + F(n-2) $$ 其中： $ F(0) = 0, F(1) = 1$ 例如

$$F(3) = F(2) + F(1) = F(1)+F(0)+F(1) = 1+0+1 =2$$

常见解法 递归

func fib(n int){
  if n < 2 {
    return n
  }
  return fib(n-1)+fib(n-2)
}

时间复杂度$\theta{({\frac{1+\sqrt{5}}{2}}^n)}$

动态规划

func fib(n int){
  a := 0
  b := 1
  for ;n>0; {
    a, b = b, a
    b = a+b;
    n--
  }
  return a
}

时间复杂度$\theta{(n)}$

矩阵快速幂

我们首先要注意到上面的a和b实际上是在每次循环时做一个转换 $$ b \rightarrow a $$ $$ b + a \rightarrow b $$

求第n项就是将这种转换对$(0,1)$这对数进行n次转换，这时我们可以将这里的$(0,1)$看作是向量，因为我们需要对多个量进行转换，数学里最擅长表达此操作的方法就是矩阵(想一想矩阵解多元一次方程组)，如果对单独的量进行转换就是用普通的函数。

我们命名一个矩阵$T$,由于每次的转换是一样的，那么转换n次等同于将矩阵$T$应用n次到向量$\begin{pmatrix}{0}\\{1}\end{pmatrix}$

$$ f(n) = T^{n} \times \begin{pmatrix}{0}\\{1}\end{pmatrix} $$

现在我们需要求出具体的转换矩阵$T$就完成大部分任务了

$$ ? \times \begin{pmatrix}{0}\\{1}\end{pmatrix} = \begin{pmatrix}{1}\\{1}\end{pmatrix} \\ ? \times \begin{pmatrix}{1}\\{1}\end{pmatrix} = \begin{pmatrix}{1}\\{2}\end{pmatrix} \\ ? \times \begin{pmatrix}{1}\\{2}\end{pmatrix} = \begin{pmatrix}{2}\\{3}\end{pmatrix} \\ $$ 设$x_1, x_2, y_1, y_2$为矩阵$T$的项,由 $$ \begin{bmatrix}{x_1}&{y_1}\\{x_2}&{y_2}\end{bmatrix} \times \begin{pmatrix}{0}\\{1}\end{pmatrix} = \begin{pmatrix}{1}\\{1}\end{pmatrix}\\ \begin{bmatrix}{x_1}&{y_1}\\{x_2}&{y_2}\end{bmatrix} \times \begin{pmatrix}{1}\\{1}\end{pmatrix} = \begin{pmatrix}{1}\\{2}\end{pmatrix} $$ 得方程组 $$ \begin{cases} x_1\times 0+y_1 = 1\\ x_2\times 0+y_2 = 1\\ x_1 + y_1 = 1\\ x_2 + y_2 = 2 \\ \end{cases} $$ 得出矩阵$T$为$\begin{bmatrix}{0}&{1}\\{1}&{1}\end{bmatrix}$ 求第n项就是先求出$T^n$再乘上向量$\begin{pmatrix}{0}\\{1}\end{pmatrix} $ 转换为代码

func fib(n int) int {
	a, b := 0, 1
	if n == 0 {
		return a
	}
	M := T([2][2]int{{0, 1}, {1, 1}}, n)
	return M[0][0]*a + M[0][1]*b//只用返回a经过转换后的数
}

func T(matrix [2][2]int, n int) [2][2]int {//快速幂
	if n == 1 {
		return matrix
	}
	if n%2 == 0 {
		m := T(matrix, n/2)
		return matrixMul(m, m)
	} else {
		return matrixMul(matrix, T(matrix, n-1))
	}

}

func matrixMul(m1 [2][2]int, m2 [2][2]int) [2][2]int {//矩阵乘法
	return [2][2]int{
		{m1[0][0]*m2[0][0] + m1[0][1]*m2[1][0], m1[0][0]*m2[0][1] + m1[0][1]*m2[1][1]},
		{m1[1][0]*m2[0][0] + m1[1][1]*m2[1][0], m1[1][0]*m2[0][1] + m1[1][1]*m2[1][1]}}
}

此处的快速幂是递归的方式，还可以将其改为迭代的方式

func T(matrix [2][2]int, n int) [2][2]int {//快速幂
	tmp := [2][2]int{{1,0},{0,1}}//单元矩阵，等同于整数中的1
	for ;n>0;n>>=1 {
		if n&1==1 {//位与，检测最后一位是否是1，如果是则是奇数
			tmp = matrixMul(tmp, matrix)
		}
		matrix = matrixMul(matrix, matrix)
	}a
	return tmp

}