1. 实验题目

在 8 枚外观相同的硬币中, 有一枚是假币, 并且已知假币与真币的重量不同, 但不知
道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币, 设计一个高
效的算法来检测出这枚假币。

2. 实验目的

(1 ) 深刻理解并掌握减治法的设计思想;
(2 ) 提高应用减治法设计算法的技能;
(3 ) 理解这样一个观点: 建立正确的模型对于问题的求解是非常重要的。

3. 实验要求

(1 ) 设计减治算法实现8 枚硬币问题;
(2 ) 设计实验程序, 考察用减治技术设计的算法是否高效;
(3 ) 扩展算法, 使之能处理n 枚硬币中有1 枚假币的问题。

4. 问题分析

将T(n)的问题转化为T(n/3)的问题

5. 算法思路

1.创建4个数组,前三个的数量为n/3;最后一组为n%3
2.先对前三组的质量进行判断
  2.1前三组相等,对第四组进行递归处理
  2.2前三组不等,可能会出现:
    2.2.1   1=2>3
    2.2.2   1=2<3
    2.2.3   1=3>2
    2.2.4   1=3<2
    2.2.5   2=3>1
    2.2.6   2=3<1
    然后对较大或者较小组进行递归处理
3.递归结束的标志是n==1或者n==2
4.输出假币的大小
5.输出假币的位置

6. 算法实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1001;                       //假设求解8枚硬币问题
int a[N] = {0};
int temp=0;     //设定全局变量存储一个真币的值
void Coin(int low, int high, int n);

int main()
{
    int n;
    int i;
    cin>>n;
    for(i=0; i<n; i++)
        cin>>a[i];
    Coin(0,n-1,n);
    return 0;
}

void Coin(int low, int high, int n)           //在a[low]~a[high]中查找假币
{
    int i, num1=0, num2=0, num3=0,num4=0;      // num1、num2和num3存储3组硬币的个数
    int add1=0,add2=0,add3=0;        //add1,add2,add3存储前三组硬币的重量和
    int temp1=0,temp2=0,temp3=0;
    //cout<<low<<endl;  用于测试数据,懒得debug慢慢找


    num1=num2=num3=n/3;
    num4=n%3;


    for (i = 0; i < num1; i++)                    //计算第1组硬币的重量和
        add1 = add1 + a[low + i];
    for (i = num1; i < num1*2; i++)          //计算第2组硬币的重量和
        add2 = add2 + a[low + i];
    for(i = num1*2; i < num1*3; i++)
        add3 = add3 +a[low+i];
    temp1=add1+add2;
    temp2=add1+add3;
    temp3=add2+add3;

    if( temp1 == temp2)					//1=2=3
    {
        if (num4 == 1)
        {
            if(a[low+num1*3]>temp)
                cout<<"假币是第"<<low+num1*3+1<<"个,假币的质量较大"<<endl;
            else
                cout<<"假币是第"<<low+num1*3+1<<"个,假币的质量较小"<<endl;
        }
        else if(n==2)
        {
            if(a[low]==temp)
            {
                if(a[low+num1*3+1]>temp)
                    cout<<"假币是第"<<low+num1*3+2<<"个,假币的质量较大"<<endl;
                else
                    cout<<"假币是第"<<low+num1*3+2<<"个,假币的质量较小"<<endl;;
            }
            else
            {
                if(a[low]>temp)
                    cout<<"假币是第"<<low+1<<"个,假币的质量较大"<<endl;
                else
                    cout<<"假币是第"<<low+1<<"个,假币的质量较小"<<endl;
            }
        }
    }
    else if(temp1>temp2&&temp1==temp3)  //1=3<2
    {
        temp = a[low];
        Coin(low+num1,low+num1*2,num1);
    }
    else if(temp1>temp2&&temp2==temp3) 	//1=2>3
    {
        temp = a[low];
        Coin(low+num1*2,low+num1*3,num1);
    }
    else if(temp1<temp2&&temp1==temp3)  //1=3>2
    {
        temp=a[low];
        Coin(low+num1,low+num1*2,num1);
    }
    else if(temp1<temp2&&temp2==temp3)  //1=2<3
    {
        temp=a[low];
        Coin(low+num1*2,low+num1*3,num1);
    }
    else if(temp2>temp3)    			//2=3<1
    {
        temp=a[num1];
        Coin(low,low+num1,num1);
    }
    else if(temp2<temp3)    			//2=3>1
    {
        temp=a[num1];
        Coin(low,low+num1,num1);
    }
}

7. 运行效果(截图)

测试数据:
8
2 2 2 4 2 2 2 2
假币的质量较大
假币是第4个

16
2 2 2 2 2 2 2 2 2 2 2 4 2 2 2 2
假币是第12个,假币的质量较大

16
2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2
假币是第8个,假币的质量较小

8. 算法分析

~~判断大小情况太复杂~~
算法比较长，因为加入了假币和真币质量大小的比较
如果只需要判断假币的位置，代码量可缩减大半

9. 经验归纳与总结

函数传多个参数时，程序出错了，所以返回类型我改为了void，需要补习一下C++函数传递参数方面的知识

实验项目3———8枚硬币问题