PAT 基礎級練習：結構體應用——有理數均值計算（題目 結構-05）

題目：有理數均值計算

給定 N 個有理數，求它們的平均值，結果以最簡分數形式輸出（若分母為 1 則輸出整數）。

解題思路

1. 定義結構體 rational 包含分子 numerator 和分母 denominator。
2. 讀入 N，依次讀入 N 個有理數（格式為 "分子/分母"）。
3. 通分累加：sum = a/b + c/d = (a*d + c*b) / (b*d)。
4. 每次累加後立即約分（求最大公約數 GCD），防止中間結果溢出 int 範圍。
5. 累加完成後，分子不變，分母乘以 N 得到平均值，再次約分。
6. 按格式輸出結果。

關鍵代碼實現

#include <stdio.h>

struct rational {
    int numerator;
    int denominator;
};

// 輾轉相除法求最大公約數，效率優於窮舉法
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main(void) {
    int n;
    scanf("%d", &n);
    struct rational nums[101], sum = {0, 1}; // 初始化為 0/1

    for (int i = 0; i < n; i++) {
        scanf("%d/%d", &nums[i].numerator, &nums[i].denominator);
    }

    // 累加所有有理數
    for (int i = 0; i < n; i++) {
        sum.numerator = sum.numerator * nums[i].denominator + nums[i].numerator * sum.denominator;
        sum.denominator = sum.denominator * nums[i].denominator;
        if (sum.numerator != 0) {
            int g = gcd(sum.numerator, sum.denominator);
            sum.numerator /= g;
            sum.denominator /= g;
        }
    }

    // 求平均值：分母乘以 n
    sum.denominator *= n;
    int g = gcd(sum.numerator, sum.denominator);
    sum.numerator /= g;
    sum.denominator /= g;

    // 輸出
    if (sum.denominator == 1)
        printf("%d\n", sum.numerator);
    else
        printf("%d/%d\n", sum.numerator, sum.denominator);

    return 0;
}

優化要點

• 使用輾轉相除法（歐幾里得算法）計算 GCD，時間複雜度 O(log min(a,b))，遠快於原代碼的遞減遍歷法。
• 每次累加後立即約分，有效控制中間數值大小，降低溢出風險。
• 初始化 sum = {0, 1} 而非直接賦值第一個數，使邏輯更統一。

測試樣例

輸入：
3
1/2
1/3
1/6

輸出：
1/3

驗證：(1/2 + 1/3 + 1/6) / 3 = (1) / 3 = 1/3。