POJ1013 Counterfeit Dollar 解题报告

有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++;  
补充：软件开发 , C++ ,