猜数字游戏的提示(Master-Mind Hints,UVa 340)题解

系统管理员 2022-12-28 04:25 140阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入
     *  输出
 *  原题（PDF）
 *   *  题目分析
     *  案例分析
     *  解题标程
     *  错题总结

--------------------

# 题目描述 #

你的任务是实现一个经典的“猜数字”游戏。给定答案序列和用户猜的序列，统计有多少数字位置正确（设为 A ），有多少数字在两个序列中都出现过但位置不对（ B ）。  
输入包含多组数据。每组输入第一行为序列长度 n ，第二行是答案序列，接下来是若干行猜测序列。猜测序列全 0 时表示该组数据结束。n=0 时输入结束。

对于每一组数据，输出的开头应有一行 “Game x:”（没有双引号，x为当前组数据的编号，从1开始递增），然后对于每个猜测序列，输出一组数，格式(A,B)，A,B的意义如上所示，注意在(A,B)之前要输出四个空格符。

## 输入 ##

4  
    1 3 5 5  
    1 1 2 3  
    4 3 3 5  
    6 5 5 1  
    6 1 3 5  
    1 3 5 5  
    0 0 0 0  
    10  
    1 2 2 2 4 5 6 6 6 9  
    1 2 3 4 5 6 7 8 9 1  
    1 1 2 2 3 3 4 4 5 5  
    1 2 1 3 1 5 1 6 1 9  
    1 2 2 5 5 5 6 6 6 7  
    0 0 0 0 0 0 0 0 0 0  
    0

## 输出 ##

（每个(A,B)前都有一个制表符TAB）

Game 1:  
    (1,1)  
    (2,0)  
    (1,2)  
    (1,2)  
    (4,0)  
    Game 2:
    (2,4)  
    (3,2)
    (5,0)  
    (7,0)

--------------------

# 原题（PDF） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

--------------------

## 题目分析 ##

通过匹配情况可以直接统计 A ，为了求得 B ，对于每个数字（1-9），统计二者出现次数 c1 和 c2 ，则min(c1,c2)就是该数字对于 B 的贡献。最后要减去A的部分。  
**B 中记录的是猜测串和答案串中每个数字 d 可能造成的最大不匹配数，A 中记录的是猜测串和答案串的实际匹配个数，因此 B-A 即为位置不匹配数**

## 案例分析 ##

如案例1：  
第一行 4 为序列长度  
第二行 1 3 5 5 为答案串  
之后若干行 为猜测串  
注意：

*  1、先判断答案串与猜测串的匹配相同情况
 *  2、在字符匹配成功后，该字符位置的字符不可能再出现位置不同的情况
 *  3、在答案串中同一个数字会会出现多次（即无法通过某一数字是否用过来确定匹配）
 *  4、序列内容数字的范围在1-9之间

## 解题标程 ##

#include <stdio.h>
    #define maxn 1010
    
    int main()
    {
        
      int n;
      int a[maxn];    //答案串
      int b[maxn];    //猜测串
      int kase=0;
      while(scanf("%d",&n)==1&&n){
        
        printf("%Game %d:\n",++kase);
    
        for(int i=0;i<n;i++)
          scanf("%s",a);
    
        while(1){
        
          int A=0,B=0;
          for(int i=0;i<n;i++){
        
            scanf("%c",&b[i]);
            
            //统计匹配情况，A 的值
            if(a[i]==b[i])
              A++;
          }
          
          //开始记录B的值
          for(int d=1;d<=9;d++){
        
            int c1=0;   //记录答案串中等于 d 的个数
            int c2=0;   //记录猜测串中等于 d 的个数
            for(int i=0;i<n;i++)[
              if(a[i]==d) c1++;
              if(b[i]==d) c2++;
            ]
    
            //比较c1和c2确定两串中可能的最大不匹配数
            if(c1<c2) B+=c1;
            else  B+=c2;
          }
          printf("  (%d,%d)\n",A,B-A);
        }
      }
      return 0;
    }

--------------------

## 错题总结 ##

*  1、用 **可能的不匹配数** 减去 **已经成功的匹配数** 所得为 **实际不匹配数**的巧妙想法
 *  2、最初想法为记录在答案串中每个数字的使用和匹配情况，用表来对应表示，但发现答案串中的数字可以为重复！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/f201700fa4f24c90808fa07c2d6c50d5.png