题解：找出假币

Guderian出品

说明

假币问题： 有$ n $枚硬币， 其中有一枚是假币， 己知假币的重量较轻。 现只有一个天平， 要求用尽量少的比较次数找出这枚假币。

分析

算法设计策略：分治法

将 n 枚硬币分成相等的两部分:

(1)当$ n $为偶数时， 将前后两部分， 即$ 1…n/2 $和$ n/2+1…n$， 放在天平的两端， 较轻的一端里有假币， 继续在较轻的这部分硬币中用同样的方法找出假币:

(2)当$ n $为奇数时， 将前后两部分， 即$1..(n -1)/2$和$(n+1)/2+1…n$， 放在天平的两端， 较轻的一端里有假币， 继续在较轻的这部分硬币中用同样的方法找出假币； 若两端重量相等， 则中间的硬币， 即第$ (n+1)/2 $枚硬币是假币。

实现

（1）常量和变量说明

coins[]：硬币数组

first，last：当前考虑的硬币数组中的第一个和最后一个下标

（2）C语言程序

#include<stdio.h> 

int getCounterfeitCoin(int coins[],int first,int last)
{
    int firstSum = 0,lastSum = 0;
    int ì;
    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;
        }
    }
}

例：若输入的硬币数为30， 则最少的比较次数为2 ， 最多的比较次数为4。

（3）复杂度分析

• 时间复杂度：$O(n\log n)$
  • 二分法本身耗时$O(\log n)$，每次顺序求和操作耗时$O(n)$，总计时间复杂度$O(n\log n)$
• 空间复杂度：$O( n )$