Sprawdza, czy tekst czyta się tak samo od przodu i od tyłu – porównując końce.
Palindrom to słowo (albo liczba), które czyta się tak samo od przodu i od tyłu. Przykłady: kajak, radar, zakaz, potop. Sprawdzenie, czy tekst jest palindromem, to klasyczne, proste zadanie na tekstach.
Jak to sprawdzić? Najprościej dwoma „palcami": jeden ustawiamy na pierwszej literze, drugi na ostatniej. Porównujemy je. Jeśli są takie same, przesuwamy pierwszy w prawo, a drugi w lewo i porównujemy kolejną parę. Jeśli w którymkolwiek momencie litery się różnią – to nie palindrom. Jeśli palce spotkają się w środku bez żadnej różnicy – to palindrom.
Krótszy sposób: odwrócić cały tekst i sprawdzić, czy jest taki sam jak oryginał. Działa i jest bardzo krótki w kodzie, ale zużywa więcej pamięci – trzeba zapamiętać odwróconą kopię tekstu.
Uwaga na pułapkę: często trzeba najpierw pominąć spacje i wielkość liter. Na przykład „Kobyła ma mały bok" jest palindromem dopiero wtedy, gdy usuniemy spacje i zamienimy wszystko na małe litery. Zwykłe porównanie znak po znaku bez tego zawiedzie.
Na maturze: klasyk działu tekstowego. Trzeba umieć wskazać, która para liter się nie zgadza, albo napisać pętlę porównującą końce tekstu.
Prześledź, jak dwa „palce" schodzą się od końców do środka. Sprawdzana para jest podświetlona, pasujące litery robią się zielone, a pierwsza niepasująca para – czerwona (i wtedy wiadomo, że to nie palindrom).
Naciśnij „Krok", aby porównać skrajne litery, albo „Auto".
funkcja czy_palindrom(T, n): lewy ← 0 prawy ← n - 1 dopóki lewy < prawy: jeżeli T[lewy] ≠ T[prawy]: zwróć fałsz // para liter się różni lewy ← lewy + 1 prawy ← prawy - 1 zwróć prawda
def czy_palindrom(tekst):
"""Sprawdza, czy tekst czyta się tak samo od przodu i od tyłu."""
lewy = 0
prawy = len(tekst) - 1
while lewy < prawy:
if tekst[lewy] != tekst[prawy]:
return False # znaleziono różniącą się parę
lewy += 1
prawy -= 1
return True
# Krótszy wariant: porównanie z odwróconym tekstem
def czy_palindrom_krotko(tekst):
return tekst == tekst[::-1]
print(czy_palindrom("kajak")) # Wynik: True
print(czy_palindrom("kotek")) # Wynik: False#include <string>
#include <iostream>
using namespace std;
bool czy_palindrom(const string& t) {
int lewy = 0, prawy = (int)t.size() - 1;
while (lewy < prawy) {
if (t[lewy] != t[prawy]) return false; // para sie rozni
lewy++;
prawy--;
}
return true;
}
int main() {
cout << czy_palindrom("kajak") << "\n"; // Wynik: 1 (prawda)
cout << czy_palindrom("kotek") << "\n"; // Wynik: 0 (falsz)
}Bo każdą parę „litera z lewej – litera z prawej" sprawdzamy raz. Gdy palce dojdą do środka, wszystkie pary są już porównane. Sprawdzanie dalej porównywałoby te same pary drugi raz, bez sensu.
Środkowa litera nie ma pary i nie trzeba jej z niczym porównywać – zawsze „pasuje sama do siebie". Pętla z warunkiem lewy < prawy sama ją pomija.
Tak. Pusty tekst i pojedyncza litera czytają się tak samo w obie strony, więc z definicji są palindromami. Pętla od razu się kończy i zwraca prawda.
Najpierw usuń spacje i znaki przestankowe oraz zamień litery na małe, a dopiero potem porównuj końce. Dzięki temu „Kobyła ma mały bok" wyjdzie palindromem.
Sprawdzamy metodą dwóch palców: porównujemy pierwszą literę z ostatnią, potem drugą z przedostatnią, i tak do środka. Wpisz odpowiedzi i kliknij Sprawdź.
Dla słowa kajak (5 liter) pierwsza para to k i , druga para to a i , a środkowa litera j nie ma pary. Wszystkie pary się zgadzają, więc czy kajak jest palindromem? .
Ile par liter trzeba porównać, żeby sprawdzić słowo? To połowa długości, zaokrąglona w dół:
| Słowo | Długość | Par do sprawdzenia |
|---|---|---|
| kot | 3 | |
| anna | 4 | |
| kajak | 5 | |
| komputer | 8 |
O(n)O(1)Czasowa O(n). Sprawdzamy co najwyżej połowę liter – pary od końców do środka – więc czas rośnie liniowo z długością tekstu. Pamięć O(1) przy metodzie dwóch palców, bo nie kopiujemy tekstu (wariant z odwracaniem potrzebuje O(n) pamięci na kopię).
Te zadania CKE sprawdzają dokładnie to zagadnienie – link prowadzi wprost do treści podpunktu w arkuszu:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: