斐波那契数列，定义：
斐波那契数列.jpg
递归求解
普通递归
public int Fib(int n) {
if(n <= 1) {
return n;
}
return Fib(n-1) + Fib(n - 2);
}
尾递归
public int Fib(int n) {
return Fib(n, 0, 1);
}
public int Fib(int n, int acc1, int acc2) {
if(n == 0)
return 0;
if(n == 1)
return acc2;
return Fib(n -1, acc2, acc1 + acc2);
}
非递归递推解
public int Fib(int n) {
int []a = new int[1000];
a[0] = 0;
a[1] = 1;
for(int i = 2; i < 1000; i++) {
a[i] = a[ i-1 ] + a[ i-2 ];
}
return a[n];
}
利用矩阵计算
通过矩阵的快速幂实现
public int Fib(int n) {
Matrix ans = new Matrix(1, 0, 0, 1);
Matrix base = new Matrix(1, 1, 1, 0);
while(n > 0) {
if((n & 1) == 1) {
ans = mlti(base, ans);
}
base = mlti(base, base);
n >>= 1;
}
printM(ans);
return ans.m[1][0];
}
public Matrix mlti(Matrix a, Matrix b) {
Matrix tmp = new Matrix(0, 0, 0, 0);
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
for(int k = 0; k < 2; k++) {
tmp.m[i][j] = tmp.m[i][j] + a.m[i][k] * b.m[k][j];
}
}
}
return tmp;
}
Matrix.class:
public class Matrix {
public int[][] m = new int[2][2];
public Matrix(int a, int b, int c, int d) {
m[0][0] = a;
m[0][1] = b;
m[1][0] = c;
m[1][1] = d;
}
}
