#include <cstdlib>
#include <iostream>
using namespace std;
const int max1=1000;
void solve(int coin[], int n, int p, int q);
int main(int argc, char *argv[])
{
int coin[max1] = {0};
int n;
cout<<"输入硬币数量: ";
cin>>n;
if(n<=2)
cout<<"无法判断!"<<endl;
else
{
cout<<"输入硬币重量: ";
for(int i=0;i<n;i++)
cin>>coin[i];
solve(coin, n, 0, n - 1);
}
system("PAUSE");
return EXIT_SUCCESS;
}
void solve(int coin[], int n, int p, int q)
{
if (p == q)
{
cout<<"假币的序号为: "<<p+1<<"假币的重量为: "<<coin[p]<<endl;
}
else if (q - p == 1)
{
if (p > 0)
{
if (coin[p] == coin[0])
solve(coin, n, p + 1, q);
else
solve(coin, n, p, q - 1);
}
else if (q < n - 1)
{
if (coin[p] == coin[n - 1])
solve(coin, n, p + 1, q);
else
solve(coin, n, p, q - 1);
}
}
else if (p < q)
{
int temp = (q - p + 1) / 3;
int sum1 = 0, sum2 = 0;
for(int i = 0; i < temp; i++)
{
sum1 += coin[p + i];
sum2 += coin[q - i];
}
if (sum1 == sum2)//在中间
{
solve(coin, n, p + temp, q - temp);
}
else//在两边,不在中间
{
if (sum1 == coin[p + temp] * temp)//左边的和中间的相等,在右边
{
solve(coin, n, q - temp + 1, q);
}
else
{
solve(coin, n, p, p + temp - 1);
}
}
}
}