有12枚硬幣(標記為A-L)，其中有1枚是假幣，但不知道假幣比真幣更輕或更重。Sally借助於天平，設計出一種方案，可以恰好三次測量出誰是假幣、比真幣更輕或更重。要求你幫助Sally，根據她的測量數據，計算出誰是假幣、比真幣更輕還是更重。例如一組測量數據為： ABCD EFGH even ABCI EFJK up ABIJ EFGH even 注意：天平左右的硬幣數量總是相等的。 可以計算得出K是假幣，且比真幣更輕。 分析 解決這道題的關鍵是抓住以下幾個關鍵點： （1）假幣只有一個，因此在不平衡的測量中，假幣一定會出現。記錄硬幣出現在不平衡測量中的次數，是判斷假幣的一個條件。但僅用這個條件是不夠的，比如： A B up CD AB up C D even 在這個例子中，A和B出現在不平衡測量中的次數相等，都是2，因此還需考慮第二點。 （2）假幣在測量中表現是一致的，假如假幣比真幣更輕，那麼它在不平衡測量中一定總在up的一邊。所以，凡是在不平衡測量裡，時而在up的一邊，時而在down的一邊，如上例中的A，則說明其對測量的失衡沒有決定性作用，則一定是真幣，應該將它標注出來。 （3）出現在平衡測量中的硬幣全是真幣，將它們標注出來。 算法思路 定義COIN結構，如下： struc COIN { bool appear; int type; int count; }; 其中，appear標記是否出現在三次測量中，因為並非所有硬幣都參與測量；type表示硬幣的類型，初始為UNDEFINED，確定為真幣則為DOLLAR，若非真幣出現在up一邊則為LIGHT，否則為HEAVY；count表示硬幣出現在不平衡測量中的次數。 算法分為三步： Step 1：初始化COIN數組，為本輪計算做好准備。 Step 2：根據輸入的測量數據，更新COIN數組。 Step 3：掃描COIN數組，找到假幣，並將其信息打印出來。 代碼 // 1013.cpp // 2012-12-27 by btwsmile #include <stdio.h> #include <string.h> // define #define UNDEFINED -1 #define LIGHT 0 #define DOLLAR 1 #define HEAVY 2 #define N 12 // struct COIN struct COIN { bool appear; int type; int count; }; // functions // prepare - reset coin[] void prepare(COIN*); // update - update coin[] void update(COIN*, char*, char*, char*); // search - find Counterfeit in coin[] int search(COIN*); // entry int main() { COIN coin[N]; char szLeft[10]; char szRight[10]; char szRelation[10]; int n; scanf("%d", &n); for(int i = 0; i < n; ++i) { prepare(coin); // scanf & update for(int j = 0; j < 3; ++j) { scanf("%s %s %s", szLeft, szRight, szRelation); update(coin, szLeft, szRight, szRelation); } // find Counterfeit int iCounterfeit = search(coin); // print if(iCounterfeit > -1) { printf("%c is the counterfeit coin and it is %s.\n", ('A'+iCounterfeit), ((coin[iCounterfeit].type == HEAVY) ? "heavy" : "light") ); } } return 0; } // definitions // prepare void prepare(COIN* coin) { for(int i = 0; i < N; ++i) { coin[i].appear = false; coin[i].type = UNDEFINED; coin[i].count = 0; } } // update void update(COIN* coin, char* pszLeft, char* pszRight, char* pszRelation) { int iSize = strlen(pszLeft); char* psz[2] = { pszLeft, pszRight }; if( strcmp(pszRelation, "even") == 0 ) // "even" { for(int i = 0; i < iSize; ++i) { for(int j = 0; j < 2; ++j) { int index = psz[j][i] - 'A'; coin[index].appear = true; coin[index].type = DOLLAR; } } } else // "up" or "down" { int iTypeLeft, iTypeRight; if( strcmp(pszRelation, "up") == 0 ) { iTypeLeft = HEAVY; iTypeRight = LIGHT; } else { iTypeLeft = LIGHT; iTypeRight = HEAVY; } for(int i = 0; i < iSize; ++i) { for(int j = 0; j < 2; ++j) { int index = psz[j][i] - 'A'; coin[index].appear = true; coin[index].count++; if(coin[index].type != DOLLAR) { int iType = ((j>0) ? iTypeRight : iTypeLeft); if(coin[index].type == UNDEFINED) coin[index].type = iType; else if(coin[index].type != iType) coin[index].type = DOLLAR; } } } } // end else } // search int search(COIN* coin) { int iMaxCount = 0; int iCounterfeit = -1; for(int j = 0; j < N; ++j) { if(coin[j].appear && coin[j].type != DOLLAR && coin[j].count > iMaxCount) { iMaxCount = coin[j].count; iCounterfeit = j; } } return iCounterfeit; }
