斐波那契数列： 从第三项开始，每一项的值是前两项的和。 第一项和第二项为 1.

即 1 1 2 3 5 8 13 21 34 55 89…
计算第n项的值。

public class Fib {
// 递归实现斐波那契,时间复杂度为O(2^n) 空间复杂度为 S(n)
public static int fib(int n){
if (n<=2){
return 1;
}else{
return fib(n-1)+fib(n-2);
}
}

  1. // 时间复杂度为O(n)<br />    public static int fib2(int n){<br />        int a = 1,b=1;<br />        return fib(n,a,b);<br />    }<br />    public static int fib(int n,int a,int b){<br />        if (n<=2) return a;<br />        else{<br />            return fib(n-1,b,a+b);<br />        }<br />    }
  4. // 循环实现斐波那契<br />    public static int fac(int n){<br />        int a = 1; int b = 1; int c = 0;<br />        for (int i = 3; i<=n;i++){<br />            c = a+b;<br />            a = b;<br />            b = c;<br />        }<br />        return c;<br />    }<br />    public static void main(String[] args) {<br />        System.out.println(fac(5));<br />    }<br />}