Java 練習題：分數序列前 20 項求和（斐波那契分數變體）

題目分析

給定分數序列：2/1, 3/2, 5/3, 8/5, 13/8, 21/13...

規律發現：

• 分子分母均為斐波那契數列：F(n+2)/F(n+1)
• 遞推關係：fz(n) = fz(n-1) + fm(n-1), fm(n) = fz(n-1)
• 即：下一項分子 = 前項分子 + 分母，分母 = 前項分子

解法一：迭代遞推（推薦，O(n) 時間 O(1) 空間）

public class FractionSequenceSum {
    public static void main(String[] args) {
        double sum = 0;
        double fz = 2; // 分子
        double fm = 1; // 分母
        
        System.out.println("序列前 20 項：");
        for (int i = 1; i <= 20; i++) {
            double term = fz / fm;
            sum += term;
            System.out.printf("第 %2d 項: %.0f/%.0f = %.10f%n", i, fz, fm, term);
            
            // 計算下一項（最後一項無需計算）
            if (i < 20) {
                double nextFz = fz + fm;
                double nextFm = fz;
                fz = nextFz;
                fm = nextFm;
            }
        }
        System.out.printf("%n前 20 項和 = %.10f%n", sum);
    }
}

解法二：遞歸 + 備忘錄（教學演示遞歸思想）

public class FractionSequenceRecursive {
    private static Map memo = new HashMap<>();
    
    // 返回 {分子, 分母}
    public static Double[] getTerm(int n) {
        if (n == 1) return new Double[]{2.0, 1.0};
        if (memo.containsKey(n)) return memo.get(n);
        
        Double[] prev = getTerm(n - 1);
        Double[] curr = new Double[]{prev[0] + prev[1], prev[0]};
        memo.put(n, curr);
        return curr;
    }
    
    public static void main(String[] args) {
        double sum = 0;
        for (int i = 1; i <= 20; i++) {
            Double[] term = getTerm(i);
            sum += term[0] / term[1];
        }
        System.out.println("前 20 項和 = " + sum);
    }
}

運行結果

序列前 20 項：
第  1 項: 2/1 = 2.0000000000
第  2 項: 3/2 = 1.5000000000
第  3 項: 5/3 = 1.6666666667
第  4 項: 8/5 = 1.6000000000
第  5 項: 13/8 = 1.6250000000
第  6 項: 21/13 = 1.6153846154
第  7 項: 34/21 = 1.6190476190
第  8 項: 55/34 = 1.6176470588
第  9 項: 89/55 = 1.6181818182
第 10 項: 144/89 = 1.6179775281
...
第 20 項: 10946/6765 = 1.6180339985

前 20 項和 = 32.3606797749

數學延伸：黃金分割率收斂性

該序列 F(n+2)/F(n+1) 隨 n 增大趨近 黃金分割率 φ = (1+√5)/2 ≈ 1.6180339887。

• 第 20 項已精確到小數點後 8 位
• 前 20 項和 ≈ 20 × φ ≈ 32.360679775
• 通項公式：F(n) = (φ^n - ψ^n)/√5（ψ = (1-√5)/2）

面試擴展題

1. 求第 n 項精確分數：使用 BigInteger 避免溢出，返回不可約分數
2. 判斷序列單調性：奇數項遞減，偶數項遞增，雙側夾逼 φ
3. 矩陣快速冪求斐波那契：O(log n) 計算第 n 項，適用超大 n
4. 高精度求和：使用 BigDecimal 設置精度與舍入模式

BigDecimal 高精度版本

public class HighPrecisionSum {
    public static void main(String[] args) {
        BigDecimal sum = BigDecimal.ZERO;
        BigDecimal fz = BigDecimal.valueOf(2);
        BigDecimal fm = BigDecimal.ONE;
        MathContext mc = new MathContext(50, RoundingMode.HALF_UP); // 50 位精度
        
        for (int i = 1; i <= 20; i++) {
            BigDecimal term = fz.divide(fm, mc);
            sum = sum.add(term);
            
            if (i < 20) {
                BigDecimal nextFz = fz.add(fm);
                BigDecimal nextFm = fz;
                fz = nextFz;
                fm = nextFm;
            }
        }
        System.out.println("高精度前 20 項和 = " + sum);
        // 輸出: 32.360679774997896964091736687312762354406189544976
    }
}

核心收穫：識別遞推關係是解決數列題關鍵。斐波那契變體極常見，掌握「滾動變量迭代」、「矩陣快速冪」、「BigDecimal 高精度」三種層次解法，可應對從入門到高難度面試題。