1. 实验内容

1）减治法应用实现
在n枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的减治算法来检测出这枚假币。
int nCoin(int coin[], int n, int p, int q)；
coin[]数组存储各枚硬币的重量。

2.算法分析

在假币问题中，每次用天平比较后，只需解决一个规模减半的问题，所以，它属于一个减治算法。解决这个问题的最自然的想法就是一分为二，也就是把n枚硬币分成两组A、B，每组有[n/2]枚硬币，如果n为奇数，就留下一枚硬币C，然后把两组硬币分别放到天平的两端。如果两组硬币的重量相同，那么留下来的硬币C就是假币；否则，假币就出现在和[n/2]*C重量不相等的一组里，重复上述过程直至找到假币。

2.1 算法的改进

考虑不是把硬币分成两组，而是分成三组，前两组有[n/3]枚硬币A和B，其余的硬币作为第三组C，将前两组硬币放入天平比较。如果他们的重量相同，那么假币一定在第三组C中，用同样的方法对第三组C进行处理；如果前两组的重量不相等，那假币就出现在和(C/ （n-[n/3]*2)）*n/3重量不相等的一组里，重复上述过程直至找到假币。

2.2 伪代码

2.3 算法实现

3. 实验过程

3.1代码：

1.假币的随机生成

void random(int coin[]){
    for (int i = 0; i < N; i++)
        coin[i] =1;        //所有硬币的重量为1
    
    int  x = rand()%N; //生成0到n的随机数
    cout<<"经过random函数赋值，第"<<x+1<<"枚硬币为假币"<<endl;
    coin[x] = 2;  //第x枚硬币为假币
}

2.假币函数

int Coin(int low,int high,int n,int a[]){
    cout<<" low: "<<low<<" high: "<<high<<" n:"<<n<<endl;
    int i,num1,num2,num3;
    int add1=0,add2=0;
    if(n==0)
        return 0;
    if(n==1)
        return low+1;
    if(n%3==0)
        num1=num2=n/3;
    else
        num1=num2=n/3+1;
    num3=n-num1-num2;
    for(i=0;i<num1;i++)
        add1=add1+a[low+i];
    for(i=num1;i<num1+num2;i++)
        add2=add2+a[low+i];
    if(add1>add2)//题目假设，假币是比真币重所以add1重假币在低区间。
        return Coin(low, low+num1-1, num1, a);
    else if(add1<add2)
        return Coin(low+num1, low+num1+num2-1, num2, a);
    else
        return Coin(low+num1+num2, high, num3, a);
    
    
}

3.main函数

#include <iostream>
using namespace std;
const int N=8;
int coin[N];
int main(int argc, const char * argv[]) {
   random(coin);
     cout<<"经过random函数赋值，Coin数组如下"<<endl;
    for (int i = 0; i < N; i++)
        cout<<coin[i]<<" ";        //所有硬币的重量为1
    cout<<endl;
   int x= Coin(0,N-1,N,coin);
   cout<<"经过Coin函数计算，第"<<x<<"为假币"<<endl;
    return 0;
}

4.合起来

#include <iostream>
using namespace std;
const int N=8;
int coin[N];
void random(int coin[]){
    for (int i = 0; i < N; i++)
        coin[i] =1;        //所有硬币的重量为1
    
    int  x = rand()%N; //生成0到n的随机数
    cout<<"经过random函数赋值，第"<<x+1<<"枚硬币为假币"<<endl;
    coin[x] = 2;  //第x枚硬币为假币
}
int Coin(int low,int high,int n,int a[]){
    cout<<" low: "<<low<<" high: "<<high<<" n:"<<n<<endl;
    int i,num1,num2,num3;
    int add1=0,add2=0;
    if(n==0)
        return 0;
    if(n==1)
        return low+1;
    if(n%3==0)
        num1=num2=n/3;
    else
        num1=num2=n/3+1;
    num3=n-num1-num2;
    for(i=0;i<num1;i++)
        add1=add1+a[low+i];
    for(i=num1;i<num1+num2;i++)
        add2=add2+a[low+i];
    if(add1>add2)//题目假设，假币是比真币重所以add1重假币在低区间。
        return Coin(low, low+num1-1, num1, a);
    else if(add1<add2)
        return Coin(low+num1, low+num1+num2-1, num2, a);
    else
        return Coin(low+num1+num2, high, num3, a);
    
    
}
int main(int argc, const char * argv[]) {
   random(coin);
     cout<<"经过random函数赋值，Coin数组如下"<<endl;
    for (int i = 0; i < N; i++)
        cout<<coin[i]<<" ";        //所有硬币的重量为1
    cout<<endl;
   int x= Coin(0,N-1,N,coin);
   cout<<"经过Coin函数计算，第"<<x<<"为假币"<<endl;
    return 0;
}

3.2 结果截图