今天要给大家分享的实例就是和斐波那契数列相关的内容，下面一起来看看相关题目以及问题的解决思路和代码实现方式吧!
题目：
输入一个整数n，请输出斐波那契数列的第n项
注：
从0开始，第0项为0，第1项是1
n<=39
思路1：
尾递归
代码实现：
public class Solution {
public int Fibonacci(int n) {
return Fibonacci(n,0,1);
}
private static int Fibonacci(int n,int acc1,int acc2){
if(n==0) return 0;
if(n==1) return acc2;
else return Fibonacci(n - 1, acc2, acc1 + acc2);
}
}思路2：
考虑负数，大数，算法的复杂度，空间的浪费。
代码实现：
public class Solution {
public int Fibonacci(int n) {
//方法1：用递归，系统会让一个超大的n来让Stack Overflow，所以
//递归就不考虑了
//使用迭代法，用fn1和fn2保存计算过程中的结果，并复用起来
int fn1 = 1;
int fn2 = 1;
//考虑出错情况
if (n <= 0) {
return 0;
}
//第一和第二个数直接返回
if (n == 1 || n == 2) {
return 1;
}
//当n>=3时，走这里，用迭代法算出结果
//这里也说明了，要用三个数操作的情况，其实也可以简化为两
//个数，从而节省内存空间
while (n-- > 2) {
fn1 += fn2;
fn2 = fn1 - fn2;
}
return fn1;
}
}思路3
代码实现：
/*
* O(logN)解法：由f(n) = f(n-1) + f(n-2)，可以知道
* [f(n),f(n-1)] = [f(n-1),f(n-2)] * {[1,1],[1,0]}
* 所以最后化简为:[f(n),f(n-1)] = [1,1] * {[1,1],[1,0]}^(n-2)
* 所以这里的核心是：
* 1.矩阵的乘法
* 2.矩阵快速幂（因为如果不用快速幂的算法，时间复杂度也只能达到O(N)）
*/
public class Solution {
public int Fibonacci(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
//底
int[][] base = {{1,1},
{1,0}};
//求底为base矩阵的n-2次幂
int[][] res = matrixPower(base, n - 2);
//根据[f(n),f(n-1)] = [1,1] * {[1,1],[1,0]}^(n-2)，f(n)就是
//1*res[0][0] + 1*res[1][0]
return res[0][0] + res[1][0];
}
//矩阵乘法
public int[][] multiMatrix(int[][] m1,int[][] m2) {
//参数判断什么的就不给了，如果矩阵是n*m和m*p,那结果是n*p
int[][] res = new int[m1.length][m2[0].length];
for (int i = 0; i < m1.length; i++) {
for (int j = 0; j < m2[0].length; j++) {
for (int k = 0; k < m2.length; k++) {
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;
}
/*
* 矩阵的快速幂：
* 1.假如不是矩阵，叫你求m^n,如何做到O(logn)？答案就是整数的快速幂：
* 假如不会溢出，如10^75,把75用用二进制表示：1001011,那么对应的就是：
* 10^75 = 10^64*10^8*10^2*10
* 2.把整数换成矩阵，是一样的
*/
public int[][] matrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];
//先把res设为单位矩阵
for (int i = 0; i < res.length; i++) {
res[i][i] = 1;
} //单位矩阵乘任意矩阵都为原来的矩阵
//用来保存每次的平方
int[][] tmp = m;
//p每循环一次右移一位
for ( ; p != 0; p >>= 1) {
//如果该位不为零，应该乘
if ((p&1) != 0) {
res = multiMatrix(res, tmp);
}
//每次保存一下平方的结果
tmp = multiMatrix(tmp, tmp);
}
return res;
}
}以上就是今天的实例分享了，更多相关实例请继续关注本站的java实例栏目了解吧。
推荐阅读：