演算法偽幣問題 (分治法)

📢 本文由 gemini-3-flash-preview 翻譯

問題描述

有 $n$ 枚硬幣，其中有一枚是偽幣，已知偽幣的重量較輕。現只有一個天平，要求用儘量少的比較次數找出這枚偽幣

問題分析

將 $n$ 枚硬幣分成相等的兩部分：

當 $n$ 為偶數時，將前後兩部分，即 $1\cdots\frac{n}{2}$ 和 $\frac{n}{2}+1\cdots n$ 放在天平的兩端，較輕的一端裡有偽幣，繼續在較輕的這部分硬幣中用同樣的方法找出偽幣
當 $n$ 為奇數時，將前後兩部分，即 $1\cdots\frac{n-1}{2}$ 和 $\frac{n+1}{2}+1\cdots n$ 放在天平的兩端，較輕的一端裡有偽幣，繼續在較輕的這部分硬幣中用同樣的方法找出偽幣；若兩端重量相等，則中間的硬幣，即第 $\frac{n+1}{2}$ 枚硬幣是偽幣

C 程式碼

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h>

// coins:重量陣列   first,last:陣列第一個與最後一個下標
int getCounterfeitCoin(int *coins, int first, int last);

int main(void){
    int coins[10] = {2,2,1,2,2,2,2,2,2,2};
    int tmp = getCounterfeitCoin(coins, 0, 9);
    printf("第 %d 個是偽幣\n",tmp+1);
    return 0;
}

int getCounterfeitCoin(int *coins, int first, int last){
    int firstSum=0; int lastSum=0;
    int i;

    // 只剩兩枚硬幣
    if(first == last -1){
        if(coins[first] < coins[last])
            return first;
        return last;
    }

    // 偶數枚硬幣
    if ((last-first+1)%2 == 0){
        for(i=first; i<first+(last-first)/2+1; i++){
            firstSum += coins[i];
        }
        for(i=first+(last-first)/2+1; i<last+1; i++){
            lastSum += coins[i];
        }

        if(firstSum < lastSum){
            return getCounterfeitCoin(coins, first, first+(last-first)/2);
        }else{
            return getCounterfeitCoin(coins, first+(last-first)/2+1, last);
        }
    }else{  // 奇數枚硬幣
        for(i=first; i<first+(last-first)/2; i++){
            firstSum += coins[i];
        }
        for(i=first+(last-first)/2+1; i<last+1; i++){
            lastSum += coins[i];
        }

        if(firstSum < lastSum){
            return getCounterfeitCoin(coins, first, first+(last-first)/2-1);
        }else if(firstSum > lastSum){
            return getCounterfeitCoin(coins, first+(last-first)/2+1, last);
        }else{
            return first+(last-first)/2;
        }
    }
}