Java教程

【基础算法】java实现斐波那契数列

本文主要是介绍【基础算法】java实现斐波那契数列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

什么是斐波那契数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……
总结的规律:从第3个数开始,每个数都等于它前两个数的和。

代码实现

package com.distributedlock;
import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        System.out.println(testMethod1(10));
        System.out.println(testMethod2(10));
        System.out.println(testMethod3(10));
    }

    /**
     * 递归实现,效率不高
     * @param n
     * @return
     */
    public static int testMethod1(int n){
        if (n == 1 || n == 2) {
            return 1;
        }
        if (n > 2) {
            return testMethod1(n - 1) + testMethod1(n - 2);
        }
        return -1;
    }

    /**
     * for循环实现
     * @param n
     * @return
     */
    public static long testMethod2(int n) {
        if (n < 1) {
            return -1;
        }
        if (n ==1 || n == 2) {
            return 1;
        }
        long a =1l, b= 1l, c =0l;
        for (int i = 0; i < n - 2; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    /**
     * for循环和数组实现
     * @param n
     * @return
     */
    public static long testMethod3(int n) {
        if (n < 1) {
            return -1;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        long[] arr = new long[n];
        arr[0] = arr[1] = 1;		//第一个和第二个数据特殊处理
        for (int i = 2; i < n; i++) {
            arr[i] = arr[i -2] + arr[i - 1];
        }
        //可以得到整个的数列数据 仅n>2
        System.out.println("数组内容:" + Arrays.toString(arr));
        return arr[n - 1];
    }
}

执行效果
在这里插入图片描述

这篇关于【基础算法】java实现斐波那契数列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!