剑指offer刷题总结——数组篇（二）

1.斐波那契数列

【题目】

大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。

【代码】

package swear2offer.array;


public class FeiBoNaQi {
   

    /**
     * 大家都知道斐波那契数列，现在要求输入一个整数 n，
     * 请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。
     * 0,1,1,2,3,5
     * n<=39
     * */
    public int Fibonacci(int n) {
   
        if (n == 0) return 0;

        if (n == 1 || n== 2) return 1;

        return Fibonacci(n-1) + Fibonacci(n-2);
    }

    /**
     * 非递归方式，递归的数据结构使用的栈，那就是使用栈的方式
     * */
    public int NoRecursive(int n) {
   
        if (n>2) {
   
            int[] a = new int[n+1];
            a[0] = 0;
            a[1] = 1;
            a[2] = 1;

            for (int i=3; i<=n; i++) {
   
                a[i] = a[i-1] + a[i-2];
            }

            return a[n];
        } else {
   
            if (n == 0) return 0;
            else return 1;
        }
    }

    public static void main(String[] args) {
   
        System.out.println(new FeiBoNaQi().Fibonacci(39));
        System