算法假币问题 (分治)

问题描述

有 $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;
        }
    }
}