C語言入門經典：百錢買百雞問題的三重循環與優化解法

「百錢買百雞」是中國古典數學問題，也是C語言初學者練習循環嵌套、條件判斷、整數運算的經典案例。本文展示從暴力三重循環到數學優化二重循環的演進過程。

問題描述

• 公雞5元/只，母雞3元/只，小雞1元/3只（即1/3元/只）
• 100元買100只雞，問公雞、母雞、小雞各幾只？
• 方程組：

  
    x + y + z = 100          // 總數
    5x + 3y + z/3 = 100      // 總價
    x,y,z ≥ 0 且為整數, z % 3 == 0
    

解法一：暴力三重循環（直觀但低效）

#include 

void main(void) {
    int x, y, z; // 公、母、小
    for (x = 1; x < 21; x++) {       // 公雞最多100/5=20
        for (y = 1; y < 34; y++) {   // 母雞最多100/3≈33
            for (z = 1; z < 100; z += 3) { // 小雞步長3（整數價）
                if (5*x + 3*y + z/3 == 100 && x + y + z == 100) {
                    printf("公雞%d只 母雞%d只 小雞%d只\n", x, y, z);
                }
            }
        }
    }
    getchar();
}

• 循環次數：20 × 33 × 33 ≈ 21,780 次
• z += 3利用「小雞數必為3的倍數」剪枝
• 適合理解問題建模，不適合大規模問題

解法二：數學優化二重循環（消去一變量）

由x + y + z = 100得z = 100 - x - y，代入價格方程：

5x + 3y + (100 - x - y)/3 = 100
→ 15x + 9y + 100 - x - y = 300
→ 14x + 8y = 200
→ 7x + 4y = 100

只需雙重循環驗證7x + 4y == 100且z = 100-x-y為3的倍數：

#include 

void main(void) {
    int x, y;
    for (x = 1; x < 21; x++) {
        for (y = 1; y < 34; y++) {
            if (7*x + 4*y == 100 && (100 - x - y) % 3 == 0) {
                int z = 100 - x - y;
                printf("公雞%d只 母雞%d只 小雞%d只\n", x, y, z);
            }
        }
    }
    getchar();
}

• 循環次數：20 × 33 = 660 次，提速33倍
• 無內層循環，邏輯更清晰
• 體現「用數學優化算法」的核心思想

解法三：進一步優化單循環（線性掃描）

由7x + 4y = 100，對x求解y = (100 - 7x)/4：

#include 

int main() {
    for (int x = 1; x <= 20; x++) {
        int remainder = 100 - 7*x;
        if (remainder % 4 == 0) {
            int y = remainder / 4;
            int z = 100 - x - y;
            if (z >= 0 && z % 3 == 0) {
                printf("公雞%d只 母雞%d只 小雞%d只\n", x, y, z);
            }
        }
    }
    return 0;
}

• 僅遍歷x（1~20），20次循環，O(1)級效率
• 體現「代數消元」將多變量問題降維

所有整數解

共3組解（若允許0則有4組，含0公雞25母雞75小雞）。

複雜度對比

通用數學解法：線性不定方程

7x + 4y = 100，gcd(7,4)=1整除100，有整數解。

特解：x=4, y=18（觀察得）。通解：

x = 4 + 4k
y = 18 - 7k
z = 100 - x - y = 78 + 3k
k 為整數

非負約束：x≥0, y≥0, z≥0 → k=0,1,2得上述3組解。

教學總結

1. 建模：將文字問題轉化為方程組
2. 暴力基準：先寫最直觀的枚舉代碼，跑通邏輯
3. 觀察約束：變量範圍、整數性、步長優化（如z+=3）
4. 代數消元：用方程減少循環維度
5. 數學閉式解：線性不定方程通解公式，O(1)求解
6. 邊界處理：非負、整數、上下界檢查

這道題完美展示了「程序=數據結構+算法」中算法優化的層層遞進：從暴力枚舉到數學建模，每一步都在減少計算量、提升代碼優雅度。這正是計算機科學核心思維的縮影。

1. 上一篇文章： 設計模式深度解析：工廠方法模式的結構、實現與模板優化
2. 下一篇文章： 圖解棧幀機制：EIP、EBP、ESP 在函數調用中的協作原理

關於C

OpenERP (Odoo) 彈出提示窗口完整指南：osv.except_osv 國際化與變量嵌入

OpenERP/Odoo 開發中，osv.except_os

C語言基礎練習：輸入正整數 n，計算 1 + n + n² + n³ 的值

題目需求 從鍵盤讀入一個正整數 n，計算並輸出多項式 1 +

C語言互動程式：持續輸入實數累加直到總和超過 1000

程式反覆提示使用者輸入實數，邊輸入邊累加，當總和超過 100

C語言結構體內存對齊詳解：Windows vs Linux、大小計算與優化佈局

sizeof 是編譯期運算符，但結構體大小受**內存對齊**