计算斐波那契数（java）

• 2021 年 2 月 18 日
• 笔记
• 算法

计算斐波那契数

【lintcode】366
描述
　查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指：
　　前2个数是 0 和 1 。
　　第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
　　0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …

以下是用java代码解决的几种方式实现

package com.recursive;

import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Scanner;

/**
 * 计算斐波那契数
 * 数列：0 1 1 2 3 5 8 13 21 34  55 89。。。。。
 * 下标：0 1 2 3 4 5 6 7  8   9  10 11.。。。。
 * 下标：1 2 3 4 5 6 7 8  9  10  11 12
 * <p>
 * fib(0) = 0
 * fib(1) = 1
 * fib(n) = fib(n-2) + fib(n-1) n>=2
 */
public class ComputerFibonacci {

    public static void main(String[] args) {
        int n = 44;
//        Scanner input = new Scanner(System.in);
//        System.out.println("请输入要计算的斐波那契数的下标值（从0开始）：");
//        int n = input.nextInt();

        long startTime = System.currentTimeMillis();
        System.out.println("递归方法输入的斐波那契数的下标值： " + n + ",对应的斐波那契数为 ： " + fibonacciRecursive(n));
        long endTime = System.currentTimeMillis();
        long time = endTime - startTime;
        System.out.println("程序运行时间：" + time / 60 + "s");

        long startTime2 = System.currentTimeMillis();
        System.out.println("迭代方法输入的斐波那契数的下标值： " + n + ",对应的斐波那契数为 ： " + fibonacciIteration(n));
        long endTime2 = System.currentTimeMillis();
        long time2 = endTime2 - startTime2;
        System.out.println("程序运行时间：" + time2 / 60 + "s");

        long startTime3 = System.currentTimeMillis();
        System.out.println("for循环方法输入的斐波那契数的下标值： " + n + ",对应的斐波那契数为 ： " + fibonacciFor(n));
        long endTime3 = System.currentTimeMillis();
        long time3 = endTime3 - startTime3;
        System.out.println("程序运行时间：" + time3 / 60 + "s");

        long startTime4 = System.currentTimeMillis();
        System.out.println("尾递归方法输入的斐波那契数的下标值： " + n + ",对应的斐波那契数为 ： " + fibonacciRecursive2(n));
        long endTime4 = System.currentTimeMillis();
        long time4 = endTime4 - startTime4;
        System.out.println("程序运行时间：" + time4 / 60 + "s");
    }

    /**
     * 使用递归
     *
     * @param n
     * @return
     */
    public static int fibonacciRecursive(int n) {
        if (n == 1) {
            return 0;
        } else if (n == 2) {
            return 1;
        } else {
            return fibonacciRecursive(n - 2) + fibonacciRecursive(n - 1);
        }

    }

    /**
     * 迭代 for
     * @param n
     * @return
     */
    public static int fibonacciIteration(int n) {
        int f0 = 0,f1 = 1,currentFib = 0;
        if(n == 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }

        for (int i = 3; i <= n; i++) {
            currentFib = f0 + f1;
            f0 = f1;
            f1 = currentFib;
        }
        return currentFib;
    }

    /**
     * for循环
     *
     * @param n
     * @return
     */
    public static  int fibonacciFor(int n) {
        int a = 0;
        int b = 1;
        int c = 0;

        int ni = Integer.valueOf(n).toString().length();

        if (n == 1) {
            c = 0;
        } else if (n == 2) {
            c = 1;
        } else if (n >= 3 && ni <= 32) {
            for (int i = 3; i <= n; i++) {
                c = a + b;
                a = b;
                b = c;
            }
        }
        return c;
    }

    /**
     * 尾递归
     * @param n
     * @return
     */
    public static int fibonacciRecursive2(int n){
        return fib(n,0,1);
    }
    private static int fib(int n, int a, int b){
        if(n==1) {
            return a;
        }
        if(n==2) {
            return b;
        }
        return fib(n-1,b,a+b);

    }
}

计算结果：

递归算法参考：

//www.cnblogs.com/huan-guo/p/8489905.html