2014 年四川大學復試 C 語言真題：10 個球放入 4 個籃子的組合計數

編輯：關於C語言

題目背景

這是 2014 年四川大學計算機專業復試中的一道經典 C 語言編程題，考察遞歸回溯與組合數學建模能力。

問題描述

有 10 個相同的球，需放入 4 個編號的籃子中，滿足以下約束：

第 1 個籃子 至少 1 個球

第 2 個籃子 最多 5 個球

第 3 個籃子球數為偶數

第 4 個籃子 無限制

編程求出所有滿足條件的放置方案總數。

解題思路

1. 狀態定義

設 a[1]~a[4] 分別表示 4 個籃子的球數，a[1]+a[2]+a[3]+a[4]=10。

2. 遞歸搜索

對前 3 個籃子依次嘗試合法球數，第 4 個籃子由剩餘球數決定，最後檢查所有約束。

3. 剪枝優化

a[1] 從 1 開始枚舉
a[2] 上限為 5
a[3] 步長為 2（僅嘗試偶數）
若剩餘球數 < 0 直接回溯

完整 C 代碼實現

#include <stdio.h>

int a[5];      // 1-based 索引，a[1]~a[4]
int count = 0; // 方案計數器

void search(int idx) {
    if (idx == 4) { // 前三個籃子已定，第 4 個由剩餘決定
        a[4] = 10 - a[1] - a[2] - a[3];
        if (a[4] >= 0) { // 第 4 個籃子無下限，只需非負
            count++;
            // 可選：輸出具體方案
            // printf("%d %d %d %d\n", a[1], a[2], a[3], a[4]);
        }
        return;
    }

    int start, end, step;
    switch (idx) {
        case 1: start = 1; end = 10; step = 1; break;       // 至少 1 個
        case 2: start = 0; end = 5;  step = 1; break;       // 最多 5 個
        case 3: start = 0; end = 10; step = 2; break;       // 偶數
        default: return;
    }

    for (int v = start; v <= end; v += step) {
        a[idx] = v;
        // 剪枝：已放入球數不超過 10
        if (a[1] + a[2] + a[3] <= 10) {
            search(idx + 1);
        }
    }
}

int main() {
    search(1);
    printf("滿足條件的方案總數：%d\n", count);
    return 0;
}