求解斐波那契数列的方式

淡淡的烟草味﹌ 2022-07-16 04:26 185阅读 0赞

# 题目描述 #

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

# 输入 #

## 4 ##

## 2 ##

# 输出 #

## 3 ##

## 1 ##

import java.util.Scanner;
    
    /**
     * Created by acer on 2016/10/5.
     * 斐波那契数列:
     * 0 1 1 2 3 5
     */
    public class Fibonacci {
        
    
        //递归方式
        public int finbonacci(int n){
            if(n<=0){
                return 0;
            }
            if(n==1){
                return 1;
            }
            return finbonacci(n-1)+finbonacci(n-2);
        }
    
        /*
            优点:1.代码简洁
            缺点:1.时间和空间消耗严重,每一次调用函数，都需要在栈空间分配空间保存参数,返回地址以及临时变量，而且每次往栈里面
                  压入和弹出元素都很消耗时间
                2.由于方法调用在栈空间执行,栈空间很小，因次当递归产生的空间开销超过栈所能允许的上限时候，会产生栈溢出
                3.在斐波那契数列计算过程中，递归会产生大量的重复的计算，使其效率更低,最差情况下是O(2^n)
         */
    
    
        //循环方式
        public int fibonacci(int n){
            if(n<0||n>39){
                throw new RuntimeException("invalid input");
            }
            int[] test={
       0,1};
            if(n>=0&&n<=1){
                return test[n];
            }
            int addOne=0;
            int addTwo=1;
            int sum=0;
            for(int i=2;i<=n;i++){
                sum=addOne+addTwo;
                addOne=addTwo;
                addTwo=sum;
            }
            return sum;
        }
        //循环的特点:相比于递归的方式来讲降低了大量的重复计算，时间复杂度为O(n)
    
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            Fibonacci f=new Fibonacci();
            while(sc.hasNext()){
                int data=sc.nextInt();
                System.out.println(f.finbonacci(data));
                System.out.println(f.fibonacci(data));
            }
        }
    }