#include <iostream>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <string.h>
using namespace std;
//this program's file name is coin.cpp
//this program is designed by 200624101101杨振平 on NOV 22th,2008
//the algorithm of divide into two parts
int find2(int coin[], int low, int high);
//the algorithm of divide into three parts
int find3(int coin[], int low, int high);
//main function
void main()
{
//define variables
int i, *coin,n,temp;
cout <<"Please import the coin number (the n maximum is a machine round number numerical value)：";
cin>>n;
//srand()function generate a random seed which begin with the current time
srand( (unsigned)time( NULL ) );
cout <<"The random produces a data in course of (use 0 and 1 to represent counterfeit money and real currency respectively).../n/n";
//genenrate one more position use coin[0] to store the count of call weight this time
coin=new int[n+1];
//randomly generate a number between 1 and n
temp=1+rand()%n;
//counter
coin[0]=0;
//initial the coin array
for(i=1; i <n+1; ++i)
coin[i]=(i!=temp)?1:0;
//print the coin array
for(i=1; i <n+1; ++i)
if(i!=temp)
cout <<"The " <<setw(3) <<i <<"th coin is real currency(1)" <<endl;
else
cout <<"The " <<setw(3) <<i <<"th coin is counterfeit money(0)" <<endl;
//print the result of the algorithm of divide into two parts
cout <<endl <<endl <<"the result of counterfeit money with the algorithm of divide into two parts：" <<endl;
cout <<"counterfeit money is in the" <<setw(3) <<find2(coin,1,n) <<"th position!" <<endl;
cout <<"the total count of weight is" <<setw(3) <<coin[0] <<" times!" <<endl;
//print the result of the algorithm of divide into three parts
cout <<endl <<endl <<"the result of counterfeit money with the algorithm of divide into three parts：" <<endl;
cout <<"counterfeit money is in the" <<setw(3) <<find3(coin,1,n) <<"th position!" <<endl;
cout <<"the total count of weight is" <<setw(3) <<coin[0] <<" times!" <<endl <<endl <<endl;
}
//implement of find2 function
int find2(int coin[], int low, int high)
{
//define variables
int i,mid,sum1,sum2,sign;
coin[0]=0;
do //Location instructed by lower bound and upper bound
{
mid=(low+high)/2;
sign= (low+high)%2;//Mark odd number and even number
//cout <<sign <<endl;
sum1=sum2=0;
if(sign==0)//Handle the odd number condition
{
for(i=low; i <mid; i++)
sum1 += coin[i];
for(i=mid+1; i <=high; i++)
sum2 += coin[i];
if( sum1==0 && sum2==0 )
;
else
coin[0] += 1;
if(sum1==sum2)
return mid;
else if(sum1 <sum2)
{
high=mid-1;
}
else
{
low=mid+1;
}
}
else//Handle the even number condition
{
for(i=low; i <=mid; i++)
sum1 += coin[i];
for(i=mid+1; i <=high; i++)
sum2 += coin[i];
if( sum1==0 && sum2==0 )
;
else
coin[0] += 1;
if(sum1 <sum2)
high=mid;
else
low=mid+1;
}
}while(1);//end while
return -1;
}
//implement of find3 function
int find3(int coin[], int low, int high)
{
//define variables
int i,mid1,mid2,sum1,sum2,sum3,flag,my_space;
coin[0]=0;
if(high <3)
{cout <<"您必须键入的个数要大于3" <<endl <<endl <<endl; exit(1);}
while(low <=high) //Location instructed by lower bound and upper bound
{
sum1=sum2=sum3=0;
my_space=(high-low+1)/3;
mid1=low+my_space-1;
mid2=mid1+my_space;
//The remainder that mark is got rid of by 3,
//is that the remainder is 0 , 1 , 2 respectively
flag= (high-low+1) % 3;
for(i=low; i <=mid1; i++)
sum1 += coin[i];
for(i=mid1+1; i <=mid2; i++)
sum2 += coin[i];
for(i=mid2+1; i <=mid2+my_space; i++) //Pay attention to here
sum3 += coin[i];
if( sum1==0 && sum2==0 && sum3==0 )
;
else
coin[0] += 1;
if(flag==0)//Handle a remainder being 0's condition
{
if(sum1==sum2)
low=mid2+1;
if(sum1==sum3)
{ low=mid1+1; high=mid2; }
if(sum2==sum3)
high=mid1;
}
else if(flag==1)//Handle a remainder being 1's condition
{
if( sum1==sum2)
{
if(sum1==sum3)
{ return high;}
else
{low=mid2+1; high=high-1;}
}
else
{
if(sum1==sum3)
{ low=mid1+1; high=mid2;}
if(sum2==sum3)
{ high=mid1; }
}
}
else//Handle a remainder being 2's condition
{
if( sum1==sum2)
{
if(sum1==sum3)
{
coin[0] += 1;
if(coin[high-1]==0)
return high-1;
else
return high;
}
else
{low=mid2+1; high=high-2;}
}
else
{
if(sum1==sum3)
{ low=mid1+1; high=mid2;}
if(sum2==sum3)
{ high=mid1; }
}
}
}//end while
return -1;
}
