本文主要是介绍算法竞赛入门经典 回文词 UVa401 msg数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这里不讲解题, 讲答案里的一个细节, 就是msg数组的作用及原理.
作者在书中没有直接说明msg数组的作用及原理, 我这里就简明讲解下.
首先, msg作为一个字符串数组.
msg[0]就对应 “not a palindrome”, 1就对应 “a regular palindrome”, 依些类推. 下标的所有取值[0,3]
刚好4个数值对应4个状态.
有朋友可能会问这里为啥不这样写呢?
If(p)
{if(m)//状态3, p!=0 && m!=0else//状态1, p!=0 && m==0}
else
{if(m)//状态2, p==0 && m!=0else//状态0, p==0 && m==0
}
这样写没错, 但代码冗长, 明显可以优化.
学过linux的朋友可能就知道, linux的文件权限rwx, 对应的数字就是421, 而且每个[0,7]的数字可以唯一对应一种权限.
7 rwx
6 rw-
5 r-x
4 r--
3 -wx
2 -w-
1 --x
唉嘛, 是不是有点像二进制0和1.
是的, 化成0和1就变成这样了
7 rwx 111
6 rw- 110
5 r-x 101
4 r-- 100
3 -wx 011
2 -w- 010
1 --x 001
是的, 这里的m*2+p就是这个原理. 作者在初始化的时候, 把m和p都置为1. 就是判断前默认是回文串和镜像串.
为什么m要乘以2 ? 学过进制转换吧, 二进制转10进制的时候, 比如有k位 0表示最低位, num(i)表示这个数字的第i位.
Ans = num(0)*2^0 +num(1)*2^1+num(2)*2^2+...+num(k-2)*2^(k-2)+num(k-1)*2(k-1)
所以2进制的权从低位到高位为1,2,4,8,16,32…
我们这里用二进制的2个位, 就能表示2*2=4个状态.
linux文件权限用了3个位, 所以4,2,1,就是这么来的.
打个表吧:
m p m*2+p(D) m*2+p(B)
0 0 0 00
0 1 1 01
1 0 2 10
1 1 3 11
D表示10进制, B表示2进制.
源代码:
// UVa401 Palindromes
// Rujia Liu
#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)) return rev[ch - 'A'];return rev[ch - '0' + 25];
}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-1-i]) m = 0; // 不是镜像串}printf("%s -- is %s.\n\n", s, msg[m*2+p]);}return 0;
}
这篇关于算法竞赛入门经典 回文词 UVa401 msg数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
