题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

/**
 * Created by ZengXihong 2019-06-01.
 */

/**
 * 题目描述
 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
 n<=39
 */
public class Solution7 {
    /**
     * 从 0 开始，则第 0 项为 0 ，第1 项为 1 ，第二项 = 第 0 项 + 第 1 项
     * 使用递归
     * @param n
     * @return
     */
    public int Fibonacci1(int n) {
        if(n<=1){
            return n;
        }
        return Fibonacci1(n-1)+Fibonacci1(n-2);

    }

    /**
     * 同理  第二项 = 第 0 项 + 第 1 项 
     * @param n
     * @return
     */
    public int Fibonacci2(int n) {
        if(n<=1){
            return n;
        }
        int a=0,b=1,c=a+b;
        for (int i=2;i<=n;i++){
            c=a+b;
            a=b;
            b=c;

        }
        return c;
    }

    

}