剑指Offer面试题：10.斐波那契数列

一、题目
————————————————
写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。

————————————————
二、思路
————————————————
　　如果直接写递归函数，由于会出现很多重复计算，效率非常底，不采用。
　　要避免重复计算，采用从下往上计算，可以把计算过了的保存起来，下次要计算时就不必重复计算了：先由f(0)和f(1)计算f(2)，再由f(1)和f(2)计算f(3)……以此类推就行了，计算第n个时，只要保存第n-1和第n-2项就可以了。
————————————————
三、解决问题
————————————————
测试用例

　　1.功能测试（3，5，8等）

　　2.边界值测试（0，1，2等）

　　3.性能测试（50，100等）

　　4.特殊（负数）
————————————————

package swordoffer;

/**
 * @author LQ
 * @version 1.0
 * @date 2020-03-15 16:17
 */

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

public class Solution10 {
    public static void main(String[] args) {
        Solution10 demo = new Solution10();
        System.out.println(demo.Fibonacci(0));
        System.out.println(demo.Fibonacci(1));
        System.out.println(demo.Fibonacci(2));
        System.out.println(demo.Fibonacci(8));
        System.out.println(demo.Fibonacci(50));
        System.out.println(demo.Fibonacci(100));
        System.out.println(demo.Fibonacci(-5));
    }

    public int Fibonacci(int n) {
        if(n < 0){//当n<0,不符合约束条件
            throw new RuntimeException("下标错误,应从0开始！");
        }
        if(n == 0){
            return 0;//当n=0
        }
        if(n == 1){
            return 1;//当n=1
        }
        int prePre = 0;//F(n-1)
        int pre = 1;//F(n-2)
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result = prePre + pre;//F(n)=F(n-1) + F(n-2)
            prePre = pre;//F(n-1)=F(n-2)
            pre = result;//F(n-2)=F(n)
        }
        return result;//F(n)
    }

}

————————————————

————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。