2017年软件设计师上半场下午题目

【说明】
假币问题：有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枚硬币是假币。
【C代码】
下面是算法的C语言实现，其中:
coins[]：硬币数组
first,last：当前考虑的硬币数组中的第一个和最后一个下标。

答案：

#include<stdio.h>

int getCounterfeitCoin(int coins[], int first, int last)
{
    int firstSum = 0, 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) // 第一空可以直接看题目题目中直接把偶数的时候区间为1...n/2给出来了，也可以看下面的那个循环的i为first+(last - first)/2+1
        {
            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 coins[first + (last - first) / 2]; // 第三空位置，当硬币数量为奇数的时候有三种情况，比偶数多的一个情况为，就是这个奇数区间的中位数
    }
}

算法采用了（分治）设计策略。 // 分治分而治之，这个题的具体算法名称叫做二分，二分就是分治的经典运用。

时间复杂度为：O(logn)。// 倒也不需要怎么详细的计算，首先根据是分支算法，所以时间复杂度里面一定有logn,分支的特点就是把O(n)的降为O(logn)，这个题如果采取暴力的话就是O(n)。

若输入的硬币数为30，则最少的比较次数为（2），最多的比价次数为（4）。
最少的情况为：因为30位偶数，所以至少要被分一次，然后成为奇数之后，那个假币就是奇数的中位数，所以只需要2次。
最多的情况为：floor(log2(30)) = 4