算法之斐波那契数列如何求第n个值与前n项和？（Java）

指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）。

1.1.求斐波那契数列的第n项的值 2.2.求斐波那契数列前n项的和

2.1.求第n项的值 输入：6 输出：8

2.2.求前n项的和 输入：6 输出：20

3.1.求第n项的值 3.1.1找出斐波那契数列的规律，用不断的递归解决，但递归的时间复杂度为O(2^n)。

3.1.2另一种方式是自底向上求解，从1，2推导3。再从2，3推导出4。也就是说，我们想要求第n项的值的话，只需要知道n-1和n-2的值就可以了，而不需要像递归那样所有的值都求出来。

3.2.求前n项的和 3.2.1在递归的基础上，再加一个sum存储前n项的和

3.2.2求前n项的和我们可以推导出一条公式：Sn = A(n+2) - 1。我们可以直接用求第n项的值的方法来求出A(n+2) - 1，就可以得出前n项的和了。 这个公式是怎么得到的呢？很简单。

求和：Sn=a1+a2+a3+……+An

       Sn=a3+a2+a3+……+An-1

       Sn=a4+a3+……+An-1……

       Sn=An+A(n-1)+An-1

 public static int f(int n) throws Exception {         if(n==0){            throw new Exception("参数错误！");         }         if (n == 1 || n == 2) {             return 1;         } else {             return f(n-1)+f(n-2);//自己调用自己         }  }

    public static int FibonacciSum(int n) {         int sum = 0;         for(int i=1;i         int f1 = 1;         int f2 = 1;         int prePreFib = f1;         int preFib = f2;         int fib = 0;         int flag = 2;

        if (n == 1 || n == 2){             return f1;         }         if (n >= 3){             while (flag < n){                 fib = preFib + prePreFib;                 prePreFib = preFib;                 preFib = fib;                 flag++;             }         }         return fib;     }  

    private int fibonacciSum(int n){         return fibonacci(n+2) - 1;     }  

题目要求：编写程序在控制台输出斐波那契数列前20项，每输出5个数换行

斐波那契数列指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

这个数列从第三项开始，每一项都等于前两项之和。

这道兔子题的实质就是斐波那契数列： 有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少?，现在从变量、数组、递归三个角度出发解决这个puzzle,当然还有其它的方法，同一道题用各种不同的思路去思考解决，也是对知识综合运用的锻炼吧。

关于斐波那契数列的优化 https://blog.csdn.net/dadai_/article/details/50209511