PAT 基礎編程 循環-10：分數序列前 N 項和求解與優化完全指南

PAT 基礎編程 循環-10：分數序列前 N 項和求解與優化完全指南

浙江大學 PAT 甲級/乙級「循環-10」題目要求計算特定分數序列前 N 項和。本文從遞推關係建模、迭代實現、遞歸替代方案、精度控制、邊界處理五個維度，提供完整解題框架與代碼範式。

題目需求精讀

• 序列定義：2/1, 3/2, 5/3, 8/5, 13/8, ...
• 遞推規律：分子分母均為斐波那契數列，a[n] = a[n-1] + a[n-2]
• 輸入：正整數 N
• 輸出：前 N 項和，保留 2 位小數

數學建模：分子分母雙遞推

設第 i 項為 num[i] / den[i]，則：

num[1] = 2, den[1] = 1
num[i] = num[i-1] + den[i-1]
den[i] = num[i-1]

驗證：

方案一：標準迭代法（推薦，O(N) 時間 O(1) 空間）

#include <stdio.h>

int main() {
    int N;
    scanf("%d", &N);
    
    double sum = 0.0;
    int num = 2, den = 1;  // 第一項
    
    for (int i = 1; i <= N; i++) {
        sum += (double)num / den;
        // 更新下一項分子分母
        int next_num = num + den;
        int next_den = num;
        num = next_num;
        den = next_den;
    }
    
    printf("%.2f\n", sum);
    return 0;
}

方案二：遞歸實現（教學演示，注意棧溢出風險）

#include <stdio.h>

float series_sum(int n) {
    if (n == 1) return 2.0f;  // 基例
    // 遞歸計算前 n-1 項和，再加第 n 項
    // 需輔助函數計算第 n 項值
    return series_sum(n-1) + term_value(n);
}

float term_value(int n) {
    if (n == 1) return 2.0f;
    if (n == 2) return 1.5f;
    // 實際需傳遞分子分母或用全局狀態，遞歸不適合此題
    return 0; // 佔位
}

評價： 遞歸此處屬於「為遞歸而遞歸」，增加函數調用開銷且難維護狀態，不推薦實戰使用。

方案三：優化版迭代（單變量滾動，極致簡潔）

#include <stdio.h>

int main() {
    int N;
    scanf("%d", &N);
    
    double sum = 0;
    double a = 2.0, b = 1.0;  // 用 double 直接存分子分母，避免轉換
    
    for (int i = 0; i < N; i++) {
        sum += a / b;
        double next_a = a + b;
        b = a;
        a = next_a;
    }
    
    printf("%.2f\n", sum);
    return 0;
}

精度與溢出風險控制

邊界測試用例

# N=1
輸入: 1
輸出: 2.00

# N=2
輸入: 2
輸出: 3.50

# N=10
輸入: 10
輸出: 16.48  # 手工驗證前10項和

# N=0 (若題目允許)
輸入: 0
輸出: 0.00  # 循環 0 次，sum 保持 0

相關變體題目延伸

1. 前 10 項和固定值：無需輸入，直接輸出常量
2. 通用斐波那契分數序列：任意初始值 a/b, c/d
3. 高精度輸出：要求 10 位小數，需 long double 或大數庫
4. 矩陣快速冪優化：O(log N) 求第 N 項（大 N 場景）

解題模板速記卡

#include <stdio.h>

int main() {
    int N;
    if (scanf("%d", &N) != 1) return 0;  // 輸入驗證
    
    double sum = 0;
    double num = 2, den = 1;
    
    for (int i = 0; i < N; i++) {
        sum += num / den;
        double tmp = num;
        num = num + den;
        den = tmp;
    }
    
    printf("%.2f\n", sum);
    return 0;
}

分數序列求和是「遞推建模 + 迭代實現 + 精度控制」三位一體的經典訓練場。掌握雙變量滾動更新模式，可輕松應對斐波那契、兔子繁殖、樓梯跳躍等同構問題。建議動手對比 int/double/long long 三種類型在 N=50 時的表現，體會數值計算的工程權衡。