斐波那契数列 相关问题 详解
斐波那契数列相关问题详解
斐波那契数列及其相关问题是算法学习中的经典主题，变形与应用非常广泛，涵盖了递推关系、动态规划、组合数学、数论等多个领域。以下是斐波那契数列的相关问题及其解法的详解。
1. 经典斐波那契数列
定义
- 初始条件： F ( 0 ) = 0 , F ( 1 ) = 1 F(0) = 0, F(1) = 1 F(0)=0,F(1)=1
- 递推公式： F ( n ) = F ( n − 1 ) + F ( n − 2 ) ( n ≥ 2 ) F(n) = F(n-1) + F(n-2) \ (n \geq 2) F(n)=F(n−1)+F(n−2) (n≥2)
问题类型
- 求第 n n n 项的值。
- 生成前 n n n 项。
- 优化时间复杂度。
解法
- 递归解法（时间复杂度： O ( 2 n ) O(2^n) O(2n)，会有大量重复计算）
- 动态规划解法（时间复杂度： O ( n ) O(n) O(n)，空间复杂度： O ( n ) O(n) O(n) 或 O ( 1 ) O(1) O(1)）
- 矩阵快速幂解法（时间复杂度： O ( log n ) O(\log n) O(logn)）
实现代码
递归解法：
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
n
n 很大时，直接计算斐波那契数会导致数值爆炸。引入模运算解决：
F
(
n
)
=
(
F
(
n
−
1
)
+
F
(
n
−
2
)
)
m
o
d
M
F(n) = (F(n-1) + F(n-2)) \mod M
F(n)=(F(n−1)+F(n−2))modM
解法
- 使用动态规划加模运算。
- 结合矩阵快速幂和模运算。
实现代码
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
)
F(n) = F(n-1) + F(n-2) + F(n-3)
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
⋅
F
(
n
−
1
)
+
b
⋅
F
(
n
−
2
)
F(n) = a \cdot F(n-1) + b \cdot F(n-2)
F(n)=a⋅F(n−1)+b⋅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
n
n 项的和：
S
(
n
)
=
F
(
0
)
+
F
(
1
)
+
⋯
+
F
(
n
)
S(n) = F(0) + F(1) + \dots + F(n)
S(n)=F(0)+F(1)+⋯+F(n)
通过公式：
S
(
n
)
=
F
(
n
+
2
)
−
1
S(n) = F(n+2) - 1
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. 斐波那契数列在矩阵中的应用
问题
斐波那契数列可以通过矩阵的形式来表示，其递推关系可以写成：
[
F
(
n
)
F
(
n
−
1
)
]
[
1
1
1
0
]
⋅
[
F
(
n
−
1
)
F
(
n
−
2
)
]
\begin{bmatrix}F(n) \\F(n-1)\end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} F(n-1) \\ F(n-2) \end{bmatrix}
[F(n)F(n−1)][1110]⋅[F(n−1)F(n−2)]
利用矩阵快速幂，可以在 O ( log n ) O(\log n) O(logn) 时间内计算第 n 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(n) O(n) 降低到 O ( 1 ) O(1) 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 n n 项、斐波那契数列求和、模运算、变形数列、矩阵快速幂等。
- 优化方向：在空间复杂度和时间复杂度上，可以通过动态规划、矩阵快速幂等方法进行优化。