剑指 offer之斐波那契数列_Java

2019/7/21 13:32:08 人评论 次浏览 分类:学习教程

题目:斐波那契数列
题目描述
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39

解题思路:
斐波纳契数列,又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)。

(1)使用递归:解法直观,但是时间效率极低
(2)用循环实现
(3)数学公式:由于隐含的时间常数较大,很少有软件采用这种算法。
这里实现的分别是第一种和第二种思路。

代码实现:
第2种方法:递归

public class Solution {
    public int Fibonacci(int n) {
        //从0开始,第0项为0
        if(n==0) {
			return 0;
		}
        //第一项
		if(n==1) {
			return 1;
		}
        //递归实现斐波那契数列的第n项
		return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

第2种方法:循环

public class Solution {
    public int Fibonacci(int n) {
        //从0开始,第0项为0
       if(n==0) {
			return 0;
		}
        //第一项为1
		if(n==1) {
			return 1;
		}
        //第n-1项
		int preOne=1;
        //第n-2项
		int preTwo=0;
        //用来表示此时斐波那契数列的第n项
		int sum=0;
		for(int i=2;i<=n;i++){
			sum=preOne+preTwo;
			preTwo=preOne;
			preOne=sum;
		}
		return sum;
    }
}

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->