題目描述：

斐波那契數(shù)，通常用?F(n)?表示，形成的序列稱(chēng)為?斐波那契數(shù)列?。該數(shù)列由?0?和?1?開(kāi)始，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和。也就是：

F(0) = 0，F(xiàn)(1)?= 1?

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

給你?n?，請(qǐng)計(jì)算?F(n)?。

遞歸法：

// 特別耗時(shí)? O(2^n)

public int fibDiGui(int n) {

????if(n<=1){

????????return n;

????}

????return fib(n-1)+fib(n-2);

}

普通計(jì)算法：

// 一般耗時(shí)? O(n)

public int fibBaoLi(int n) {

????int n1 = 0,n2=1,ns = 0;

????while(ns++<=n){

????????if(ns%2==0){

????????????n1+=n2;

????????}else{

????????????n2+=n1;

????????}

????}

????return n%2==0?n1:n2;

}