cpe練習筆記 UVa401 Palindromes




原文題目

題目大意
判斷下面三種型態的字串

regular palindrom
從左邊或是右邊讀起來都一樣
ex. ABCDEDCBA

mirrored string
看起來是左右完全一樣
ex. 3AIAE
※ E的反向是3(參考下圖)

mirrored palindrome
左右讀起來一樣,看起來也一樣
ex. ATOYOTA


反向參考圖

注意
數字0和英文字母O被視為相同,只有O有效


策略
1. 判斷字串奇偶
2. 用字串左半減去右半字串(ASCII)
3. 如果相等 regular palindrome 或 mirrored palindrome
    如果不相等 not a palindrome 或 mirrored string

程式碼

#include <stdlib.h>
#include <stdio.h>

void check(char datas[],int num);
void check2(char datas[],int num);
void check3(char datas[],int num);

//字典集
char dic[37]={'A','B','C','D','E',
    'F','G','H','I','J',
    'K','L','M','N','O',
    'P','Q','R','S','T',
    'U','V','W','X','Y',
    'Z','1','2','3','4',
    '5','6','7','8','9'};
//反向字典集 
char rdic[37]={'A','n','n','n','3',
    'n','n','H','I','L',
    'n','J','M','n','O',
    'n','n','n','2','T',
    'U','V','W','X','Y',
    '5','1','S','E','n',
    'Z','n','n','8','n'};

//反向自己
char sdic[13]={'A','H','I','M','O','T','U','V','W','X','Y','1','8'};


int main(){
 int i,j,count;
 char datas[500]={""};
 
 
 //讀入資料
 i=0;
 while(scanf("%c",&datas[i])!=EOF){
  //資料列結尾
  if(datas[i]!='n')
   printf("%c",datas[i]); //印出字串
  if(datas[i]=='n'){
   printf(" -- ");
   count=i;
   i=-1;
   check(datas,count);//字串奇偶和過濾
  }
  i++;
 }
}

//字串奇偶和過濾
void check(char datas[],int num){
 int i,j,tmp,tmp2=0;
 int mp=0;
 
 //判斷字串奇偶
 if((num)%2) //奇
  tmp=num/2+1;
 else
  tmp=num/2;//偶
  
 //判斷是否左右一樣
 for(i=0;i<tmp;i++){
  tmp2=tmp2+(datas[i]-datas[num-i-1]);
 }
  
 if(tmp2==0) //是->判斷類型
  check2(datas,num); //可能為 regular palindrome 或 mirrored palindrome 
 else
  check3(datas,num); //可能是 not a palindrome 或 mirrored string 
}

//regular palindrome 或 mirrored palindrome 
void check2(char datas[],int num){
int i,j,count=0;
 for(i=0;i<num;i++){
  for(j=0;j<15;j++){
   if(datas[i]==sdic[j])
    count++;
  }
 }
 
if(count==num)
 printf("is a mirrored palindrome.nn");
else
 printf("is a regular palindrome.nn");
}

//not a palindrome 或 mirrored string 
void check3(char datas[],int num){
 int i,j,count=0;
 for(i=0;i<num;i++){
  for(j=0;j<37;j++){
   if(datas[i] == dic[j] && rdic[j] != 'n')//表示該字串存在反向
    count++;
  }
 }
 
 if(count>=num)//全部都有反向
  printf("is a mirrored string.nn");
 else  
  printf("is not a palindrome.nn");
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料