Programowanie i algorytmy

Palindrom tekstowy

Zadanie 5. Napisz program, który określi czy wczytany ciąg jest palindromem tekstowym.

 

Uwaga!!! Palindromem nazywamy wyraz, który czytany z lewej do prawej jest taki sam jak z prawej do lewej np.:

kajak

kobyłamamałybok

 

Dane wejściowe

Pierwszy wiersz składa się z jednej liczby n<10000, który określa ilość zestawów danych.

Każdy zestaw danych opisany w osobnym wierszu składa się z jednego wyrazu nie dłuższego niż 100 małych liter języka angielskiego.

Dane wyjściowe

Dla każdego zestawu danych wypisz słowo tak, jeśli dany ciąg jest palindromem, w przeciwnym wypadku wypisz nie.

Przykład

Wejście

3

adam

kobylamamalybok

sedes

Wyjście

nie

tak

tak

Program można testować na automatycznej sprawdzarce tutaj

Rozwiązanie.

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
bool czy_palindrom(char tab[])
{
  int dl; //zmienna przechowuje długość wczytanego wyrazu
  dl = strlen(tab); //strlen zwraca ilość znaków w tablicy tab
  --dl; //zmniejszenie wartości zmiennej dl, w celu wskoczenia
      // na ostatni indeks tablicy
  for(int i=0;i<=dl/2;i++)
    if(tab[i]!=tab[dl-i]) //jeśli odpowiednie litery nie będą się zgadzać
      return false;    //funkcja zwróci false
 
  return true; //gdy wszystkie litery będą się zgadzać   
}
 
int main()
{
  int t; /*zmienna określa ilość zestawów danych*/
 
  char wyraz[101]; //zmienna przechowuje wczytany wyraz
 
  cin>>t; //wczytanie liczby testów
 
  while(t--) //pętla odpowiedzialna za wczytanie zestawów danych
  {
    cin>>wyraz;
 
    if(czy_palindrom(wyraz)) //lub if(czy_palindrom(wyraz == true)
       cout<<"tak"<<endl;
    else
       cout<<"nie"<<endl;
 
  }
 
  return 0;
} 
 

 

Przykładowe dane wejściowe:

5
kobylamamalybok
kaftan
kajak
preeeeeeeerp
a

 

Dane wyjściowe:

tak
nie
tak
tak
tak

 

Objaśnienie.

Rozpatrzmy słowo kajak. Popatrzmy jak przechowywane są kolejne litery tego wyrazu:

k - 0

a - 1

j - 2

a - 3

k - 4

Żeby słowo było palindromem pierwszy znak musi być równy ostatniemu, drugi przedostatniemu itd. Czyli:

tab[0] = tab[4]

tab[1] = tab[3]

dalej nie trzeba sprawdzać

Zauważmy, że gdy do zmiennej dl przypiszemy długość słowa kajak (liczbę 5) i zmniejszymy ją o 1, to będzie pasowała ona jako ostatni numer komórki tablicy. Teraz przy każdym przejściu pętli początek zwiększamy o wartość licznika i, a koniec zmniejszamy wskakując na odpowiednie litery do porównania (tab[i] = tab[dl-i]). Warto zauważyć, że pętla powinna wykonać się nie więcej niż połowę długości wyrazu o parzystej ilości znaków i w naszym przypadku {tex}iloscznakow\ div\ 2{/tex} dla nieparzystej ilości znaków (nie musimy wykonywać dodatkowego odejmowania w tablicy).

 

powrót