AI工具人

# 面试题精选:神奇的斐波那契数列

f0 = 0
f1 = 1
f(n) = f(n-1) + f(n-2)

### 递归求解

``````    private static long fibonacci(int n) {
if (n == 0) {
return 0L;
}
if (n == 1) {
return 1L;
}
return fibonacci(n-1) + fibonacci(n-2);
}``````

``````                          fib(5)
/                \
fib(4)                fib(3)
/        \              /       \
fib(3)      fib(2)         fib(2)   fib(1)
/    \       /    \        /      \
fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
/     \
fib(1) fib(0)``````

### 递推求解

``````    private static long fibonacci(int n) {
long[] fb = new long[n+1];
fb[1] = 1;
for (int i = 2; i &lt;= n; i++) {
fb[i] = fb[i-1] + fb[i-2];
}
return fb[n];
}``````

``````    private static long fibonacci(int n) {
if (n &lt; 2) {
return n;
}
long fa = 0L;
long fb = 1L;
long fc = fa + fb;
for (int i = 2; i &lt; n; i++) {
fc = fa + fb;
fa = fb;
fb = fc;
}
return fc;
}``````

### 矩阵幂运算

``````>&gt;fb = [1,1;1,0]
fb =
1   1
1   0

>&gt;fb^10
ans =
89   55
55   34

>&gt;fb^30
ans =
1346269    832040
832040    514229``````

``````    // 快速求矩阵的n次方
private static long[][] pow(long[][] matrix, int n) {
if (n == 1) {
return matrix;
}
long[][] res = pow(matrix, n/2);
res = multi(res, res);
if (n%2 == 1) {
res = multi(res, matrix);
}
return res;
}
// 两个矩阵相乘
private static long[][] multi(long[][] m1,  long[][] m2) {
long[][] res = new long[2][2];
res[0][0] = m1[0][0]*m2[0][0] + m1[0][1]*m2[1][0];
res[0][1] = m1[0][0]*m2[0][1] + m1[0][1]*m2[1][1];
res[1][0] = m1[1][0]*m2[0][0] + m1[1][1]*m2[1][0];
res[1][1] = m1[1][0]*m2[0][1] + m1[1][1]*m2[1][1];
return res;
}

public static void main(String[] args) {
long[][] fb = {{1,1},{1,0}};
long[][] res = pow(fb, 10);
System.out.println(res[0][1]);
}``````

### 面试题扩展

1. 你每次可以上1级台阶，或者2级台阶，问：上到第n级台阶总共有多少种不同的路径？
2. fib(i)对应的是斐波那契的第i项，找到所有第fin(i)个素数(i<=20)，比如fib(20)是6765，第6765个素数是67931。