a022: 迴文

2022.11.30 PM 07:00 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=a022
出題者 : jiangsir
標籤 : 字串處理(reverse)、for(i,j)迴圈、stack(堆疊)
難易度 : 2

解題想法 : 
本題有三種解法(如標籤)，因此分別使用了C,C++,Python三種語言實作不同的方式，參考如下 :

1. C - for(i,j)迴圈
設定兩個變數i,j，
i從0出發往右走，j從(輸入字串長度 - 1)出發往左走，直到 i>=j 為止，過程判斷輸入字串的第i項是否等於第j項，若不是則可直接輸出"no"並結束程式，若迴圈正常結束則必為回文，直接輸出"yes"即可。

(示意圖)
abcba               abcba
^   ^ ==(i++,j--)=>  ^ ^  ==(i++,j--)=> yes
i   j                i j

abca               abca 
^  ^ ==(i++,j--)=>  ^^  ==(b != c)=> no 
i  j                ij   


2. C++ - stack(堆疊)
首先將輸入字串分為前半和後半(皆不含中間)，並將前半先丟進stack，再來跑一個for i走訪後半，若stack最上方的元素不是字串的第i項的話，則直接輸出no並結束程式，反之則將stack的頂端元素pop掉，若迴圈正常結束則表示成功，輸出yes。

至於前半後半的判斷，需使用數學方式來實作，例如設字串長為a，若a為奇數，則 a/2 = 中間項，因此後半會從 a/2+1 開始；若a為偶數，則a/2就是後半的開頭。根據上述說明可以發現到，後半的開頭可以由以下方法求得 :
is_odd = s.size()%2 (奇數為1，偶數為0)
後半的開頭 = s.size()/2 + is_odd，符合規則。

3. Python - reverse
取得迭代器翻轉後的結果，可以使用[::-1]來實現，詳細可參考此連結(https://reurl.cc/YdqbK4)，如此一來我們只需要再多一個字串存翻轉後的結果，若翻轉後的結果和原字串相等，則輸出yes，反之輸出no。

//C language

#include<stdio.h>
#include<string.h>
char str[1005];
int main(){
    fgets(str,1005,stdin);
    for(int i=0,j=strlen(str)-1; i<j; i++,j--){
        if(str[i]!=str[j]){
            printf("no\n");
            return 0;
        }
    }
    printf("yes\n");
    return 0;
}

//C++ language

#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main(){
    string s;
    cin>>s;
    stack<char>st;
    for(int i=0;i<s.size()/2;i++){
        st.push(s[i]);
    }
    int is_odd = (s.size()%2);
    for(int i=s.size()/2+is_odd; i<s.size();i++){
        if(st.top()!=s[i]){
            cout<<"no\n";
            return 0;
        }
        st.pop();
    }
    cout<<"yes\n";
    return 0;
}

## Python language

s=input()
t=s[::-1]
if s==t: print("yes")
else: print("no")

相關文章

分享此文：