[编程题]斐波那契数列

n<=39

c++动态规划版
```class Solution {
public:
int Fibonacci(int n) {
int f = 0, g = 1;
while(n--) {
g += f;
f = g - f;
}
return f;
}
};
```

# python solution:

``````# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
res=[0,1,1,2]
while len(res)<=n:
res.append(res[-1]+res[-2])
return res[n]
``````

```public class Solution {
public int Fibonacci(int n) {
int preNum=1;
int prePreNum=0;
int result=0;
if(n==0)
return 0;
if(n==1)
return 1;
for(int i=2;i<=n;i++){
result=preNum+prePreNum;
prePreNum=preNum;
preNum=result;
}
return result;

}
}```

```class Solution {
public:
int Fibonacci(int n) {
if(n == 0)
return 0;
if(n == 1)
return 1;
int numfn1 = 0, numfn2 = 1;
int currentnum;
for(int i=2; i<=n; ++i) {
currentnum = numfn1+numfn2;
numfn1 = numfn2;
numfn2 = currentnum;
}
return currentnum;
}
};```

f(n) = f(n-1) + f(n-2)，第一眼看就是递归啊，简直完美的递归环境，递归肯定很爽，这样想着关键代码两三行就搞定了，注意这题的n是从0开始的：
```if(n<=1) return n;
else return Fibonacci(n-1)+Fibonacci(n-2);```

Fibonacci(4) = Fibonacci(3) + Fibonacci(2);
= Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
= Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);

```if(n<=1){
return n;
}
int[] record = new int[n+1];
record[0] = 0;
record[1] = 1;
for(int i=2;i<=n;i++){
record[i] = record[i-1] + record[i-2];
}
return record[n];```

```public static int[] record = null;
public int Fibonacci(int n){
if(n<=1){
return n;
}
if(null == record){
record = new int[n+1];
}
if(0!=record[n-2] && 0!=record[n-1]){
record[n] = record[n-2] + record[n-1];
} else {
return Fibonacci(n-2) + Fibonacci(n-1);
}
}```
P.S. 最后一种方法，提交时死活过不了输入5，输出5这个测试用例，我在本地都跑过了。

```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);

}
}```

```/*
* 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;
}

}```

```//柯里化
function currying(fn, n1, n2) {
return function (m) {
return fn.call(this, m, n1, n2);
};
}
function tailFibonacci(n, ac1, ac2){
if(n==0) { return 0; }
if(n ==1 || n== 2) { return ac2 };
return tailFibonacci (n - 1, ac2, ac1 + ac2);
}
function Fibonacci(n){
return currying(tailFibonacci,1,1)(n);
}

//尾递归
function tailFibonacci(n, ac1, ac2){
if(n==0) { return 0; }
if(n ==1 || n== 2) { return ac2 };
return tailFibonacci (n - 1, ac2, ac1 + ac2);
}
function Fibonacci(n){
return tailFibonacci(n, 1 , 1);
}```

```/*

*/

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;
}
}```

```public class Solution {
public int Fibonacci(int n) {
int target=0;
if(n==0)
return 0;
if(n==1)
return 1;
int one=0;
int two=1;
for(int i=2;i<=n;i++){
target=one+two;
one=two;
two=target;
}
return target;

}
}

```

```package go.jacob.day1201;

/**
* 斐波那契数列
*
* @author Administrator 记住两个方法：1.O(n)时间复杂度用循环; 2.O(logn)用矩阵相乘 切记不要用递归
*/
public class Demo2 {
/*
* 方法一：循环 时间复杂度O(n)
*/
public int Fibonacci_1(int n) {
if (n < 1)
return 0;
if (n == 1 || n == 2)
return 1;
int res = 1;
int pre = 1;
int tmp = 0;
for (int i = 3; i <= n; i++) {
tmp = res;
res = res + pre;
pre = tmp;
}
return res;
}

/*
* 结论：F(n)=F(n-1)+F(n-2),是一个二阶递推数列，
* 一定可以用矩阵乘法的形式表示
* 这道题的递推矩阵为[1,1;1,0]
*/
public int Fibonacci_2(int n) {
if (n < 1)
return 0;
if (n == 1 || n == 2)
return 1;
int[][] base = { { 1, 1 }, { 1, 0 } };
int[][] res = maxtrixPower(base, n - 2);

return res[0][0] + res[0][1];

}

/*
* 求矩阵m的p次方
*/
private int[][] maxtrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m.length];
for (int i = 0; i < m.length; i++) {
res[i][i] = 1;
}
int[][] tmp = m;

for (; p != 0; p >>= 1) {
if ((p & 1) != 0) {
res = multiMatrix(res, tmp);
}
tmp = multiMatrix(tmp, tmp);
}

return res;
}

/*
* 求两个矩阵相乘
*/
public int[][] multiMatrix(int[][] m1, int[][] m2) {
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 < m1[0].length; k++) {
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;

}

}

```

```//就记录前面计算的n-1和n-2的值嘛
public class Solution {
public static int Fibonacci(int n) {
if (n <= 1)
return n;
int res = 0;
int n1 = 0;
int n2 = 1;
for (int i=2; i<=n; i++){
res = (n1 + n2);
n1 = n2;
n2 = res;
}
return res;
}
}```

