百錢百雞問題 C 語言完整解法與優化分析

數學建模

設公雞 x、母雞 y、雛雞 z：

x + y + z = 100
5x + 3y + z/3 = 100   (雛雞 1 元 3 隻 → 單價 1/3)

整數解約束：z % 3 == 0，x,y,z >= 0。

暴力枚舉優化版

#include <stdio.h>
int main() {
    for (int x = 0; x <= 20; x++) {          // 公雞最多 20 隻 (5*20=100)
        for (int y = 0; y <= 33; y++) {      // 母雞最多 33 隻 (3*33=99)
            int z = 100 - x - y;
            if (z >= 0 && z % 3 == 0 && 5*x + 3*y + z/3 == 100) {
                printf("公雞:%d 母雞:%d 雛雞:%d\n", x, y, z);
            }
        }
    }
    return 0;
}

輸出結果 (4 組解)

公雞:0  母雞:25  雛雞:75
公雞:4  母雞:18  雛雞:78
公雞:8  母雞:11  雛雞:81
公雞:12 母雞:4   雛雞:84

進一步優化：消元法

由方程組消去 z 得 7x + 4y = 100，枚舉 x 直接解 y，時間複雜度從 O(n²) 降為 O(n)。

for (int x = 0; x <= 14; x++) {
    int rem = 100 - 7*x;
    if (rem % 4 == 0) {
        int y = rem / 4;
        int z = 100 - x - y;
        printf("%d %d %d\n", x, y, z);
    }
}