輸入: 32枚外觀看起來都相同的硬幣, 其中一枚是偽幣而且其重量與其他31枚不同(輕與重都有可能)
輸出: 找出這枚偽幣並且決定它是比真幣輕或重
Note 1: 唯一能使用的工具是一支天秤
Note 2: 只能使用5次天秤就必需找出偽幣並且決定它是比真幣輕或重
#include <iostream>
#include <cstdlib>
using namespace std;
int Coin[32]; //存取硬幣質量 硬幣編號由0開始到31 ps.宣告為全域變數供其他副程式使用
//用來比較偽幣和真幣值輛大小的副程式CheckMass()，回傳大於or小於符號提供輸出
char CheckMass(int M_1, int M_2, int M_3, int M_4) //這個檢測實際上是觀察3rd的結果，以在5th給出結論
{
//M_1 + M_2代表真幣質量和，M_3 + M_4代表偽幣與真幣質量和，藉以判斷偽幣質量較真幣輕或重
if(M_1 + M_2 > M_3 + M_4)
{
return '<';
}
else
{
return '>';
}
}
//用來計算各個分組質量(此處為相對值，令真幣質量為1單位)的副程式GetGroupWeight()
int GetGroupWeight(int Begin, int End)
{
int Sum = 0;
for(int i=Begin; i<=End; i++)
{
Sum = Sum + Coin[i];
}
return Sum;
}
int main()
{
int FakeNo,FakeNoWeight;
int Group_A, Group_B, Group_C, Group_D;
//作法:將所有硬幣編號，由0~31，並平均分為4組(A B C D)，每組8個
//初始化陣列 將所有硬幣質量以1為基準
for(int i=0; i<32; i++)
{
Coin[i] = 1;
}
cout << "請輸入偽幣編號: ";
cin >> FakeNo;
cout << "請輸入偽幣質量(大於或小於1): ";
cin >> FakeNoWeight;
Coin[FakeNo] = FakeNoWeight;
Group_A = GetGroupWeight(0,7);
Group_B = GetGroupWeight(8,15);
Group_C = GetGroupWeight(16,23);
Group_D = GetGroupWeight(24,31);
if(Group_A == Group_B) // 1st time 推論偽幣在C or D之中
{
if(Group_A == Group_C) //2nd 偽幣在 D，將其兩兩一組，分成4小組
{
if(Coin[24] + Coin[25] == Coin[26] + Coin[27]) // 3rd 推論偽幣是編號(28 29) (30 31)之一
{
if(Coin[0] + Coin[1] == Coin[28] + Coin[29]) //4th 推論偽幣是編號(30 31)之一
{
if(Coin[0] == Coin[30]) //5th 結論
{
cout << "偽幣編號為 " << 31 << " 質量 " << CheckMass(1,1,Coin[30],Coin[31]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 30 << " 質量 " << CheckMass(1,1,Coin[30],Coin[31]) << " 真幣" << endl;
}
}
else //推論偽幣是編號(28 29)之一
{
if(Coin[0] == Coin[28]) //5th 結論
{
cout << "偽幣編號為 " << 29 << " 質量 " << CheckMass(1,1,Coin[28],Coin[29]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 28 << " 質量 " << CheckMass(1,1,Coin[28],Coin[29]) << " 真幣" << endl;
}
}
}
else //推論偽幣是編號(24 25) (26 27)之一
{
if(Coin[0] + Coin[1] == Coin[24]+ Coin[25]) //4th 推論偽幣是編號(26 27)之一
{
if(Coin[0] == Coin[26]) //5th 結論
{
cout << "偽幣編號為 " << 27 << " 質量 " << CheckMass(1,1,Coin[27],Coin[28]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 26 << " 質量 " << CheckMass(1,1,Coin[27],Coin[28]) << " 真幣" << endl;
}
}
else //推論偽幣是編號(24 25)之一
{
if(Coin[0] == Coin[24]) //5th 結論
{
cout << "偽幣編號為 " << 25 << " 質量 " << CheckMass(1,1,Coin[24],Coin[25]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 24 << " 質量 " << CheckMass(1,1,Coin[24],Coin[25]) << " 真幣" << endl;
}
}
}
}
else //偽幣在C，將其兩兩一組，分成4小組
{
if(Coin[16] + Coin[17] == Coin[18] + Coin[19]) // 3rd 推論偽幣是編號(20 21) (22 23)之一
{
if(Coin[0] + Coin[1] == Coin[20] + Coin[21]) //4th 推論偽幣是編號(22 23)之一
{
if(Coin[0] == Coin[22]) //5th 結論
{
cout << "偽幣編號為 " << 23 << " 質量 " << CheckMass(1,1,Coin[22],Coin[23]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 22 << " 質量 " << CheckMass(1,1,Coin[22],Coin[23]) << " 真幣" << endl;
}
}
else //推論偽幣是編號(20 21)之一
{
if(Coin[0] == Coin[20]) //5th 結論
{
cout << "偽幣編號為 " << 21 << " 質量 " << CheckMass(1,1,Coin[20],Coin[21]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 20 << " 質量 " << CheckMass(1,1,Coin[20],Coin[21]) << " 真幣" << endl;
}
}
}
else //推論偽幣是編號(16 17) (18 19)之一
{
if(Coin[0] + Coin[1] == Coin[16]+ Coin[17]) //4th 推論偽幣是編號(18 19)之一
{
if(Coin[0] == Coin[18]) //5th 結論
{
cout << "偽幣編號為 " << 19 << " 質量 " << CheckMass(1,1,Coin[18],Coin[19]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 18 << " 質量 " << CheckMass(1,1,Coin[18],Coin[19]) << " 真幣" << endl;
}
}
else //推論偽幣是編號(16 17)之一
{
if(Coin[0] == Coin[16]) //5th 結論
{
cout << "偽幣編號為 " << 17 << " 質量 " << CheckMass(1,1,Coin[16],Coin[17]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 16 << " 質量 " << CheckMass(1,1,Coin[16],Coin[17]) << " 真幣" << endl;
}
}
}
}
}
else //偽幣在A or B之中
{
if(Group_A == Group_C) // 2nd 偽幣在B，將其兩兩一組，分成4小組
{
if(Coin[8] + Coin[9] == Coin[10] + Coin[11]) // 3rd 推論偽幣是編號(12 13) (14 15)之一
{
if(Coin[0] + Coin[1] == Coin[12] + Coin[13]) //4th 推論偽幣是編號(14 15)之一
{
if(Coin[0] == Coin[14]) //5th 結論
{
cout << "偽幣編號為 " << 15 << " 質量 " << CheckMass(1,1,Coin[14],Coin[15]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 14 << " 質量 " << CheckMass(1,1,Coin[14],Coin[15]) << " 真幣" << endl;
}
}
else //推論偽幣是編號(12 13)之一
{
if(Coin[0] == Coin[12]) //5th 結論
{
cout << "偽幣編號為 " << 13 << " 質量 " << CheckMass(1,1,Coin[12],Coin[13]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 12 << " 質量 " << CheckMass(1,1,Coin[12],Coin[13]) << " 真幣" << endl;
}
}
}
else //推論偽幣是編號(8 9) (10 11)之一
{
if(Coin[0] + Coin[1] == Coin[8]+ Coin[9]) //4th 推論偽幣是編號(10 11)之一
{
if(Coin[0] == Coin[10]) //5th 結論
{
cout << "偽幣編號為 " << 11 << " 質量 " << CheckMass(1,1,Coin[10],Coin[11]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 10 << " 質量 " << CheckMass(1,1,Coin[10],Coin[11]) << " 真幣" << endl;
}
}
else //推論偽幣是編號(8 9)之一
{
if(Coin[0] == Coin[8]) //5th 結論
{
cout << "偽幣編號為 " << 9 << " 質量 " << CheckMass(1,1,Coin[8],Coin[9]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 8 << " 質量 " << CheckMass(1,1,Coin[8],Coin[9]) << " 真幣" << endl;
}
}
}
}
else //偽幣在A，將其兩兩一組，分成4小組
{
if(Coin[0] + Coin[1] == Coin[2] + Coin[3]) // 3rd 推論偽幣是編號(4 5) (6 7)之一
{
if(Coin[8] + Coin[9] == Coin[4] + Coin[5]) //4th 推論偽幣是編號(6 7)之一
{
if(Coin[0] == Coin[6]) //5th 結論
{
cout << "偽幣編號為 " << 7 << " 質量 " << CheckMass(Coin[8],Coin[9],Coin[6],Coin[7]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 6 << " 質量 " << CheckMass(Coin[8],Coin[9],Coin[6],Coin[7]) << " 真幣" << endl;
}
}
else //推論偽幣是編號(4 5)之一
{
if(Coin[8] == Coin[4]) //5th 結論
{
cout << "偽幣編號為 " << 5 << " 質量 " << CheckMass(Coin[8],Coin[9],Coin[4],Coin[5]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 4 << " 質量 " << CheckMass(Coin[8],Coin[9],Coin[4],Coin[5]) << " 真幣" << endl;
}
}
}
else //推論偽幣是編號(0 1) (2 3)之一
{
if(Coin[8] + Coin[9] == Coin[0]+ Coin[1]) //4th 推論偽幣是編號(2 3)之一
{
if(Coin[0] == Coin[2]) //5th 結論
{
cout << "偽幣編號為 " << 3 << " 質量 " << CheckMass(Coin[8],Coin[9],Coin[2],Coin[3]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 2 << " 質量 " << CheckMass(Coin[8],Coin[9],Coin[2],Coin[3]) << " 真幣" << endl;
}
}
else //推論偽幣是編號(0 1)之一
{
if(Coin[8] == Coin[0]) //5th 結論
{
cout << "偽幣編號為 " << 1 << " 質量 " << CheckMass(Coin[8],Coin[9],Coin[0],Coin[1]) << " 真幣" << endl;
}
else
{
cout << "偽幣編號為 " << 0 << " 質量 " << CheckMass(Coin[8],Coin[9],Coin[0],Coin[1]) << " 真幣" << endl;
}
}
}
}
}
system("PAUSE");
return 0;
}
