学步园

#include<stdio.h>
 int findCoin(int coin[],int front,int back)
{ 
    int i,sumf=0,sumb=0,sum=0;     
if(front+1==back)    
 {
         if(coin[front]<coin[back])   
 return front+1;      
   else return back+1;        
              }      
  if((back-front+1)%2==0)     
{     
    for(i=front;i<=front+(back-front)/2;i++)       
      sumf=sumf+coin[i];     
    for(i=front+(back-front)/2+1;i<=back;i++)     
        sumb=sumb+coin[i];      
   if(sumf<sumb)         
    return findCoin(coin,front,front+(back-front)/2);     
    if(sumf>sumb)      
       return findCoin(coin,front+(back-front)/2+1,back);        
                    }      
    if((back-front+1)%2!=0)     
{
         for(i=front;i<=front+(back-front)/2-1;i++)    
         sumf=sumf+coin[i];   
      for(i=front+(back-front)/2+1;i<=back;i++)        
     sumb=sumb+coin[i];        
     sum=coin[front+(back-front)/2];      
   if(sumf<sumb)            
 return findCoin(coin,front,front+(back-front)/2-1);        
 if(sumf>sumb)          
   return findCoin(coin,front+(back-front)/2+1,back);       
   if(sumf+sum==sumb+sum)     
        return front+(back-front)/2+1;         
                   }}
    int main()
{  
  int coin[30]={1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};    
printf("那个假币是第%d个金币！\n",findCoin(coin,0,29));    
system("PAUSE");    
return 0;}

1.如果金币有偶数个，把金币的前半部分与后部分的重量进行比较，假金币在较小的那部分。
2.如果金币有奇数个，以正中间的那个金币作为轴，将金币分为前后两个部分，如果这两部分相当，说明这个为轴的金币就是假金币，如果不相当，假金币就在质量较小的那部分。
3.循环上述过程直到找到假金币。