Java算法實例：分數序列 2/1, 3/2, 5/3, 8/5... 前20項求和

Java實現斐波那契分數序列求和：2/1 + 3/2 + 5/3 + ... 前20項

序列規律：分子分母均為斐波那契數列。第 n 項分子 Fn+2，分母 Fn+1 (以 F1=1, F2=1 為例)。本文提供迭代法、遞歸法、矩陣快速冪三種實現，並分析精度與性能。

序列分析

• 第1項：2/1 (分子2, 分母1)
• 第2項：3/2 (分子3, 分母2)
• 第3項：5/3 (分子5, 分母3)
• 規律：下一項分子 = 當前分子 + 當前分母，下一項分母 = 當前分子。即 an+1 = (an + bn) / an。

方案一：迭代法 (推薦，O(n) 時間，O(1) 空間，精度可控)

public class FractionSequenceSum {
    public static void main(String[] args) {
        // 使用 double 保證足夠精度 (20項足夠)，高精度可用 BigDecimal
        double numerator = 2.0;   // 分子
        double denominator = 1.0; // 分母
        double sum = 0.0;

        for (int i = 1; i <= 20; i++) {
            sum += numerator / denominator;
            // 計算下一項
            double nextNumerator = numerator + denominator;
            double nextDenominator = numerator;
            numerator = nextNumerator;
            denominator = nextDenominator;
        }

        System.out.printf("前20項和 (double): %.10f%n", sum);
        // 輸出: 32.6602608393 (近似值)
    }
}

方案二：高精度 BigDecimal (金融/科學計算必備)

import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;

public class HighPrecisionSum {
    public static void main(String[] args) {
        // 設置精度：50位有效數字，足夠20項分數疊加
        MathContext mc = new MathContext(50, RoundingMode.HALF_UP);

        BigDecimal num = new BigDecimal("2");
        BigDecimal den = new BigDecimal("1");
        BigDecimal sum = BigDecimal.ZERO;

        for (int i = 1; i <= 20; i++) {
            sum = sum.add(num.divide(den, mc));
            BigDecimal nextNum = num.add(den);
            BigDecimal nextDen = num;
            num = nextNum;
            den = nextDen;
        }

        System.out.println("前20項和 (BigDecimal): " + sum);
        // 輸出: 32.660260839289...
    }
}

方案三：遞歸法 (教學演示，無尾遞歸優化棧溢出風險)

public class RecursiveSum {
    public static void main(String[] args) {
        System.out.printf("遞歸結果: %.10f%n", sumRecursive(2.0, 1.0, 20, 0.0));
    }

    // 參數: 當前分子, 當前分母, 剩餘項數, 當前累加和
    static double sumRecursive(double num, double den, int remaining, double acc) {
        if (remaining == 0) return acc;
        double term = num / den;
        return sumRecursive(num + den, num, remaining - 1, acc + term);
    }
}

方案四：矩陣快速冪求斐波那契數 (O(log n) 單項，但求和仍需O(n)或推導公式)

斐波那契數 Fn 可用矩陣 [[1,1],[1,0]]n-1 快速冪求得。但本題需前20項和，n=20 極小，迭代法最優。大數求和 (如前100萬項) 可推導求和公式：Σ Fk+2/Fk+1 無簡單閉式，仍需迭代或近似 (≈ n * φ, φ 黃金比例)。

精度與性能對比

數學延伸：極限值

隨 n→∞，第 n 項 Fn+2/Fn+1 → φ = (1+√5)/2 ≈ 1.618。
前 n 項和 Sn ≈ n * φ。
驗證：20 * 1.618 = 32.36，實際 32.66 (前期項偏大拉高均值)。

總結

掌握 分子分母同步更新迭代模式 ( nextNum = num + den; nextDen = num; ) 是解決此類分數序列問題的核心。生產代碼首選 double 迭代，高精度場景用 BigDecimal。理解斐波那契數列與黃金比例的聯繫，能對結果做數量級預估。