Java 經典算法練習：求 s = a + aa + aaa + ... 系列和的數學優化解法

Java 經典題目第 8 題：數字疊加系列和的 O(1) 空間、O(n) 時間優化解法

題目描述

求 s = a + aa + aaa + aaaa + ... (共 n 項) 的值，其中 a 為單個數字 (0-9)，n 由鍵盤輸入控制。
例如：a=2, n=5 → 2 + 22 + 222 + 2222 + 22222

數學規律分析

觀察每一項的結構：

第 1 項：a                    = a × 1
第 2 項：aa = a×10 + a       = a × 11
第 3 項：aaa = a×100+a×10+a  = a × 111
...
第 i 項：a × (10^(i-1) + 10^(i-2) + ... + 1) = a × (10^i - 1) / 9

系列和 S = Σ(i=1 to n) a × (10^i - 1)/9

= (a/9) × [ Σ(10^i) - Σ(1) ]

= (a/9) × [ (10^(n+1) - 10)/9 - n ]

= a × [ 10^(n+1) - 9n - 10 ] / 81

遞推關係 (編程實現友好)

第 i 項可由第 i-1 項遞推：

term_1 = a
term_i = term_(i-1) × 10 + a
sum += term_i

三種實現方案對比

方案 1：遞推累加 (推薦，無大數風險、易理解)

import java.util.Scanner;

public class SeriesSumOptimized {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        System.out.print("請輸入數字 a (0-9): ");
        int a = scanner.nextInt();
        if (a < 0 || a > 9) {
            System.out.println("輸入錯誤：a 必須是 0-9 的單個數字");
            return;
        }
        
        System.out.print("請輸入項數 n: ");
        int n = scanner.nextInt();
        if (n <= 0) {
            System.out.println("輸入錯誤：n 必須大於 0");
            return;
        }
        
        long term = 0;   // 當前項
        long sum = 0;    // 累加和
        
        StringBuilder process = new StringBuilder(); // 記錄計算過程用於顯示
        
        for (int i = 1; i <= n; i++) {
            term = term * 10 + a;  // 遞推生成當前項
            sum += term;
            
            // 顯示計算過程
            for (int j = 0; j < i; j++) {
                process.append(a);
            }
            if (i < n) process.append(" + ");
        }
        
        System.out.println(process + " = " + sum);
        scanner.close();
    }
}

方案 2：數學公式直接計算 (O(1) 時間，但大 n 溢出風險高)

public static long formulaSum(int a, int n) {
    // S = a * (10^(n+1) - 9n - 10) / 81
    // 使用 BigInteger 避免溢出
    BigInteger A = BigInteger.valueOf(a);
    BigInteger ten = BigInteger.TEN;
    BigInteger term = ten.pow(n + 1).subtract(BigInteger.valueOf(9L * n + 10));
    return A.multiply(term).divide(BigInteger.valueOf(81)).longValue();
}

方案 3：字符串拼接轉數字 (教學用，效能差)

public static long stringConcatSum(int a, int n) {
    long sum = 0;
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++) {
        sb.append(a);
        sum += Long.parseLong(sb.toString());
    }
    return sum;
}

效能與適用範圍對比

大數處理：BigInteger 版本 (支援任意大 n)