一、相关概念

二、题目

题目

求斐波那契数列的第n项是多少

思路

• 递归，时间复杂度O(N2)。
• 为避免递归中的重复计算，从下往上计算，将已经得到的中间项保存起来，时间复杂度O(N)。

代码

import java.util.Scanner;

/**
 * 斐波那契数列：管他从第几项开始
* <p>Description: </p>  
* @author 杨丽金  
* @date 2018-9-16  
* @version 1.0
 */
public class Fib {
    public static void main(String[] args) {
        new Fib().exe();
    }
    
    private void exe(){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            int n=scan.nextInt();
            System.out.println(fib_for(n));
            System.out.println(fib_recu(n));
            
        }
    }

    /**
     * 递归求法
     * @param n
     * @return
     */
    public int fib_recu(int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        return fib_recu(n-1)+fib_recu(n-2);
    }
    
    /**
     * 循环：把已经得到的中间项保存起来，从下往上计算，复杂度O（n）
     * @param n
     * @return
     */
    public long fib_for(int n){
        int[] result={0,1};
        if(n<2){
            return result[n];
        }else{
            long fibTwo=0;// 第i-2项
            long fibOne=1;// 第i-1项
            long fibN=0;// 第i项
            for(int i=2;i<=n;i++){
                fibN=fibTwo+fibOne;
                fibTwo=fibOne;
                fibOne=fibN;
            }
            return fibN;
        }
    }
}

参考文献

斐波那契的推导