4. 问题描述：在 n 枚外观相同的硬币中 , 有一枚是假币 , 并且已知假币较轻。可以通过一架没有刻度的天平来任意比较两组硬币 , 从而得知两组硬币的重量是否相同 , 或者哪一组更轻一些 , 但不知道轻多少 , 假币问题是要求设计一个高效的算法来检测出这枚假币。
【算法实现】设数组an]存储n枚硬币的重量，参数low和high表示假币所在的数组下标范围，设变量num1、num2和num3分别存储 3 组硬币的个数，程序如下：
int Coin(int a ], int low, int high, int n)
{
int i, num1, num2, num3;
int add1 = 0, add2 = 0;
if (n == 1)
return low + 1; //返回序号
if (n % 3 == 0) //3组硬币的个数相同
num1 = num2 = n / 3;
else //前两组硬币
num1 = num2 = n / 3 + 1;
num3 = n - num1 - num2;
for (i = 0; i < num1; i++) //计算第1组硬币的重量和
add1 = add1 + alow + i];
for (i = num1; i < num1 + num2; i++) //计算第2组硬币的重量和
add2 = add2 + alow + i];
if (add1 < add2) //在第1组查找
return Coin(a, low, low + num1 - 1, num1); else if (add1 > add2) //在第2组查找
return Coin(a, low + num1, low + num1 + num2 - 1, num2);
else //在第3组查找
return Coin(a, low + num1 + num2, high, num3);
}
