阿狗工具

1.概述

见名知意，斐波那契数列，就是数列，它的规则是这样定义的，前两个数是0和1，之后每一个数字都是前两个数字之和。

换句话说，该数列的第n个数字是前面两个数字之和（即第n-1个和第n-2个数字之和）。

下面这组数列就是斐波那契数列：

0,1,1,2,3,5,8,13,21,34,55,89,144,233.......

2.程序实现（基于Java）

现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

实现斐波那契数列的方式有很多，下面就介绍几种常用的算法：

第一种：递归法

递归法就是不断地调用自己，直到计算出第n项的斐波那契数，程序实现如下：

public static int fibonacci(int n){
    // 第一个数是0
    if(n==1){
        return 0;
    }
    // 第二个数是1
    if (n==2){
        return 1;
    }else {
        // 第三项开始为前两项数字之和。
        return fibonacci(n-2) + fibonacci(n-1);
    }
}

递归方法实现斐波那契数列的时间复杂度与空间复杂度分别是O(2^n)与O(n)，这是因为需要进行两次递归计算，递归的深度是n。

同时递归方式会在栈中保存所有的递归调用，空间复杂度是O(n)。

这种方式时间复杂度是指数级别的增长，性能会随着n增大逐渐下降，还可能会导致堆栈溢出等问题，实际并不会去选择应用递归这种方式。

第二种：记忆化递归

记忆化递归方法是对上述的普通递归方式的优化，原理是将每次算出的前两个数先保存起来然后直接使用即可，不用太多进行重复的递归计算。

代码实现：

public static int fibonacciTwo(int n){
    // 定义一个为n的数组
    int[] memo = new int[n];
    // 将数组中的每一项全部设为-1
    Arrays.fill(memo,-1);
    // 第一个数是0
    if(n==1){
        return 0;
    // 第二个数是0
    }else if(n==2){
        return 1;
    // 数组中的第n-1项目不为-1,直接返回，因为数组下标从0开始
    }else if(memo[n-1]!=-1){
        return memo[n-1];
    }else{
        // 不为-1的话需要计算。
        memo[n-1] = fibonacciTwo(n-1) + fibonacciTwo(n-2);
        return memo[n-1];
    }
}

解答思路，使用一个数组，斐波那契数列有多长我们就用多长的数组，然后将数组中的每个值都设置为一个统一标志-1。

我们将计算过的第n项值存入数组中，如果数组中的这一项值为-1.则存储，不是-1表示已经计算过直接返回即可。

由于在数组中已经存储了计算过的斐波那契数，无需重复计算，它的时间与空间复杂度都是O(n)。

第三种：迭代法

迭代法很容易的实现斐波那契数，循环计算第三项之后的每一项的值，每次将第一个与第二个值进行相加得到下一个值之后，同时更新第一个与第二个的值。

public static int fibonacciThree(int n) {
    //  第一个数字
    if (n == 1) {
        return 0;
    }
    // 第二个数字
    if (n == 2) {
        return 1;
    }
    int first = 0;
    int second = 1;
    int next = 0;
    // 从 第三项开始加
    for (int i = 2; i < n; i++) {
        // 先计算出第n项
        next = first + second;
        // 将第n-1项变为第n-2项
        first = second;
        // 然后将第n项变为第n-1项
        second = next;
    }
    // 返回第n项
    return next;

此算法的时间与空间复杂度分别是O(n)与O(1)。

上面三种方法的比较：