C語言找零錢問題：1元換1/2/5分硬幣組合枚舉

經典枚舉問題：硬幣組合

題目：1元(100分)換1分、2分、5分硬幣，每種至少1枚，求所有組合。

數學建模

設 x1、x2、x5 分別為1分、2分、5分硬幣數量：

x1 + 2*x2 + 5*x5 = 100
x1 ≥ 1, x2 ≥ 1, x5 ≥ 1, 整數解

優化枚舉範圍

• x5 最大：(100 - 1 - 2) / 5 = 19 → 範圍 1~19
• x2 最大：(100 - 1 - 5) / 2 = 47 → 範圍 1~47
• x1 由方程直接計算：x1 = 100 - 2*x2 - 5*x5

修正後代碼

#include 

int main() {
    int x1, x2, x5, count = 0;
    
    for (x5 = 1; x5 <= 19; x5++) {
        for (x2 = 1; x2 <= 47; x2++) {
            x1 = 100 - 2*x2 - 5*x5;  // 關鍵修正：係數不可漏
            if (x1 >= 1) {
                printf("x1=%3d, x2=%3d, x5=%3d\n", x1, x2, x5);
                count++;
            }
        }
    }
    printf("總共有 %d 種換法\n", count);
    return 0;
}

原代碼錯誤分析

// 錯誤版
x1 = 100 - x5 - x2;           // 漏掉硬幣面值係數！
if (x1*1 + x2*2 + x5*5 == 100)  // 條件雖正確但x1計算錯導致永假

// 正確版
x1 = 100 - 5*x5 - 2*x2;       // 直接由方程求解，無需再驗證
if (x1 >= 1)                  // 僅需檢查x1≥1

運行結果統計

x1= 93, x2=  1, x5=  1
x1= 91, x2=  2, x5=  1
...
x1=  1, x2=  2, x5= 19
總共有 87 種換法

複雜度分析

雙重循環：19 × 47 ≈ 893 次迭代，O(1) 空間，瞬間完成。若擴展到 N 種硬幣，可用動態規劃 (背包問題) 或生成函數求解。