C語言分治算法實現：假幣問題（天平稱重找輕幣）

問題描述

有 n 枚硬幣，外觀相同，其中一枚較輕（假幣）。有一天平可比較兩堆重量。設計算法找出假幣，稱重次數最少。

分治策略

• 將硬幣分為兩堆（或三堆），比較重量。
• 較輕那堆必含假幣，遞歸處理該堆。
• 若兩堆等重，假幣在剩餘未稱堆中（奇數時）。

完整代碼

#include <stdio.h>

int get_false_coin(int coin[], int low, int high) {
    if (low == high) return low;                    // 只剩一枚
    if (low + 1 == high) {                          // 剩兩枚，直接比較
        return (coin[low] < coin[high]) ? low : high;
    }

    int mid = low + (high - low) / 2;
    int sum1 = 0, sum2 = 0, sum3 = 0;
    int count = high - low + 1;

    if (count % 2 == 0) {                           // 偶數枚：分兩堆
        for (int i=low; i<=mid; i++) sum1 += coin[i];
        for (int i=mid+1; i<=high; i++) sum2 += coin[i];
        if (sum1 < sum2) return get_false_coin(coin, low, mid);
        else return get_false_coin(coin, mid+1, high);
    } else {                                        // 奇數枚：分三堆，中間單獨一枚
        for (int i=low; i<mid; i++) sum1 += coin[i];
        for (int i=mid+1; i<=high; i++) sum2 += coin[i];
        sum3 = coin[mid];
        if (sum1 == sum2) return mid;               // 兩堆等重，中間是假幣
        else if (sum1 < sum2) return get_false_coin(coin, low, mid-1);
        else return get_false_coin(coin, mid+1, high);
    }
}

int main() {
    int coin[30];
    for (int i=0; i<30; i++) coin[i] = 2;  // 真幣重 2
    coin[12] = 1;                             // 第 13 枚為假幣（輕 1）
    int idx = get_false_coin(coin, 0, 29);
    printf("假幣位置 (0-based): %d, 第 %d 枚\n", idx, idx+1);
    return 0;
}

關鍵點

• 假設天平給出精確重量和（模擬 sum1, sum2），實際天平只能比較輕重，但邏輯相同。
• 每次稱重將問題規模約減半，稱重次數 = ⌈log₂ n⌉（三分法可達 ⌈log₃ n⌉）。
• 基礎情況：1 枚直接回傳，2 枚比較。
• 奇數處理：單獨拿出中間一枚，若兩邊等重則中間為假幣。

複雜度

• 時間：O(n) —— 每層遞歸需掃描該區間求和，總掃描量 n + n/2 + n/4 + ... = 2n。
• 空間：O(log n) 遞歸深度。
• 若天平只能比較而不能求和，需改為分組計數，但分治邏輯不變。

擴展：三分法優化

將硬幣分為三堆盡量等量，稱重前兩堆：

• 左輕 → 假幣在左堆
• 右輕 → 假幣在右堆
• 等重 → 假幣在第三堆

稱重次數下限為 ⌈log₃ n⌉，對 30 枚硬幣僅需 4 次（二分需 5 次）。

假幣問題展示了分治策略在決策樹模型中的應用，是資訊論下界與算法設計結合的經典教學案例。