现有八枚硬币a b c d e f g h,已知其中一枚是假币,其重量不同于真币,但不知是较轻或较重,如何使用天平以最少的比较次数,决定出哪枚是假币,并得知假币比真币较轻或较重。
单独求假币的问题是不难的,但问题是“限制使用最少的比较次数”,所以我们不能以单纯的回圈比较来求解,我们可以使用决策树(decision tree),使用分析与树状图来协助求解。一个简单的状况是这样的:
1)我们比较a+b+c与d+e+f ,
如果相等,则假币必是g或h,我们先比较g或h哪个较重,如果g较重,再与x比较(x代指真币,且每一步必能找到一块真币),
1.1)若 g=x,从而g为真币,h为假币,则"真币较重,假币较轻";
1.2)若 g>x,从而g为假币,h为真币,则"真币较轻,假币较重";
1.3)若 g<x,从而g为假币,h为真币,则"真币较重,假币较轻",推出g是假币同时g较轻,这与g较重的前提条件矛盾,所以g<x这种情况不存在;
若选重的一方与真币进行比较,则结果只有等于和大于这2种情况,即只有1.1) 和1.2)这2种情况,即只有2个分支:等于=和 大于>。
1.4)同理,在第1)步时,若h较重,仿照1.1)、1.2)进行操作即可。
2)若a+b+c ≠ d+e+f,假设a+b+c较重(即a+b+c > d+e+f),比较 a+b 与 d+e的大小,
2.1)若 a+b = d+e,则说明d为真币(无差价,必为真币,这里的"价格"代指重量),令x=“真币重量”=d,
再将c与x进行比较,即与真币进行比较:
若 c=x,则c为真币,f为假币,推出“真币较重,假币较轻”;
若 c>x,则c为假币,f为真币,推出“真币较轻,假币较重”,
情况c< x 不存在;
2.2)若 a+b > d+e,则说明f为真币(无差价,必为真币),令x=“真币重量”=f,
再将a与x进行比较:
若 a=x,则a为真币,b为假币,推出“真币较重,假币较轻”;
若 a>x,则a为假币,b为真币,推出“真币较轻,假币较重;
情况a<x 不存在;
2.3)同理,在第2)步时,若d+e+f较重,仿照2.1)、2.2)进行操作即可。
由上面的推理知,至少需要 2+1 = 3步,才能在8块硬币中找出一块假币。
详细代码如下:
//Coins.cpp
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>void compare(int[], int, int, int);
void eightcoines(int[]);int main(void){int coins[8] = { 0 };int i;srand(time(NULL));for (i = 0; i < 8; i++){coins[i] = 10;}printf("\n输入假币重量(比10大或小): ");scanf("%d", &i);coins[rand() % 8] = i;eightcoines(coins);printf("\n\n列出所有钱币重量: ");for (i = 0; i<8; i++)printf("%d ", coins[i]);printf("\n");system("pause");return 0;
}void compare(int coins[], int i, int j, int k){if (coins[i] == coins[k]) //这里的k代表已验证的真币{if (coins[j] > coins[k]) {printf("\n假币 %d 较重", j + 1);}else {printf("\n假币 %d 较轻", j + 1);}}else if (coins[i] > coins[k]){printf("\n假币 %d 较重", i + 1);}else if (coins[i] < coins[k]){printf("\n假币 %d 较轻", i + 1);}
}void eightcoines(int coins[]){if (coins[0] + coins[1] + coins[2] ==coins[3] + coins[4] + coins[5]){compare(coins, 6, 7, 0);}else if (coins[0] + coins[1] + coins[2] >coins[3] + coins[4] + coins[5]){if (coins[0] + coins[3] == coins[1] + coins[4])compare(coins, 2, 5, 7);else if (coins[0] + coins[3] > coins[1] + coins[4])compare(coins, 0, 4, 7);else if (coins[0] + coins[3] < coins[1] + coins[4])compare(coins, 1, 3, 7);}else if (coins[0] + coins[1] + coins[2] <coins[3] + coins[4] + coins[5]){if (coins[0] + coins[3] == coins[1] + coins[4])compare(coins, 2, 5, 7);else if (coins[0] + coins[3] > coins[1] + coins[4])compare(coins, 3, 1, 7);else if (coins[0] + coins[3] < coins[1] + coins[4])compare(coins, 4, 0, 7);}
}
效果如下: