Leibniz formula for π

π = 4 ( 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ⋯ )

π 可以由萊布尼茲公式近似，特色是算越多項越接近pi, 因為公式都是重疊子問題，很適合用動態規劃實作

動態規劃的實作思路

1. 狀態表示： 設置一個數組 dp，其中 dp[i] 表示計算到第 i 項的累積和。
2. 狀態轉移方程： 我們有 dp[i] = dp[i-1] + ((-1) ** i) / (2 * i + 1)。這樣每次只需要加上第i項的新值，就可以得到當前的近似值。
3. 初始化： 設定 dp[0] = 4 * (1)，這是公式的第一項。

• Math.pow(-1, n): (-1)^n 因為某項跟上一項正負相反
• TC:O(n)每次疊代只用常數時間計算（-1）^n/（2*n+1)
• SC:O(1)只用previousSum, piApprox存變數且變數不會增長

def dynamic_programming_for_pi(target_pi=3.1415926, threshold=1e-7):
    """
    Approximates the value of π using the Leibniz formula for π.
    
    Parameters:
    - target_pi: 設置目標 pi 和精度閾值
    - threshold: 控制逼近的精確度
    
    Returns:
    - pi_approx: The approximated value of π.
    - terms_used: The number of terms used to reach the approximation.
    """
    n = 1  # 初始項數
    pi_approx = 4.0  # dp[0] 的值
    previous_sum = 1.0  # 第一項的值
    terms = [1.0] # 記錄每一項的值
    while abs(pi_approx - target_pi) >= threshold:
        # 計算第 n 項，使用動態累積和
        if n < len(terms):
            term = terms[n]        
        else:
            term = ((-1) ** n) / (2 * n + 1)
            terms.append(term)
        
        previous_sum += term
        pi_approx = 4 * previous_sum
        n += 1  # 增加項數

    return pi_approx, n

Java

public class PiApproximation {
    public static void main(String[] args) {
        double targetPi = 3.1415926;
        double threshold = 1e-7; // 控制逼近的精確度

        double piApprox = approximatePi(targetPi, threshold);
        System.out.println("逼近的 pi 值: " + piApprox);
    }

    public static double approximatePi(double targetPi, double threshold) {
        int n = 1; // 初始項數
        double previousSum = 1.0; // 第一項的值
        double piApprox = 4 * previousSum; // 初始化的 pi 近似值
        int sign = -1; // 從第二項開始，符號交替，初始設置為 -1

        while (Math.abs(piApprox - targetPi) >= threshold) {
            // 直接計算下一項，並切換符號
            double term = sign / (double) (2 * n + 1);
            previousSum += term;
            piApprox = 4 * previousSum;
            sign = -sign; // 符號切換
            n++; // 增加項數
        }

        System.out.println("使用的項數: " + n);
        return piApprox;
    }
}

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)