找硬币（分治）

例题1：找伪币

给出N个一模一样的硬币，从1开始编号，其中有一个是伪造的，且那个伪造的币比真币要轻，请问如何找出伪造的币，并输出序号？ 测试数据： 输入： 16 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 输出： 7

输入： 17 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 输出： 17

输入： 18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 输出： 17

方法一、穷举法：

两两比较，找出最轻的，最多比较n/2次能判断出来

//二分法，三分法—分治—递推(开始往后) //递归有出口，f(1)=1,f(2)=1,f(n)=f(n-1)+f(n-2) //穷举法 #include<cstdio> #include<iostream> using namespace std; int a[1000]; int main(void) { freopen("CON","r",stdin); freopen("CON","w",stdout); int n; cin>>n; //获取下标 for(int i=1;i<=n;i++){ cin>>a[i]; } //每两个比较 for(int i;i<=n;i+=2){ if(a[i]<a[i+1]){ cout<<i; return 0; }else if(a[i]>a[i+1]){ cout<<i+1; return 0; } } cout<<n;//如果前面都没有找到，奇数的情况，只有最后一个 return 0; }

方法二、二分法：

把N个硬币看成一个大问题，第一步把大问题分解成两个小问题，随机选择一半作为一组，剩下一半作为第二组，判断伪币在哪一组中。再次进行一分为二的方式来判断，直到找到为止，此问题可以使用二分法来进行处理。

#include<cstdio> #include<iostream> using namespace std; int findCoin(int coin[],int l,int r){ int sum1,sum2,mid=(l+r)/2; sum1=sum2=0; //回归点 ，只有两个硬币的情况 if(l+1==r){ return coin[l]<coin[r]?l:r; } //不止两个硬币，我们就要分治求解直到只剩两个硬币为止 if((r-l+1)%2==0){ //n是偶数的情况 for(int i=l;i<=mid;i++){ sum1+=coin[i]; } for(int i=mid+1;i<=r;i++){ sum2+=coin[i]; } if(sum1<sum2) return findCoin(coin,l,mid); else if(sum2<sum1) return findCoin(coin,mid+1,r); }else{ //n是奇数的情况 for(int i=l;i<=mid-1;i++){ sum1+=coin[i]; } for(int i=mid+1;i<=r;i++){ sum2+=coin[i]; } if(sum1<sum2) return findCoin(coin,l,mid-1); else if(sum2<sum1) return findCoin(coin,mid+1,r); else return mid; } return 0; } int a[1000]; int main(void){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } cout<<findCoin(a,1,n); return 0; }

谢谢