您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

三平方和問題：尋找正整數解的 C 語言實現與優化策略

編輯：關於C

問題描述

給定正整數 num (0 < num ≤ 10000)，找到滿足 x² + y² + z² = num 且 x ≤ y ≤ z 的正整數解 (x, y, z)。若有多解，輸出字典序最小的一組（即 x 最小，其次 y 最小）。

基礎三重循環實現


#include <stdio.h>

int main() {
    int num;
    while (scanf("%d", &num) != EOF && num > 0 && num <= 10000) {
        int flag = 0;
        for (int x = 1; x * x < num; x++) {
            for (int y = 1; y * y < num; y++) {
                for (int z = 1; z * z < num; z++) {
                    if (x*x + y*y + z*z == num && x <= y && y <= z) {
                        printf("%d %d %d\n", x, y, z);
                        flag = 1;
                        break;
                    }
                }
                if (flag) break;
            }
            if (flag) break;
        }
    }
    return 0;
}

性能分析與優化

問題 1：循環上界過大

原代碼 x*x < num 導致 x 最大遍歷到 √num ≈ 100，三重循環最多 100³ = 1,000,000 次迭代，雖在限制內可接受，但可大幅優化。

優化策略

利用有序性剪枝：x ≤ y ≤ z ⇒ 3x² ≤ num ⇒ x ≤ √(num/3)。
雙循環 + 直接計算：固定 x, y，計算 z² = num - x² - y²，判斷是否為完全平方數。
預計算平方表：避免重複乘法運算。

優化版實現（雙循環 + 整數平方根判斷）


#include <stdio.h>
#include <math.h>

// 判斷 n 是否為完全平方數，是則返回其平方根，否則返回 -1
int is_perfect_square(int n) {
    if (n < 0) return -1;
    int r = (int)(sqrt(n) + 0.5);  // 四捨五入應對浮點誤差
    return (r * r == n) ? r : -1;
}

int main() {
    int num;
    while (scanf("%d", &num) != EOF && num > 0 && num <= 10000) {
        int found = 0;
        // x 從 1 到 sqrt(num/3)
        for (int x = 1; 3 * x * x <= num; x++) {
            int x2 = x * x;
            // y 從 x 到 sqrt((num - x2)/2)
            for (int y = x; x2 + 2 * y * y <= num; y++) {
                int rem = num - x2 - y * y;
                int z = is_perfect_square(rem);
                if (z != -1 && z >= y) {
                    printf("%d %d %d\n", x, y, z);
                    found = 1;
                    break;
                }
            }
            if (found) break;
        }
        // 若題目要求無解時輸出特定信息，可在此添加
    }
    return 0;
}

複雜度對比

優化版快約 200 倍，且邏輯更清晰。

避免 `pow()` 的原因

pow() 返回 double，涉及浮點運算與轉換開銷大。
浮點誤差可能導致 pow(10,2) == 99.999999，整數比較失敗。
整數乘法 x*x 精確、快速、無副作用。

進一步優化：預計算平方表


int squares[101];  // 0^2 ~ 100^2
for (int i = 0; i <= 100; i++) squares[i] = i * i;

// 循環中直接查表
int rem = num - squares[x] - squares[y];
// 二分查找 rem 是否在 squares[y...100] 中

適用於極高性能要求或批量查詢場景。