斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)。

第一种数组实现方法:基于数组实现

/**
 * @author 薛定谔的猫
 * 斐波拉契数列数组实现
 * 求前二十项*/
public class Main {
    public static void main(String[] args) {
        getFib(20);
    }
     
    public static int getFib(int n){//核心函数
        if (n<0) {
            return -1;//小于0是没有意义的
        }else if (n == 0) {
            return 0;//等于0其实也没什么意义
        }else if (n == 1||n == 2) {
            return 1;//第一项和第二项都是1
        }else {
            int[] fibAry = new int[n + 1];
            fibAry[0] = 0;
            fibAry[1] = fibAry[2] = 1;
             
            for(int i = 3;i<=n;i++) {
                fibAry[i] = fibAry[i-1] + fibAry[i-2];//当前项等于后一项加上后两项
                System.out.println("第" + i + "项"+fibAry[i]);//输出当前项
            }
            return fibAry[n];//返回当前项
        }
    }
}
 
 

第二种实现方法:基于变量实现

/**
 * @author 薛定谔的猫
 * 斐波拉契数列变量实现
 * 求前二十项*/
public class Main {
    public static void main(String[] args) {
        getFib(20);
    }
     
    public static int getFib(int n){//核心函数
        if (n<0) {
            return -1;//小于0是没有意义的
        }else if (n == 0) {
            return 0;//等于0其实也没什么意义
        }else if (n == 1||n == 2) {
            return 1;//第一项和第二项都是1
        }else {
            int temp = 0;//当前项变量
            int a = 1;//第一项
            int b = 1;//第二项
             
            for(int i = 3;i<=n;i++) {
                //变量互换值
                temp = a+b;//当前项等于前两项相加
                a = b;//前两项互换值
                b = temp;//当前项赋值给前一项
                System.out.println("第" + i + "项"+temp);//输出当前项
            }
            return temp;//返回当前项
        }
    }
}
  

 

第三种实现方法:递归实现(用递归的都是神)

递归定义:简单的说就是自己调用自己。

 
/**
 * @author 薛定谔的猫
 * 斐波拉契数列变量实现
 * 求前二十项
 * 这种方法最简单,但是最占用内存,特别是当n很大的时候
 *
 *
 * 为什么递归得效率低?
 * 递归效率低是函数调用的开销导致的。在一个函数调用之前需要做许多工作,
 * 比如准备函数内局部变量使用的空间、搞定函数的参数等等,这些事情每次调用函数都需要做
 * ,因此会产生额外开销导致递归效率偏低,所以逻辑上开销一致时递归的额外开销会多一些当然了,
 * 通过有意识的组织代码的写法可以把某些递归写成尾递归,尾递归可以进行特殊的优化所以效率
 * 会比普通的递归高一些,也不会因为递归太多导致栈溢出遍历树还不用递归的话,那么人肉写一个栈
 * +深度优先遍历或者人肉队列+广度优先遍历,再辅以黑魔法给栈或者队列提速,应该会比递归快一些,
 * 加速幅度和语言和写法相关,但在大多数情况下我觉得是得不偿失的,花了很大精力很可能效率提升不
 * 明显
 *
 * 此回答转自知乎
 
 * */
public class Main {
    public static void main(String[] args) {
        for(int i = 1;i<=20;i++) {
        System.out.println("第" +i + "项" + getFib(i));
        }
    }
     
    public static int getFib(int n){//核心函数
        if (n<0) {
            return -1;//小于0是没有意义的
        }else if (n == 0) {
            return 0;//等于0其实也没什么意义
        }else if (n == 1||n == 2) {
            return 1;//第一项和第二项都是1
        }else {
                return getFib(n-1) + getFib(n-2);//返回当前项,核心递归
            }
        }
    }