经典问题之找假币

二分法是我们经常使用的方法，它的优点就在于直观，清晰

以下是二分法的代码实现：

#include <stdio.h>
#define LENGTH 16 //表示假币的数量，可以在范围内任意修改
#define FALSE -1
void search(int data[],int start,int end);

void search(int data[],int start,int end)
{
  int i,sum1=0,sum2=0;  //sum1,sum2用于表示两组硬币的重量
  if((end-start)==2)  //硬币数为2，则可以直接进行判断
  {
    if(data[start]<data[start+1])
      printf("nn假币是第%d个.",start);  
    else
      printf("nn假币是第%d个",start+1);
  }
  //硬币数量不为2，将硬币分为两组，计算量组的硬币重量，
  //若相等，则假币在最后一个（此时硬币数为奇数），
  //否则（硬币数为偶数），判断找出两组硬币中的质量较小的一组，假币必在其中，继续调用函数
  else
  {
    for(i=start;i<(end+start)/2;i++)
    {
      sum1+=data[i];
      sum2+=data[(end-start)/2+i];
    }
    if(sum1==sum2)
      printf("nn假币是第%d个.",end-1);
    else
    {
      if(sum1<sum2)
      {
        end=(end+start)/2;
        search(data,start,end);
      }
      else
      {
        start=(start+end)/2;
        search(data,start,end);
      }
    }
  }
}
int main(void)
{
  int place;
  int coin[LENGTH]={0};
  printf("输入你想让假币存在的位置:");
  scanf("%d",&place);
  coin[place%LENGTH]=FALSE; //防止越界
  search(coin,0,LENGTH);
  return 0;
}

三分法是在二分法的基础上拓展出来的，因为二分法虽然直观，清晰，但同时，它没有最大限度地进行对时间的优化，故此三分法进行优化
以下是三分法的代码实现：

#include <stdio.h>
#define N 50
void search(int data[],int count,int start);//将硬币分三组进行比较
void search(int data[],int count,int start)//count表示判断的硬币个数，start表示这组硬币的起始位置
{
  int a,b,i;
  double sum1=0,sum2=0;
  a=count/3;
  b=count%3;
  if(count==1)//硬币个数为1，直接判断
  {
    printf("n假币是第%d个.",start);return;
  }
  if(count==2)//硬币个数为2，判断一次
  {
    if(data[start]>data[start+1])
    {
      printf("n假币是第%d个.",start+1);return;
    }
    else
    {
      printf("n假币是第%d个.",start);return;
    }
  }
  if(count==3)//硬币个数为3，判断一次
  {
    if(data[start]==data[start+1])
    {
      printf("n假币是第%d个.",start+2);return;
    }
    else if(data[start]<data[start+1])
    {
      printf("n假币是第%d个.",start);return;
    }
    else
    {
      printf("n假币是第%d个.",start+1);return;
    }
  }
  if(b==0)//余数为 0，任取两组硬币进行比较(此处选取第一，二组进行比较)
  {
    for(i=0;i<a;i++)
    {
      sum1+=data[start+i];
      sum2+=data[start+i+a];
    }
    if(sum1==sum2)//sum1与sum2相等，故假币在第三组，调用search()继续进行判断
    {
      search(data,a,start+2*a);return;
    }
    else if(sum1<sum2)//sum1<sum2，故假币在第一组，调用search()继续进行判断  
    {
      search(data,a,start);return;
    }
    else  //sum1>sum2，假币在第二组，调用search()继续进行判断  
    {
      search(data,a,start+a);return;
    }
  }
  if(b==1)  //b表示硬币个数除以 3的余数，若 b为 1，则将余数 1加到第一组，保证第二组和第三组的硬币个数相同
  {
    for(i=a+1;i<2*a+1;i++)
    {
      sum1+=data[start+i];
      sum2+=data[start+i+a];
    }
    if(sum1==sum2)
    {
      search(data,a+1,start);return;
    }
    else if(sum1<sum2)
    {
      search(data,a,start+a+1);return;
    }
    else
    {
      search(data,a,start+2*a+1);return;
    }
  }
  if(b==2)//b表示硬币个数除以 3的余数,若 b为 2,则将余数 2分成1+1,分别加到第一,二组,保证第一组和第二组的硬币个数相同
  {
    for(i=0;i<=a;i++)
    {
      sum1+=data[start+i];
      sum2+=data[start+i+a+1];
    }
    if(sum1==sum2)
    {
      search(data,a,start+2*a+2);return;
    }
    else if(sum1<sum2)
    {
      search(data,a+1,start);return;
    }
    else
    {
      search(data,a+1,start+a+1);return;
    }
  }
}
int main(void)
{
  int place;
  int coin[N]={0};
  printf("请输入你想让假币所在的位置:");
  scanf("%d",&place);
  coin[place%N]=-1;//假币为-1
  search(coin,N,0);//调用search函数
  return 0;
}

三分法主要在于将数组表示的假币分成三份，减少了时间复杂度，但其的判断条件也就将复杂，我们直到当硬币数量为1时，必定是假币，当硬币数量为2时，只需比较一次，当硬币数量为3时，也只需比较一次，便可得到结果：故整体思路就是将硬币3分，调用3分函数，直至可以得到结果

以上便是此次分享的全部内容！Fighting！