首页 > 试题广场 > 斐波那契数列
[编程题]斐波那契数列
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。

n<=39

1461个回答

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

编辑于 2015-06-19 17:21:55 回复(70)

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]
发表于 2017-10-07 19:13:09 回复(10)
思路:
用循环,最好不要用递归
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;

    }
}

发表于 2015-12-23 23:29:40 回复(18)
迭代方法,用两个变量记录fn-1和fn-2:
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;
    }
};

发表于 2015-10-17 07:44:34 回复(8)
这个题可以说是迭代(Iteration) VS 递归(Recursion),
f(n) = f(n-1) + f(n-2),第一眼看就是递归啊,简直完美的递归环境,递归肯定很爽,这样想着关键代码两三行就搞定了,注意这题的n是从0开始的:
if(n<=1) return n;
else return Fibonacci(n-1)+Fibonacci(n-2);
然而并没有什么用,测试用例里肯定准备着一个超大的n来让Stack Overflow,为什么会溢出?因为重复计算,而且重复的情况还很严重,举个小点的例子,n=4,看看程序怎么跑的:
Fibonacci(4) = Fibonacci(3) + Fibonacci(2);
                    = Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
                    = Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
由于我们的代码并没有记录Fibonacci(1)和Fibonacci(0)的结果,对于程序来说它每次递归都是未知的,因此光是n=4时f(1)就重复计算了3次之多。
那么如何求解呢,动态规划似乎不错,关于动态规划三个条件:最优子结构、无后效性、子问题重叠这些就不谈了,因为理(wo)论(ye)性(bu)太(tai)强(dong)了。
下例是一个简单的动态规划,以一定的空间代价避免代价更大的重复计算的栈空间浪费:
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];
虽然看起来很蠢,空间浪费了sizeof(int)*(n-1),但是对于那个超大n的测试用例应该是可以通过了,时间复杂度也达到了O(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这个测试用例,我在本地都跑过了。
编辑于 2015-10-05 18:48:28 回复(24)
给一个尾递归的解答:不是不能用递归,递归本质上是栈,可能导致栈溢出,只要避免溢出就可以了。大家不要被惯性思维所限制啊,熟悉的题目只想到了熟悉的解答,那样还是书呆子!

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

编辑于 2017-03-23 23:46:01 回复(12)
看到大家的代码,好像或多或少都有点瑕疵,这里我放上一个瑕疵相对较少的版本:
/*
整体思路:考虑负数,大数,算法的复杂度,空间的浪费
*/

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

编辑于 2016-04-26 15:02:26 回复(14)
/*
	 * 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;
	}
	
}

发表于 2016-08-06 19:25:47 回复(17)
要求输出斐波那契数列的第n项,可以理解为数组下标从1开始。
可以通过javascript中的尾递归和柯里化方法实现,减少因递归产生的栈溢出的现象。
对于尾递归来说,由于只存在一个调用帧,所以永远不会发生“栈溢出”错误。
这种方法的优势在于,无论n取多大,永远不会出现栈溢出。
//柯里化
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);
}
编辑于 2018-04-12 16:30:14 回复(0)
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;

    }

}

发表于 2017-12-01 21:54:34 回复(2)
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;

    }
}


发表于 2015-04-12 22:21:47 回复(0)

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

编辑于 2017-08-25 17:27:37 回复(0)
总之不能用递归!
发表于 2015-06-01 21:34:04 回复(9)
//就记录前面计算的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];
	 }
}

编辑于 2017-06-29 11:06:56 回复(17)

//时间复杂度为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;     } };

编辑于 2017-12-20 09:55:49 回复(3)
  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;
    }

发表于 2017-03-18 11:31:16 回复(0)
/*
*方法一:递归,不考虑,有大量的重复计算,会导致内存溢出
*/
/*
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;
        
        
    }
}
发表于 2016-08-10 16:21:31 回复(0)
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;
    }
};

发表于 2018-05-02 22:47:12 回复(0)
# -*- 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    
           
发表于 2017-09-19 16:10:38 回复(0)
难受,用递归提示运行时间超过,只能用简单的for循环了
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;
    }
}

发表于 2017-03-31 17:48:46 回复(0)
public class Solution {
    public int Fibonacci(int n) {
		return n<=0 ? 0 :n<=2 ? 1 : Fibonacci(n-1) + Fibonacci(n-2);
    }
}
简单粗暴,拿走不谢!

发表于 2017-08-23 07:03:38 回复(2)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号