```public class Solution {
public static int Fibonacci(int n) {
int[] ns = {0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,
10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,
2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986};
return ns[n];
}
}```

Time Complexity: O(logn)
Space Complexity: O(1)

```    def Fibonacci(self, n):
q=[[1,1],[1,0]]
if n==0: return 0
res=self.mypower(q,n-1)
return res[0][0]
def mypower(self, a, n):
ret=[[1,0],[0,1]]
while n>0:
if (n&1)==1:
ret=self.mymultiply(ret, a)
n>>=1
a=self.mymultiply(a, a)
return ret

#Matrix Multiplication
def mymultiply(self, a, b):
c=[[0 for _ in xrange(2)] for _ in xrange(2)]
for i in xrange(2):
for j in xrange(2):
c[i][j]=(a[i][0]*b[0][j]+a[i][1]*b[1][j])
return c```

/*
*方法一：递归，不考虑，有大量的重复计算，会导致内存溢出
*/
/*
public class Solution {
public int Fibonacci(int n) {

if(n<=0) {
return 0;
}
if(n==1) {
return 1;
}

returnFibonacci(n-2)+Fibonacci(n-1);

}
}
*/

/*
*方法二：使用迭代法，用fn1和fn2保存计算过程中的结果，并复用起来
*/
public class Solution {
public int Fibonacci(int n) {
int fn1 = 1;
int fn2 = 1;
if(n <= 0 ) {
return 0;
}
if(n==1 || n==2) {
return 1;
}

while(n>2) {
fn1 += fn2;
fn2 = fn1-fn2;
n--;
}
return fn1;

}
}

```  public int Fibonacci(int n) {
if (n==0) return 0;
if (n <= 2) {
return 1;
}
if (n == 3)
return 2;
int n1 = 1;
int n2 = 2;
for (int i = 4; i <= n; i++) {
n1 ^= n2;
n2 ^= n1;
n1 ^= n2;
n2 += n1;

}
return n2;
}```

```class Solution {
public:
int Fibonacci(int n) {
//递归版
//运行时间：599ms
//占用内存：480k
//        if(n <= 0)  return 0;
//        if(n == 1)  return 1;
//        if(n == 2)  return 1;
//        int fib_n = 0;
//        fib_n = Fibonacci(n -1) + Fibonacci(n - 2);
//        return fib_n;
//动态规划版
//运行时间：3ms
//占用内存：384k
if(n <= 0)  return 0;
int first = 1;
int second = 1;
while(--n  > 1){
second = first + second;
first = second - first;
}
return second;
}
};
```

```class Solution:
def Fibonacci(self, n):
# write code here
f = [0,1,1]
i=3;
while(i<=n):
f.append(f[i-1]+f[i-2])
i = i + 1
return f[n]
```

# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
list=[1,1]
num=0
if(n==1 or n==2):
return 1
else:
for i in range(3,n+1,1):
num=list[i-3]+list[i-2]
list.append(num)
return num

```public class Solution {
public int Fibonacci(int n) {
if(n<=0) return 0;
if(n==1||n==2) return 1;
int one = 1;
int two = 1;
int result = 0;
for (int i = 2; i < n; i++) {
result = one + two;
one = two;
two = result;
}
return result;
}
}```

```
//时间复杂度为logN；
//参考程序猿代码面试指南；
class Solution {
public:
int Fibonacci(int n) {
if(n<1) return 0;
if(n==1||n==2) return 1;
vector<vector<int> > base = {{1,1},{1,0}};
vector<vector<int> >  res=matrixPower(base, n-2);
return res[0][0]+res[1][0];
}

//矩阵相乘
vector<vector<int> > matrix_multiply(vector<vector<int> > arrA, vector<vector<int> > arrB)
{
int rowA=arrA.size();
int colA=arrA[0].size();
int colB=arrA[0].size();
int rowB=arrA.size();
vector<vector<int> > res (rowA,vector<int> (colB,0));
if(colA!=rowB) return res;
for(int i=0;i<rowA;i++)
{
for(int j=0;j<colB;j++)
{
for(int m=0;m<colA;m++)
res[i][j]+=arrA[i][m]*arrB[m][j];
}
}
return res;
}

vector<vector<int> > matrixPower(vector<vector<int> > a,int p)
{
vector<vector<int> > res (a.size(),vector<int> (a[0].size(),0));
for(int i=0;i<res.size();i++)
{
res[i][i]=1;
}
vector<vector<int> > tmp(a);
for(;p!=0;p>>=1)
{
if((p&1)!=0)
{
res=matrix_multiply(res,tmp);
}
tmp=matrix_multiply(tmp,tmp);
}
return res;
}
};
```

1720条回答 107573浏览

# 通过挑战的用户

• 2019-08-25 02:20:45
• 2019-08-25 02:08:31
• 2019-08-25 00:44:04
• 2019-08-25 00:21:14
• 2019-08-25 00:13:50

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题