回文词(Palindromes,UVa401)题解

系统管理员 2022-12-28 04:24 210阅读 0赞

### 文章目录 ###

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

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

# 题目描述 #

输入是一个字符串，判断它是否为回文串以及镜像串。输入字符串保证不含数字0 。所谓回文串，就是反转以后和原串相同，如 abba 和 madam 。所谓镜像串，就是左右镜像之后和原串相同，如 2S 和 3AIAE 。

注意，并不是每个字符在镜像之后都能得到一个合法字符。  
在本题中，每个合法字符的镜像如下表所示：

> Character Reverse  
> A - - - - A  
> E - - - - 3  
> H - - - - H  
> I - - - - I  
> J - - - - L  
> L - - - - J  
> M - - - - M  
> O - - - - O  
> S - - - - 2  
> T - - - - T  
> U - - - - U  
> V - - - - V  
> W - - - - W  
> X - - - - X  
> Y - - - - Y  
> Z - - - - 5  
> 1 - - - - 1  
> 2 - - - - S  
> 5 - - - - Z  
> 8 - - - - 8

## 输入 ##

NOTAPALINDROME  
    ISAPALINILAPASI  
    2A3MEAS  
    ATOYOTA

## 输出 ##

NOTAPALINDROME -- is not a palindrome.  
    ISAPALINILAPASI -- is a regular palindrome.   
    2A3MEAS -- is a mirrored string.  
    ATOYOTA -- is a mirrored palindrome.

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

# 原题（PDF） #

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

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

## 算法分析 ##

关键点：在判断回文串的同时，判断是否为镜像串。  
找到对应字符在镜像表中的对应位置

## 解题标程 ##

#include <stdio.h>
    #include <string.h>
    #include <ctype.h>
    
    const char *rev="A   3  HIL JM O   2TUVWXY51SE Z  8 ";  //镜像表
    const char *msg[]={
        "not a palindrome","a regular palindrome","a mirrored string","a mirrored palindrome"};
    
    //字符在镜像表中的对应位置
    char r(char ch)
    {
        
      if(isalpha(ch))           //isalpha()用于判断字符是否为字母
        return rev[ch-'A'];     //镜像表中前26个均为字母排序
      return rev[ch-'0'+25];    //镜像表中26个字典序结束后即为数字
    }
    
    int main()
    {
        
      char s[30];
      while(scanf("%s",s)==1){
        
        int len=strlen(s);
        int p=1,m=1;    //回文串与镜像串的标志
        for(int i=0;i<(len+1)/2;i++){
        
          if(s[i]!=s[len-1-i])  p=0;    //非回文串  
          if(r(s[i])!=s[len-i-1]) m=0;  //非镜像串
        }
        printf("%s -- is %s.\n",s,msg[m*2+p]);  //用(m*2+p)的值巧妙的统一输出
      }
      return 0;
    }

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

## 错题总结 ##

*  1、先进行回文串的判断，再进行镜像串的判断。二者判断可同时进行。
 *  2、<ctype.h> 头文件中定义的isalpha、isdigit、isprint等工具可以用于判断字符的属性
 *  **isalpha()**：用于**判断是否为字母**
 *  **isdigit()**：用于**判断是否为数字**
 *  **isprint()**：用于**判断是否为可打印字符**

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

*  3、标程中的 msg\[m\*2+p\] 的巧妙统一输出，可以多进行思考、借鉴。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/af9081e22b864dd09100396fd2ff4dc4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]: /images/20221120/b9d9bccb0507468693e4dd9dc132120b.png