题目要求：

一个国王要赏赐给一个大臣30枚金币，但是其中有一枚是假币。国王提出要求：只能用一个天平作为测量工具，并用尽量少的比较次数找出这枚假币，那么余下的29枚金币就赏赐给这个大臣；否则这个大臣将得不到赏赐。已知假币要比真币的分量略轻一些。聪明的大臣思考片刻，很快用天平找出了这枚假币，于是得到了剩下的29枚金币。你知道这位大臣是如何找到假币的吗？请编写一个程序模拟找假币的过程，注意用尽量少的比较次数找出这枚假币。

#include "stdio.h"

int getFalseCoin(int coin[],int low,int high)
{
    int i,sum1 = 0,sum2 = 0,sum3 = 0;
    if(low+1==high)
    {
        if(coin[low] sum2) return getFalseCoin(coin,low+(high-low)/2+1,high);
    }

    if((high-low+1)%2 !=0)
    {
        for(i=low;i<=low+(high-low)/2-1;i++)
            sum1= sum1 + coin[i];       		/*前半段和*/
        for(i=low+(high-low)/2+1;i<=high;i++)
            sum2 = sum2 + coin[i];       		/*后半段和*/
            sum3 = coin[low+(high-low)/2];
            if(sum1< sum2)  
                return getFalseCoin(coin,low,low+(high-low)/2-1);
        if(sum1 > sum2)         
            return getFalseCoin(coin,low+(high-low)/2+1,high);
        if(sum1+sum3 == sum2+sum3) return low+(high-low)/2+1;
    }

}
main()
{
    int coin[30] = {2,2,2,2,2,2,2,2,2,2, 2,2,2,2,2,2,2,2,2,2, 2,2,2,2,2,
    2,2,1,2,2};
    printf("The %dth coin is false
",getFalseCoin(coin,0,29));
    getche();
}

运行结果：

运行结果