題目描述

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第n項（從0開始，第0項為0）。
n<=39

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

/**
 * 題目描述
 大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第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;
    }

    

}