问题描述：
在n枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币。
解题思路：
使用减治法的解题思路，将硬币分为3堆，则每堆的硬币数量为 n/3 ，但是这是在 n%3==0 的情况下才能成立，所以我们将 n 枚硬币分为 3 堆加 1 堆 余数堆(余数堆可能为0)，则可分为如下(n-n%3)/3, (n-n%3)/3, (n-n%3)/3, n%3.
如下图：
(n-n%3)/3
(n-n%3)/3
(n-n%3)/3
n%3
a
b
c
d
- 首先获取真币，通过从数组中随机取三枚硬币，互相比较，相等的两枚为真币，任意取一枚作为真币 记录 数组下标。
- 判断n中的硬币数量，如果n>2则执行3，否则执行5.
- 将n分为上图的四堆，拿 a 和 b 比较，如果 a == b ,则 假币在 c 或 d 中。否则假币在 a 或 b 中。
- 如果 a == b，则拿 a 和 c 比较。如果 a == c,则假币在d中。将 d 再次 执行本流程。如果不等，则假币在 c 中，将 d (余数堆) 再次 执行流程,并且n=n%3,。
- 如果 a != b，则拿 a 和 c 比较。如果 a == c,则假币在b中。将 b 再次 执行本流程。如果不等，则假币在 a 中，将 a 再次 执行流程 2，并且n=(n-n%3)/3。
- 如果n==2，则将两枚硬币与真的硬币（通过 数组下标 ）进行比较，不同的为假币，输出结果，结束。
- 如果n==1，则该硬币就是假币，输出结果结束。
*注：按照2-5流程分堆下去，在最后一执行流程 2 时，n中含有假币，并且n只可能为1或2.(初始时，n>3，若n<3，则不能判断真假)
主要代码如下：
//计算硬币总重量
int sum_coin(int coin[],int m,int n){
int result=;
if(m>n)
return ;
for(int i=m;i<=n;i++){
result+=coin[i];
} return result;
}; //找出假币 m , n 数组下标,coin 硬币数组，relCoin 真币数组下标
int check_coin(int coin[],int m,int n,int& relCoin){ int vary=n-m+; int restCoin=vary%;
int vary2=vary-restCoin; if(vary==)
return m; if(vary==)
{
if(sum_coin(coin,m,m)==sum_coin(coin,relCoin,relCoin))
return n;
else
return m; } if(sum_coin(coin,m,m+vary2/-)==sum_coin(coin,m+vary2/,m+(vary2/)*-))//第一堆 == 第二堆
{
if( (sum_coin(coin,m,m+vary2/-)==sum_coin(coin,m+(vary2/)*,m+vary2-)))//第一堆 == 第三堆
check_coin(coin,n-restCoin+,n,relCoin);
else//第一堆 ！= 第三堆
check_coin(coin,m+(vary2/)*,m+vary2-,relCoin);
}
else//第一堆 ！= 第二堆
{
if(sum_coin(coin,m,m+vary2/-)==sum_coin(coin,m+(vary2/)*,m+vary2-))//第一堆 == 第三堆
check_coin(coin,m+vary2/,m+(vary2/)*-,relCoin);
else//第一堆 ！= 第三堆
check_coin(coin,m,m+vary2/-,relCoin);
} }; //返回真币数组下标
int getRelCoin(int coin[],int m,int n)
{
if(n-m+<=)
{
cout<<"硬币数小于3枚！！！无解";
return -;
}
else
{
if(coin[]==coin[])
{
return ;
}
else
{
if(coin[]==coin[])
return ;
else
{
return ;
}
}
} };
原创,转载请注明来源，默@语：www.h-five.com