斐波那契數(shù)列

O（n）時間 O（1）空間實現(xiàn)：

http://wiki.jikexueyuan.com/project/for-offer/images/9.png" alt="" />

[java] view plaincopyprint?
public class Test09 {  
    /** 
     * 寫一個函數(shù)，輸入n，求斐波那契（Fibonacci) 數(shù)列的第n項 
     * @param n Fibonacci數(shù)的項數(shù) 
     * @return 第n項的結果 
     */  
    public static long fibonacci(int n) {  
        // 當輸入非正整數(shù)的時候返回0  
        if (n <= 0) {  
            return 0;  
        }  
        // 輸入1或者2的時候返回1  
        if (n == 1 || n == 2) {  
            return 1;  
        }  
        // 記錄前兩個（第n-2個）的Fibonacci數(shù)的值  
        long prePre = 1;  
        // 記錄前兩個（第n-1個）的Fibonacci數(shù)的值  
        long pre = 1;  
        // 記錄前兩個（第n個）的Fibonacci數(shù)的值  
        long current = 2;  
        // 求解第n個的Fibonacci數(shù)的值  
        for (int i = 3; i <= n ; i++) {  
            // 求第i個的Fibonacci數(shù)的值  
            current = prePre + pre;  
            // 更新記錄的結果，prePre原先記錄第i-2個Fibonacci數(shù)的值  
            // 現(xiàn)在記錄第i-1個Fibonacci數(shù)的值  
            prePre = pre;  
            // 更新記錄的結果，pre原先記錄第i-1個Fibonacci數(shù)的值  
            // 現(xiàn)在記錄第i個Fibonacci數(shù)的值  
            pre = current;  
        }  
        // 返回所求的結果  
        return current;  
    }  
    public static void main(String[] args) {  
        System.out.println(fibonacci(0));  
        System.out.println(fibonacci(1));  
        System.out.println(fibonacci(2));  
        System.out.println(fibonacci(3));  
        System.out.println(fibonacci(4));  
        System.out.println(fibonacci(5));  
        System.out.println(fibonacci(6));  
        System.out.println(fibonacci(7));  
    }  
}  

運行結果：

http://wiki.jikexueyuan.com/project/for-offer/images/10.png" alt="" />