2013/10/06

[HW]找偽幣

輸入: 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;
}