枚举--称硬币

一时失言乱红尘 2021-11-29 17:44 353阅读 0赞

**问题描述**  
　　赛利有 12 枚银币。其中有11 枚真币和1 枚假币。假币看起来和真币没有区别，但是重  
量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称  
三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币，发现天平平  
衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说  
明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。

**输入数据**  
输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果  
用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其  
中平衡状态用"up'', "down'', 或 "even''表示, 分别为右端高、右端低和平衡。天平左右的硬币  
数总是相等的。

**输出要求：**  
输出哪一个标号的银币是假币，并说明它比真币轻还是重。

**输入样例**  
1  
ABCD EFGH even  
ABCI EFJK up  
ABIJ EFGH even  
输出样例  
K is the counterfeit coin and it is light.

**我的思路：**

**　　我采用的是比较笨的方法，就是先根据给出的条件，通过设置标准位，来找出假币，然后再判断假币是比硬币轻还是比硬币重。思路不难想，就是实现有点多。所以造成我的代码很长。当然这还不符合OJ上面的输入和输出，我就不想改了，将就着吧。**

//先把假币找出来，然后再判断是重还是轻
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define BASE 65
    
    int Jude(char c,const char *szLeft, const char *szRight,const char *szStr)
    {
         //返回1表示比真币轻，返回2表示比真币重
        int i=0;
    
        while (szLeft[i])
        {
            if (c == szLeft[i])  //假币在左边
            {
                if (strcmp(szStr,"up") == 0)
                {
                    return 2;
                }
                else
                {
                    return 1;
                }
            }
            i++;
        }
        
        //在右边
        if(strcmp(szStr,"up") ==0)
        {
            return 1;
        }
        else
        {
            return 2;
        }
    }
    
    int main()
    {
        char left[7],right[7],str[5];
        char tmp_l[7],tmp_r[7],tmp_str[5];  //用来存储不平衡的那行
        int result[12],i,Count = 3;
        FILE *fp;
        memset(result,0,sizeof(result));
        fp = fopen("in.txt","r");
        if (fp == NULL)
        {
            printf("Fopen failed.\n");
            return -1;
        }
    while (Count)
    {
        memset(left,0,sizeof(left));
        memset(right,0,sizeof(left));
    
        fscanf(fp,"%s%s%s",left,right,str);
        //printf("left:%s,right:%s,str:%s\n",left,right,str);
        if (strcmp(str,"even") == 0)
        {  
            i=0;
            while (left[i])
            {
                result[left[i]-BASE] = 1;   //等于1表示是真币
                i++;
            }
    
            i=0;
            while (right[i])
            {
                result[right[i]-BASE] = 1;   
                i++;
            }
        }
    
        if (strcmp(str,"up") == 0)
        {
            strcpy(tmp_l,left);
            strcpy(tmp_r,right);
            strcpy(tmp_str,str);
    
            i=0;
            while (left[i])
            {
                if (result[left[i] - BASE] == 0)
                {
                    result[left[i]-BASE] = 2;     //表示有可能是假币
                }
                i++;
            }
            
            i=0;
            while(right[i])
            {
                if (result[right[i] - BASE] == 0)  //没称过
                {
                    result[right[i] - BASE] = 2;
                }
                i++;
            }
        }
    
        if (strcmp(str,"down") == 0)
        {
            strcpy(tmp_l,left);
            strcpy(tmp_r,right);
            strcpy(tmp_str,str);
    
            i=0;
            while (right[i])
            {   
                if (result[right[i] - BASE] == 0)  //没称过
                {
                    result[right[i]-BASE] = 2;
                }
                i++;
            }
    
            i=0;
            while(left[i])
            {
                if (result[left[i] - BASE] == 0)  //没称过
                {
                    result[left[i] - BASE] = 2;
                }
                i++;
            }
        }
    
        Count --;
    
    }
    
        for(i=0; i < 12; i++)
        {
            if (result[i] == 2)
            {
                if(Jude(BASE + i,tmp_l,tmp_r,tmp_str) == 1)
                {
                    printf("%c is the counterfeit coin and it is light.\n",BASE + i);
                }
                else
                {
                    printf("%c is the counterfeit coin and it is heavy.\n",BASE + i);
                }
            }
        }
    
        return 0;
    }

**更秒的解法：**

**　　标准答案上的解法是用枚举法，解题思路是跟我的逆过来的。总共12个字母，只有两种情况，比真币轻还是比真币重。那么我们可以去枚举每个硬币的两种情况，总共24种情况。然后用每种情况套入到给出的条件去判断是否都符合，都符合条件了就是我们要的结果。**

**所以说，我们应该学会从不通的角度去考虑问题，有时候逆过来解决问题，可能方法更简单些。**

转载于:https://www.cnblogs.com/Jason-Damon/archive/2013/04/13/3018425.html