算法设计 |
您所在的位置：网站首页 › 瓷砖下放8个硬币方法图 › 算法设计 |
算法设计
|
八枚硬币问题 问题描述： 在八枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测出这枚假币。
解决思路： 假定输入的八枚硬币：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，
2. 分别取a,b,c、d,e,f 放在天平的两侧，现在假设硬币abc重于def，这说明这两组中有一组包含一枚假币，但不确定是在左侧，还是右侧。
3. 由上面的我们已经知道假币在前面两组了，那么剩下的那组的两枚硬币应该是相等的，我们取其中一枚作为考量值，这里取g硬币。取左侧的一枚硬币：a硬币，再取右侧的一枚硬币：e硬币，把ae作为新左侧的硬币组合，再取右侧的一枚硬币：d硬币+考量值：g硬币作为新右侧组合。如果出现重量不等，则可确定：这两组中的一组存在一枚假币，但具体是哪一枚还没有确定。 4. 我们可以通过把a、e、d分别于h比较，假如与h不一样，则这枚硬币为假币，并且可以确定这枚假币是重还是轻。整个解决思路就是这样。
5. 最后结果e与h比较，e不等于h重量，并且较轻，e为最终结果。 
代码实现： #include 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 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 |
【本文地址】
今日新闻 |
推荐新闻 |