純 C 語言分治法解決假幣問題：O(log N) 邏輯與源碼

經典假幣問題：N 枚硬幣中有一枚較輕，天平無砝碼，僅能比較兩堆重量。分治策略：每次將硬幣分為兩堆（奇數時留一旁），稱重較輕那堆遞歸，直至剩 1 枚。時間複雜度 O(log₃ N)（三分查找）。本文給出 C 語言遞歸實現。

分治邏輯

1. 若區間長度為 2：直接比較，較輕者為假幣。
2. 若長度為偶數：平分兩堆，稱重，遞歸較輕堆。
3. 若長度為奇數：留出中間 1 枚，其餘平分兩堆稱重。
   • 若等重 → 中間那枚是假幣。
   • 否則遞歸較輕堆。

源碼（C++ 風格輸出，易改為 C）

#include 

// coin[] 存儲每枚硬幣重量，真幣權值相同，假幣較小
int find_false_coin(int coin[], int low, int high) {
    int i, sum1 = 0, sum2 = 0, sum3 = 0;
    if (low == high - 1) { // 兩枚
        return (coin[low] < coin[high]) ? low : high;
    }
    int mid = low + (high - low) / 2;
    if ((high - low + 1) % 2 == 0) { // 偶數枚
        for (i = low; i <= mid; i++) sum1 += coin[i];
        for (i = mid + 1; i <= high; i++) sum2 += coin[i];
        return (sum1 < sum2) ? find_false_coin(coin, low, mid)
                             : find_false_coin(coin, mid+1, high);
    } else { // 奇數枚
        for (i = low; i < mid; i++) sum1 += coin[i];
        for (i = mid + 1; i <= high; i++) sum2 += coin[i];
        sum3 = coin[mid];
        if (sum1 == sum2) return mid;
        return (sum1 < sum2) ? find_false_coin(coin, low, mid-1)
                             : find_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 枚（下標 12）為假幣，重 1
    int idx = find_false_coin(coin, 0, 29);
    printf("第 %d 枚硬幣是假幣\n", idx + 1); // 輸出 13
    return 0;
}

關鍵實現細節

• 數組 coin[] 模擬硬幣重量，真幣統一權值，假幣較小。
• 遞歸參數 low, high 為區間下標（含端點）。
• 奇數情況下 mid 為正中索引，左堆 [low, mid-1]，右堆 [mid+1, high]，中間 mid 留出。
• 比較 sum1 與 sum2 決定遞歸方向。

複雜度分析

• 每次遞歸問題規模約減為 1/3（三分查找）。
• 時間複雜度 O(log₃ N)，遠優於線性掃描 O(N)。
• 空間複雜度 O(log₃ N)（遞歸棧）。

擴展：未知假幣輕重

若不知假幣是輕是重，需額外記錄「上次稱重結果」傳遞給遞歸，或引入「可疑輕/重」標記，邏輯較複雜但同樣可分治解決。

總結

假幣問題是分治算法的教科書級應用：將問題等分為可比較的子問題，通過一次比較排除 2/3 候選。代碼簡潔高效，體現「減而治之」的算法哲理。