C 語言入門經典：百錢買百雞問題的三重/二重迴圈求解與優化

百錢買百雞：從暴力枚舉到數學優化的演進

「百錢買百雞」出自《孫子算經》，是迪奧芬圖斯方程 (不定方程) 的經典入門案例。公雞 5 文、母雞 3 文、小雞 3 隻 1 文，求購買組合使總數 100 隻、總價 100 文。

數學模型

設公雞 x 隻，母雞 y 隻，小雞 z 隻
方程組：
  x + y + z = 100          (數量約束)
  5x + 3y + z/3 = 100      (價格約束，z 必為 3 的倍數)

消元得：7x + 4y = 100
整數解範圍：x ∈ [0, 14], y ∈ [0, 25], z = 100 - x - y

版本一：三重迴圈暴力枚舉 (教學示範)

#include 

void main(void) {
    int a, b, c;  // a=公雞, b=母雞, c=小雞
    
    for (a = 1; a < 21; a++)          // 公雞最多 20 隻 (5*20=100)
        for (b = 1; b < 34; b++)      // 母雞最多 33 隻 (3*33=99)
            for (c = 1; c < 100; c += 3) {  // 小雞步進 3
                if ((5*a + 3*b + c/3 == 100) && (a + b + c == 100))
                    printf("\n 100元錢能買到%d只公雞 %d 只母雞 %d只小雞!\n\n", a, b, c);
            }
    getchar();
}

複雜度：~ 20 × 33 × 33 ≈ 21,780 次迭代。適合理解迴圈嵌套與條件判斷，但效率低。

版本二：二重迴圈 + 代數消元 (優化)

#include 

void main(void) {
    int a, b;  // a=公雞, b=母雞
    
    for (a = 1; a < 21; a++)
        for (b = 1; b < 34; b++) {
            int c = 100 - a - b;           // 由數量約束直接得出小雞數
            if ((5*a + 3*b + c/3 == 100) && (c % 3 == 0))  // 價格驗證 + 整除檢查
                printf("\n 100元錢能買到%d只公雞 %d 只母雞 %d只小雞!\n\n", a, b, c);
        }
    getchar();
}

複雜度：~ 20 × 33 = 660 次迭代，**提速 33 倍**。核心優化：利用 `x + y + z = 100` 消除第三層迴圈，並檢查 `z % 3 == 0` 保證價格方程整數解。

版本三：單重迴圈 + 直接求解 (最優)

#include 

void main(void) {
    int x;  // 公雞數
    
    for (x = 0; x <= 14; x++) {      // 7x + 4y = 100 → x ≤ 14
        int remainder = 100 - 7*x;
        if (remainder % 4 == 0) {    // y 必為整數
            int y = remainder / 4;   // 母雞數
            int z = 100 - x - y;     // 小雞數
            if (z % 3 == 0)          // 驗證小雞為 3 的倍數
                printf("公雞:%d 母雞:%d 小雞:%d\n", x, y, z);
        }
    }
}

複雜度：15 次迭代，**再提速 44 倍**。直接求解不定方程 `7x + 4y = 100`，僅遍歷自變數 `x`。

四組整數解

教學價值總結

1. 迴圈嵌套與邊界控制：三重迴圈版本練習基礎語法
2. 代數消元思想：利用約束條件減少搜尋空間
3. 整數除法與模運算：`z % 3 == 0` 確保小雞價格為整數
4. 不定方程求解：線性不定方程 `ax + by = c` 的整數解結構
5. 程式優化意識：從 O(n³) → O(n²) → O(n) 的思維演進

這個古老問題完美展示了「數學建模 → 暴力求解 → 代數優化 → 直接求解」的程式設計思維升級路徑，是演算法設計入門的極佳教材。