我的八枚硬币问题
实验项目3———8枚硬币问题
1.问题分析：
这个问题就是要找出这八枚硬币中放入假币，前提是还不知道是偏重还是偏轻，所有，要设计一个高效的算法找出这么假币，并且得知是偏重还是偏轻。
假定输入的八枚硬币：a、b、c、d、e、f、g、h
把硬币分成三组，从八枚硬币中任取六枚a、b、c、d、e、f，在天平两端各放三枚进行比较。 假设a、b、c三枚放在天平的一端，d、e、f三枚放在天平的另一端，可能出现如图所示的三种比较结果。
2. 算法设计思路--伪代码////emmmmm----写给自己看的，不会写伪代码，随便写的
输入：硬币的重量
输出：假币所在的位置以及偏轻还是偏重
1.如果abc的重量大于def的重量，就移开cf，交换be的位置
1.如果ae的重量大于db的重量，比较a,d和g币的重量，并且输出
2.如果ae的重量等于db的重量，比较cf和g币的重量，并且输出
3.如果ae的重量小于db的重量，比较eb和g币的重量，并且输出
2. 如果abc的重量等于def的重量， 比较gh和a币的重量，并且输出
3. 如果abc的重量小于def的重量，同步骤1.
4.算法结束
3. 算法实现
程序源代码：
#include<iostream>
using namespace std;
void Findout(int v[]);//在八枚硬币中查找
void cmp(int a,int b,int real,int index1,int index2);//将两枚硬币和真硬币比较，找出其中的假硬币
void Outcome(int fal,int tru,int i);//打印数据
int main()
{
int i,v[9];
cout<<"请依次输入硬币的重量："<<endl;
for(i=1;i<=8;i++)
cin>>v[i];
Findout(v);
return 0;
}
void Findout(int v[])
{
int a=v[1];
int b=v[2];
int c=v[3];
int d=v[4];
int e=v[5];
int f=v[6];
int g=v[7];
int h=v[8];
int abc = a+b+c;
int def = d+e+f;
if(abc>def)
{
if((a+e) > (d+b))
{
cmp(a,d,g,2,4);
}
else if((a+e) == (d+b))
{
cmp(c,f,g,3,6);
}
else
{
cmp(b,e,g,2,5);
}
}
else if(abc == def)
{
if(g == a)
{
Outcome(h,g,8);
}
else
{
Outcome(g,h,7);
}
}
else
{
if((a + e) > (d + b))
{
cmp(b,e,g,2,5);
}
else if((a + e) == (d + b))
{
cmp(c,f,g,3,6);
}
else
{
cmp(a, d, g,2,4);
}
}
}
void Outcome(int fal,int tru,int i)
{
cout<<"该假币的位置在： "<<i<<endl;
if(fal > tru) cout<<"该假币的重量偏重！"<<endl;
else cout<<"该假币的重量偏轻 ！"<<endl;
}
void cmp(int a,int b,int real,int index1,int index2)
{
if(a == real) Outcome(b,real,index2);
else Outcome(a,real,index1);
}4. 运行结果（截图）
5. 算法分析
在这个八枚硬币问题中，应用减治法，将问题一分为二，这样只需要3次比较便能解决问题。对于n枚硬币问题，同样可以用减治法处理，采用分治和递归的方法逐步接近问题的解。
6. 经验归纳与总结
减治法是把一个大问题划分为若干个小问题，但是这些子问题不需要分别 ，只需要求解其中的一个子问题，因而也无须对子问题的解进行合并，这样大大提高了算法的效率。
实验扩展：
扩展算法, 使之能处理n 枚硬币中有1 枚假币的问题。
解题思维：将硬币分成A、B、C三组，如果A等于C，则假币在B组，递归将B三等分，重复上述步骤；如果A不等于C，则假币在A和C中，分别将A和B、C和B比较，哪个不等于B，则假币必在其中，递归将其三等分，重复上述步骤。注意，当分组里的硬币数少于3个时，无须划分，直接将组里某个硬币与组外任一硬币比较，不同即是假币，相同的话说明另外一个必是假币。
代码如下：---------硬币数量可以根据 Maxnum 的值修改
#include <iostream>
using namespace std;
#define Maxnum 9
int Out(int arr[],int low,int high)
{
int sum = 0;
for(int i = low; i<=high; i++)
sum += arr[i];
return sum;
}
int nCoin(int v[], int n, int low, int high)
{
int k = n/3;
int Remain = n%3;
if(Remain == 0) //恰好分成了三组
{
int index = 0;
int A = Out(v,low,low+k-1);
int B = Out(v,low+k,low+2*k-1);
int C = Out(v,low+2*k,high);
if(n == 3)//只有三枚硬币的情况
{
if(A==B) index = high;
if(A==C) index = high-1;
if(B==C) index = low;
return index;
}
else
{
if(A==B)
{
index = nCoin(v,k,low+2*k,high);//递归调用，从C组中找出假币
return index;
}
if(A==C)
{
index = nCoin(v,k,low+k,low+2*k-1);
return index;
}
if(B==C)
{
index = nCoin(v,k,low,k-1);
return index;
}
}
}
if(Remain == 1) //第三组剩下一枚硬币的情况
{
//把最后一个去掉，比较。
int index = high;
int A,B,C;
if(n==1)
return index;
else
{
A = Out(v,low,low+k-1);
B = Out(v,low+k,low+2*k-1);
C = Out(v,low+2*k,high-1);
//cout<<A<<B<<C<<endl;
if(A == B && B == C)
{
return index;
}
else if(A==B)
{
cout<<"ramain1 aaaabbb"<<endl;
index = nCoin(v,k,low+2*k,high-1);
return index;
}
else if(A==C)
{
cout<<"ramain1 aaaaccc"<<endl;
index = nCoin(v,k,low+k,low+2*k-1);
return index;
}
else if(B==C)
{
cout<<"ramain1 bbbccc"<<endl;
index = nCoin(v,k,low,k-1);
return index;
}
}
}
if(Remain == 2) ////余数为2的情况！
{
int index = 0;
int index1 = high-1;
int index2 = high;
int A,B,C;
A = Out(v,low,low+k-1);
B = Out(v,low+k,low+2*k-1);
C = Out(v,low+2*k,high-2);
//cout<<A<<B<<C<<endl;
if(n<3)
{
int campare11 ;
if(high != Maxnum-1)
campare11 = v[Maxnum-1];
else
campare11 = v[0];
if(v[high] == campare11)
index = low;
if(v[low] == campare11)
index = high;
return index;
}
else
{
if(A==B&&B==C)
{
int cam = v[0];
if(v[high-1] == cam)
index = index2;
if(v[high] == cam)
index = index1;
return index;
}
else if(A==B)
{
cout<<"ramain2 aaaabbb"<<endl;
index = nCoin(v,k,low+2*k,high-2);
return index;
}
else if(A==C)
{
cout<<"ramain2 aaaacccc"<<endl;
index = nCoin(v,k,low+k,low+2*k-1);
return index;
}
else if(B==C)
{
cout<<"ramain2 bbbccc"<<endl;
index = nCoin(v,k,low,k-1);
return index;
}
}
}
}
int main()
{
int number;
int v[Maxnum];
cout<<"请输入硬币的重量：";
for(int i=0;i<Maxnum;i++)
{
cin>>v[i];
}
if(Maxnum<3)
{
cout<<"数量太少，无法比较"<<endl;
return 0;
}
number = nCoin(v, Maxnum, 0, Maxnum-1);
int flag;
if(number!= Maxnum-1)
flag = v[Maxnum-1];
else
flag = v[0];
if(v[number] < flag)
cout<<"假币的位置为 "<<number+1<<" 并且假币偏轻"<<endl;
else
cout<<"假币的位置为 "<<number+1<<" 并且假币偏重"<<endl;
return 0;
}
运行截图如下：