package com.cyb;
/**
 * 斐波那契数列:后一个数等于前两个数之和 0 1 1 2 3 5 8 13 21.....
 * @author chenyanbin
 *
 */
public class Main {
    /*
     * 递归方式
     */
    public static int fib1(int n) {
        if (n <= 1)
            return n;
        return fib1(n - 1) + fib1(n - 2);
    }
    /*
     * 优化后算法
     */
    public static int fib2(int n) {
        if (n <= 1) //第一个、第二个数，返回本身
            return n;
        int first = 0;
        int second = 1;
        while (n-- > 1) {
            second += first; // 第三个数=第一个数+第二个数
            first = second - first;
        }
        return second;
    }
    public static void main(String[] args) {
        Long begin = System.currentTimeMillis();
        System.out.println(fib1(40));
        Long end = System.currentTimeMillis();
        System.out.println("递归算法；开始时间:" + begin + ";结束时间:" + end + ";耗时:" + (end - begin));
        //-------------
        Long begin2 = System.currentTimeMillis();
        System.out.println(fib2(40));
        Long end2 = System.currentTimeMillis();
        System.out.println("优化后算法；开始时间:" + begin2 + ";结束时间:" + end2 + ";耗时:" + (end2 - begin2));
    }
}