Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

Palindrom

powrót

Zagadnienie to zostało już omówione w kategorii zadania>>tablice.

Link do zagadnienia jest tutaj.

W tym artykule przedstawię alternatywne rozwiązanie problemu.

Rozwiązanie rozpocznę od przykładu. Przeanalizujmy wyraz:

{tex}ALAMALA{/tex}

Ustawię teraz dwa liczniki, jeden na pierwszej komórce w tablicy: 

{tex} i = 0 {/tex}

natomiast drugi na ostatniej komórce:

{tex} j = strlen(tab) - 1{/tex}

Pamiętajmy o tym, że komórki tablicy numerujemy od {tex}0{/tex}, a funkcja strlen zwróci nam ilość liter w wyrazie. Żeby prawidłowo ustawić licznik {tex}j{/tex} na ostatnim znaku w tablicy, należy odjąć {tex}1{/tex} od ilości liter ciągu.

Następnie poruszamy się licznikami w stronę środka wyrazu: licznikiem {tex}i{/tex} w prawą stronę natomiast licznikiem {tex}j{/tex} w lewą stronę porównując na bieżąco kolejne znaki. Jeśli jakaś para nie będzie sobie równa, oznacza to, że wyraz nie jest palindromem. Gdy liczniki spotkają się na środku i wszystkie pary będą zgodne to mamy palindrom.

Dla powyższego wyrazu mamy palindrom. Przeanalizujmy ten przypadek.

Wartość {tex}i{/tex} Wartość {tex}j{/tex} Litera na i-tej pozycji Litera na j-tej pozycji Status
{tex}i=0{/tex} {tex}j=6{/tex} A A ok
{tex}i=1{/tex} {tex}j=5{/tex} L L ok
{tex}i=2{/tex} {tex}j=4{/tex} A A ok

W następnej iteracji liczników spowoduje nieprawdziwość warunku {tex}i<j{/tex} - dalej nie musimy sprawdzać. Przeanalizujmy jeszcze jeden przypadek dla wyrazu

{tex}BCDSCB{/tex}

Wartość {tex}i{/tex} Wartość {tex}j{/tex} Litera na i-tej pozycji Litera na j-tej pozycji Status
{tex}i=0{/tex} {tex}j=5{/tex} B B ok
{tex}i=1{/tex} {tex}j=4{/tex} C C ok
{tex}i=2{/tex} {tex}j=3{/tex} D S źle

 

Tu natomiast widzimy, że w ostatniej iteracji para liter S jest niezgodna, a więc wryaz nie jest palindromem.

 Rozwiązanie:

 

#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
 
bool czy_palindrom(char tab[])
{
  //ustawiam liczniki "i" i "j" na pierwszy i ostatni znak wyrazu tab 
  int i=0, j = strlen(tab)-1; //pamiętajmy, że indeksujemy tablicę od 0
 
  while(i<j) //pętla wykonuje się do momentu spotkania liczników
  {
    if(tab[i]!=tab[j]) //gdy znaki nie będą się zgadzać, to wyraz nie jest palindromem
      return false;
 
    ++i; //przejscie do następnej litery idąc w prawą stronę
    --j; //przejscie do poprzedniej litry idąc w lewą stronę
  }
 
  return true; //wyraz jest palindromem
}
 
int main()
{
  char tab[100];
  cout<<"Podaj wyraz: ";
  cin>>tab;
 
  if(czy_palindrom(tab)) //lub if(czy_palindrom(tab)==true) lub if(czy_palindrom(tab)==1)
    cout<<"Wyraz "<<tab<<" jest palindromem"<<endl;
  else
    cout<<"Wyraz "<<tab<<" nie jest palindromem"<<endl;
 
  system("pause");
  return 0;
}