减治法解决假币问题plus

以下代码是使用减治法查找假币，其中假币与真币的重量关系未知。

#include <iostream> #include <stdlib.h> using namespace std; int m=0; //真币质量 int Coin(int coin[], int n, int low, int high){ //在a[low]~a[high]中查找假币 int num1, num2, num3; //存储三组硬币的个数 int add1=0, add2=0, add3=0; //add1和add2存储前两组硬币的重量和 //cout << m << endl; if(n==1) return low+1; if(n==2){ //递归结束的条件 //cout << "执行了判定条件：符合条件，可以结束！" << endl; if(coin[low]!=m) return low+1; //返回的是序号，即下标加1 else return high+1; } if(n%3==0) //3组硬币的个数相同         num1=num2=n/3; else //前两组有n/3枚硬币         num1=num2=n/3+1;     num3=n-num1-num2; //第三组硬币 for(int i=0; i<num1; i++) //计算第一组硬币的重量和         add1 = add1+coin[low+i]; for(int i=num1; i<num1+num2; i++) //计算第二组硬币的重量和         add2 = add2+coin[low+i]; for(int i=num1+num2;i<n;i++)         add3 = add3+coin[low+i]; if(add1!=add2){ if(num3!=0) m = add3/num3; if(add1!=m*num1) return Coin(coin,num1, low, low+num1-1); //在第一组查找，下标范围是low ~ low+num1-1 else return Coin(coin,num2, low+num1, low+num1+num2-1); //在第二组查找，下标范围是low+num1 ~ low+num1+num2-1 } else{ //在第三组查找，下标范围是low+num1+num2 ~ high if(num1!=0) m = add1/num1; return Coin(coin,num3, low+num1+num2, high); } } int main() { int n;     cout << "请输入硬币个数：";     cin >> n ; int coin[n]; //假币的随机生成 for(int i=0; i<n; i++)         coin[i]=2; //所有硬币的重量为 1 int x = rand()%n; //生成0到n的随机数     coin[x] = 1; //第x枚硬币为假币 int a = Coin(coin, n,0,n-1);     cout << "第" << a << "枚硬币是假币。"<< endl;      cout << "所有硬币的质量依次为：" << endl; for(int i=0; i<n; i++)         cout << coin[i] << " "; return 0; }