斐波那契数列 相关问题 详解

斐波那契数列相关问题详解

斐波那契数列及其相关问题是算法学习中的经典主题，变形与应用非常广泛，涵盖了递推关系、动态规划、组合数学、数论等多个领域。以下是斐波那契数列的相关问题及其解法的详解。

---

1. 经典斐波那契数列

定义

• 初始条件：$F(0)=0,F(1)=1$
• 递推公式：$F(n)=F(n-1)+F(n-2)(n\ge 2)$

问题类型

• 求第 $n$ 项的值。
• 生成前 $n$ 项。
• 优化时间复杂度。

解法

1. 递归解法（时间复杂度：$O(2^n)$，会有大量重复计算）
2. 动态规划解法（时间复杂度：$O(n)$，空间复杂度：$O(n)$ 或 $O(1)$）
3. 矩阵快速幂解法（时间复杂度：$O(\log n)$）

实现代码

递归解法：

public class Fibonacci {public static int fibRecursive(int n) {if (n == 0) return 0;if (n == 1) return 1;return fibRecursive(n - 1) + fibRecursive(n - 2);}public static void main(String[] args) {System.out.println(fibRecursive(10)); // 输出：55}
}

动态规划解法：

public class Fibonacci {public static int fibDP(int n) {if (n == 0) return 0;if (n == 1) return 1;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}public static void main(String[] args) {System.out.println(fibDP(10)); // 输出：55}
}

---

2. 斐波那契数列的模运算

问题

当 $n$ 很大时，直接计算斐波那契数会导致数值爆炸。引入模运算解决：
$$F(n)=(F(n-1)+F(n-2))\mathrm{mod}M$$

解法

1. 使用动态规划加模运算。
2. 结合矩阵快速幂和模运算。

实现代码

public class FibonacciMod {public static int fibMod(int n, int mod) {if (n == 0) return 0;if (n == 1) return 1;int prev1 = 0, prev2 = 1;for (int i = 2; i <= n; i++) {int temp = (prev1 + prev2) % mod;prev1 = prev2;prev2 = temp;}return prev2;}public static void main(String[] args) {System.out.println(fibMod(1000, 1000000007)); // 输出大数的模值}
}

---

3. 变形斐波那契数列

问题1：三阶斐波那契数列

递推关系扩展为：
$$F(n)=F(n-1)+F(n-2)+F(n-3)$$

实现代码

public class Tribonacci {public static int tribonacci(int n) {if (n == 0) return 0;if (n == 1 || n == 2) return 1;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = dp[2] = 1;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];}return dp[n];}public static void main(String[] args) {System.out.println(tribonacci(10)); // 输出：149}
}

---

问题2：带权斐波那契数列

递推关系为：
$$F(n)=a\cdot F(n-1)+b\cdot F(n-2)$$

实现代码

public class WeightedFibonacci {public static int weightedFib(int n, int a, int b) {if (n == 0) return 0;if (n == 1) return 1;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = a * dp[i - 1] + b * dp[i - 2];}return dp[n];}public static void main(String[] args) {System.out.println(weightedFib(5, 2, 1)); // 输出：29}
}

---

问题3：斐波那契数列求和

求斐波那契数列前 $n$ 项的和：
$$S(n)=F(0)+F(1)+\cdots +F(n)$$

通过公式：
$$S(n)=F(n+2)-1$$

实现代码

public class FibonacciSum {public static int fibSum(int n) {if (n == 0) return 0;int a = 0, b = 1;int sum = 1; // F(0) + F(1)for (int i = 2; i <= n; i++) {int temp = a + b;a = b;b = temp;sum += b;}return sum;}public static void main(String[] args) {System.out.println(fibSum(5)); // 输出：12}
}

---

4. 斐波那契数列在矩阵中的应用

问题

斐波那契数列可以通过矩阵的形式来表示，其递推关系可以写成：
$$\left[\begin{array}{c}F(n)\\ F(n-1)\end{array}\right]\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{c}F(n-1)\\ F(n-2)\end{array}\right]$$

利用矩阵快速幂，可以在 $O(\log n)$ 时间内计算第 $n$ 项。

实现代码

public class FibonacciMatrix {public static int fibMatrix(int n) {if (n == 0) return 0;if (n == 1) return 1;int[][] F = {{1, 1}, {1, 0}};power(F, n - 1);return F[0][0];}private static void power(int[][] F, int n) {if (n == 0 || n == 1) return;int[][] M = {{1, 1}, {1, 0}};power(F, n / 2);multiply(F, F);if (n % 2 != 0) multiply(F, M);}private static void multiply(int[][] F, int[][] M) {int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];F[0][0] = x;F[0][1] = y;F[1][0] = z;F[1][1] = w;}public static void main(String[] args) {System.out.println(fibMatrix(10)); // 输出：55}
}

---

5. 斐波那契数列相关优化问题

问题：优化空间复杂度

通过滚动数组，仅存储最近两项，空间复杂度从 $O(n)$ 降低到 $O(1)$：

public class OptimizedFibonacci {public static int fib(int n) {if (n == 0) return 0;if (
n == 1) return 1;int a = 0, b = 1;for (int i = 2; i <= n; i++) {int temp = a + b;a = b;b = temp;}return b;}public static void main(String[] args) {System.out.println(fib(10)); // 输出：55}
}

---

总结

• 核心公式：斐波那契数列通过简单的递推公式定义，但其变形和扩展非常广泛。
• 常见问题：包括求第 $n$ 项、斐波那契数列求和、模运算、变形数列、矩阵快速幂等。
• 优化方向：在空间复杂度和时间复杂度上，可以通过动态规划、矩阵快速幂等方法进行优化。