欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

斐波那契数列实现

程序员文章站 2024-03-16 16:00:58
...

使用递归和非递归方式实现fibonacci数列,从输出结果分析:递归的执行效率低。

package com.sg.fibonacci;


public class FibonacciMain {

    public static void main(String[] args) {
        int num = 40;
        long begin = 0l;
        long end = 0l;
        
        begin= System.currentTimeMillis();
        System.out.print("Number "+num+" fibonacci value -> " +finnonacciTraversal(num));
        end = System.currentTimeMillis();
        System.out.println(" spend time: " + (end - begin));
        
        begin = System.currentTimeMillis();
        System.out.print("Number "+num+" fibonacci value -> " +fibonacciRecursive(num));
        end = System.currentTimeMillis();
        System.out.println(" spend time: " + (end - begin));
    }

    /**
     * 使用递归实现fibonacci数列
     * @param count 获取第count结果
     * @return
     */
    public static int fibonacciRecursive(int count){
        if(count == 1 || count == 2) {
            return 1;
        }else {
            int temp = fibonacciRecursive(count-1)+fibonacciRecursive(count-2);
            
            return temp;
        }
    }
    
    /**
     * 使用遍历的方式生成fibonacci数列
     * @param 获取第count结果
     * @return
     */
    public static int finnonacciTraversal(int count) {
        int f2 = 1;
        int f1 = 1;
        
        int temp = 0;
        for(int i=2;i<count;i++) {
            temp = f2;
            f2 = f1 + f2;
            f1 = temp;
        }
        
        return f2;
    }
}

 

Number 40 fibonacci value -> 102334155 spend time: 1
Number 40 fibonacci value -> 102334155 spend time: 811