算法设计--八枚硬币问题

「爱情、让人受尽委屈。」 2022-03-06 08:10 306阅读 0赞

八枚硬币问题

问题描述：

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

**解决思路：**

假定输入的八枚硬币：a、b、c、d、e、f、g、h

实验解决思路：把硬币分成三组，从八枚硬币中任取六枚a、b、c、d、e、f，在天平两端各放三枚进行比较。 假设a、b、c三枚放在天平的一端，d、e、f三枚放在天平的另一端，可能出现如图所示的三种比较结果。

实验步骤：

1.      将硬币分为3组：a,b,c、d,e,f、g,h，

![20130428145207718][]

2.      分别取a,b,c、d,e,f 放在天平的两侧，现在假设硬币abc重于def，这说明这两组中有一组包含一枚假币，但不确定是在左侧，还是右侧。

![20130428145215687][]

3.      由上面的我们已经知道假币在前面两组了，那么剩下的那组的两枚硬币应该是相等的，我们取其中一枚作为考量值，这里取g硬币。取左侧的一枚硬币：a硬币，再取右侧的一枚硬币：e硬币，把ae作为新左侧的硬币组合，再取右侧的一枚硬币：d硬币+考量值：g硬币作为新右侧组合。如果出现重量不等，则可确定：这两组中的一组存在一枚假币，但具体是哪一枚还没有确定。

![20130428145222608][]

4.      我们可以通过把a、e、d分别于h比较，假如与h不一样，则这枚硬币为假币，并且可以确定这枚假币是重还是轻。整个解决思路就是这样。

![20130428145229616][]

5.      最后结果e与h比较，e不等于h重量，并且较轻，e为最终结果。

![20130428145239913][]

**代码实现：**

#include<iostream>
    using namespace std;
    
    //函数声明
    void eightcoin(int arr[]);
    void compare(int a, int b,int real, int index1,int index2);
    void print(int jia, int zhen, int i);
    
    int main()
    {
    	int i = 0;
    	int arr[8];
    	//这里输入a、b、c、d、e、f、g、h的重量
    	cout<<"请输入八枚硬币："<<endl;
    	for(i; i < 8; i++)
    	{
    		cin>>arr[i];
    	}
    	eightcoin(arr);
    
    	system("pause");
    	return 0;
    }
    /**
    *  八枚硬币问题描述：
    *，有一枚是假币，并且已知假币与真币的重量不同
    *，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币
    *，设计一个高效的算法来检测出这枚假币
    * @date:2013/4/27
    * @author:wwj
    */
    void eightcoin(int arr[])
    {
    	//1. 取数组中的前6个元素分为两组进行比较abc,def
    	//会有a+b+c > d+e+f | a+b+c == d+e+f | a+b+c < d+e+f 三种情况
    	int abc = arr[0] + arr[1] + arr[2];
    	int def = arr[3] + arr[4] + arr[5];
    	int a = arr[0];
    	int b = arr[1];
    	int c = arr[2];
    	int d = arr[3];
    	int e = arr[4];
    	int f = arr[5];
    	int g = arr[6];
    	int h = arr[7];
    	if(abc > def)		//6枚硬币必有一枚假币，g,h为真币
    	{
    		if((a + e) > (d + b))	//去掉c,f，且b，e互换后，没有引起天平变化，说明假币必然是a，d中的一个
    		{
    			compare(a, d, g,1,3);
    			
    		}
    		else if((a + e) == (d + b))
    		{
    			compare(c,f,g,2,5);
    		}
    		else
    		{
    			compare(b,e,g,1,4);
    		}
    	}
    	else if(abc == def)	//假币在g,h之中，最好状态
    	{
    		
    		if(g == a)
    		{
    			print(h,g,7);
    		} 
    		else
    		{
    			print(g,h, 6);
    		}
    
    	}
    	else				//abc < def 这两组存在一枚假币，g,h为真币
    	{
    		if((a + e) > (d + b))
    		{
    			compare(b,e,g,1,4);
    		}
    		else if((a + e) == (d + b))
    		{
    			compare(c,f,g,2,5);
    		}
    		else
    		{
    			compare(a, d, g,1,3);
    		}
    	}
    
    }
    /**
    * 取出可能有一枚假币的两枚假币，作为参数a和参数b
    * real表示真币的重量，index1为第一枚硬币的下标，index2为第二枚硬币的下标
    */
    void compare(int a, int b,int real, int index1,int index2)
    {
    	if(a == real)
    	{
    		print(b,real,index2);
    	}
    	else
    	{
    		print(a, real,index1);
    	}
    }
    
    void print(int jia, int zhen, int i)
    {
    	if(jia > zhen)
    	{
    		cout<<"位置在："<<(i + 1)<<"是假币!"<<"且偏重!";
    	}
    	else {
    		cout<<"位置在："<<(i + 1)<<"是假币!"<<"且偏轻!";
    	}
    }

**验证结果：**

**![20130428145626772][]**

[20130428145207718]: /images/20220306/a4b1d8b26a564194abe20a8b4f4cf4c8.png
[20130428145215687]: /images/20220306/67269d34e7db4cb285fbf2649f9b154f.png
[20130428145222608]: /images/20220306/47fae0c7520946c4aaac056c204f21ff.png
[20130428145229616]: /images/20220306/0d0d967c414e4e77962702e043f5a86b.png
[20130428145239913]: /images/20220306/a2f673d680a74eeb94000b2f1065ee54.png
[20130428145626772]: /images/20220306/9d751c63dd304ec783e6887859662bbe.png