Zastanówmy się w jaki sposób działa oraz jak wygląda algorytm, który jednoznacznie określi, czy podane słowo jest palindromempalindrompalindromem, czy też nie?

Przeanalizujemy dwa rozwiązania.

Metoda pierwsza

Aby sprawdzić, czy podane słowo jest palindromem, możemy porównywać pary liter. Pierwsza para to pierwsza i ostatnia litera w słowie. Jeżeli dwie litery są takie same, zwiększymy licznik oznaczający liczbę poprawnych par liter o 1. Następną parą będzie druga i przedostatnia litera w słowie. Jeżeli litery są sobie równe, znów zwiększamy licznik o 1. I tak będziemy wykonywać sprawdzanie, aż dojdziemy do środka wyrazu, czyli aż wykonamy: (długośćSłowa) divdiv 2 sprawdzeń.

Zwróć uwagę, że korzystając z polecenia div, nie ma znaczenia, czy słowo ma parzystą, czy nieparzystą liczbę znaków.

Oto schemat blokowy realizujący pierwszą metodę sprawdzania.

R1VHkFIbbQgZs

Schemat pętli. 1. zielony okrąg. START. 2. Niebieski prostokąt. licznik = 0, slowo = „KAJAK”, dlugosc_slowa = 5, indeks = 1. 3. Fioletowy romb. Indeks <= dllugosc_slowa, div 2 Jeśli 3 nie to 4. Fioletowy romb. licznik= dlugosc_slowa div 2, jeśli nie to 5. Fioletowy romb. Wypisz „slowo nie jest palindromem” 6. Czerwony okrąg, STOP Jeśli 4. Fioletowy romb. licznik= dlugosc_slowa div 2, tak to 5. Fioletowy romb. Wypisz „slowo jest palindromem” 6. Czerwony okrąg, STOP Jeśli 3. Fioletowy romb. Indeks <= dllugosc_slowa, div 2 tak to 4. Fioletowy romb. slowo [indeks] = slowo[dlugosc_slowa‑indeks+1], jeśli tak, to 5. Niebieski prostokąt. licznik = licznik + 1 6. Niebieski prostokąt indeks = indeks + 1 7. Powrót do kroku 2. Jeśli 4. Fioletowy romb. slowo [indeks] = slowo[dlugosc_slowa‑indeks+1] nie, to 5. Niebieski prostokąt indeks = indeks + 1 1. Powrót do kroku 2.

Zwróć uwagę na wyrażenie logiczne: słowo[indeks] == słowo[długośćSłowa - indeks - 1].

Pierwszym ważnym aspektem jest sposób odwoływania się do konkretnych liter w słowie. W tym przypadku używamy nawiasów kwadratowych. Przykładowo: słowo[0] oznacza pierwszą literę w słowie.

Jak wcześniej wspomnieliśmy będziemy porównywać pary znaków. Tę operację najłatwiej wykonać wewnątrz pętli. Będzie się ona wykonywać dopóki indeks jest mniejszy od połowy długości słowa. Wewnątrz pętli sprawdzamy czy znak pobrany z pierwszej połowy słowa (slowo[indeks]) jest taki sam jak jego odpowiednik z drugiej połowy (słowo[długośćSłowa - indeks - 1]). Zwróćmy uwagę w jaki sposób wyznaczamy indeks drugiego znaku. Od długośćSłowa odejmujemy indeks, a także wartość -1. Operacja ta wynika z faktu, że znaki w słowo numerujemy od zera.

Przeanalizuj, jak działa schemat blokowy. Zapisuj ulegające zmianie wartości zmiennych. Jeżeli masz problem, w następnej sekcji dokonamy wspólnej analizy algorytmu.

Metoda druga

Bardziej optymalna metoda na sprawdzenie, czy podane słowo jest palindromem, wykorzystuje to, że odnalezienie jednej pary liter, które nie są sobie równe (a powinny być), automatycznie powoduje, że podane słowo na pewno nie jest palidromem.

Na początku możemy założyć, że mamy do czynienia ze słowem, które jest palindromem, a gdy natrafimy na wykluczającą się parę, zakończymy algorytm z informacją, że słowo nie jest palindromem.

Zbadajmy, czy słowo „ABCDEEDXBA” jest palidromem. Najpierw sprawdzone zostaną dwie litery 'A': pierwsza i ostatnia w słowie. Kolejną sprawdzaną parą będą litery 'B' (druga i przeostatnia w słowie). Następnie sprawdzone zostaną litery: 'C' oraz 'X' (trzecia od początku i trzecia od końca litera). Już wiemy, że nie ma potrzeby dalszego sprawdzania liter. Słowo na pewno nie jest palindromem, skoro zawiera co najmniej jedną parę liter, które powinny być takie same, a nie są. I właśnie w tym momencie algorytm zakończy porównywanie z informacją, że podane słowo nie jest palindromem.

Gdyby podane słowo było równe „ABCCBA”, program dokonałby trzech sprawdzeń i zakończył działanie z informacją, że podane słowo jest palindromem (program nie natrafił na parę różnych liter).

Poniżej przedstawiony został schemat blokowy realizujący drugą metodę sprawdzania:

RZlBtyWo8CIlD

Schemat pętli. 1. zielony okrąg. START. 2. Niebieski prostokąt. czy_palindrom = prawda, slowo = „ABCDDBA”, dlugosc_slowa = 7, indeks = 1 3. Fioletowy romb. Indeks <= dlugosc_slowa, div 2, jeśli tak to 4. Fioletowy romb. slowo[indeks] = slowo[dlugosc_slowa‑indeks+1], jeśli tak 5. Niebieski prostokąt. Indeks = indeks + 1 6. Powrót do kroku nr 2. Jeśli 4. Fioletowy romb. slowo[indeks] = slowo[dlugosc_slowa‑indeks+1], nie, to 5. Niebieski prostokąt. czy_palindrom = fałsz 6. Fioletowy romb. czy_palindrom = prawda, jeśli tak 7. Fioletowy romb. Wypisz „slowo jest palindromem” 8. Czerwony okrąg. STOP Jeśli 6. Fioletowy romb. czy_palindrom = prawda, nie to 7. Fioletowy romb. Wypisz „slowo nie jest palindromem” 8. Czerwony okrąg. STOP Jeśli 3. Fioletowy romb. Indeks <= dlugosc_slowa, div 2, nie to idź do kroku 6. Fioletowy romb. czy_palindrom = prawda, jeśli tak 7. Fioletowy romb. Wypisz „slowo jest palindromem” 8. Czerwony okrąg. STOP Jeśli 6. Fioletowy romb. czy_palindrom = prawda, nie to 7. Fioletowy romb. Wypisz „slowo nie jest palindromem” 8. Czerwony okrąg. STOP

W przedstawionej metodzie wykorzystaliśmy zmienną czyPalindrom, która na początku inicjowana jest wartością prawda. Jeżeli natrafimy na parę znaków, które nie są takie same (a powinny być), zmieniamy wartość czyPalindrom na fałsz. Następnie algorytm kończy się z informacją, że podane słowo nie jest palindromem.

Słownik