algorytm.org

Palindromy

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Palindromy
Ocena użytkowników:***** / 21
SłabyŚwietny 
Wpisany przez Marian, 24 lutego 2011 20:33

Palindrom (gr. palindromeo – biec z powrotem) – to wyrażenie brzmiące tak samo czytane od strony lewej do prawej i od prawej do lewej.
Aby sprawdzić czy dane słowo jest palindromem należy porównywać kolejne litery od końca oraz od początku – pierwszą od początku porównujemy z ostatnią, drugą z przedostatnią, itd. Schemat działania:

schemat blokowy - palindrom (wyraz)


Przykład:

Sprawdzimy czy wyraz "kajak" jest palindromem.
Ustawiamy i na 1 oraz j na długość (5).
sprawdzamy warunek i < j (jest spełniony, więc przechodzimy dalej)
Porównujemy litery wskazywane przez indeks i oraz j - ('k' = 'k') obie są takie same.
Zwiększamy indeks i oraz zmniejszamy indeks j (i = 2, j = 4).
Sprawdzamy warunek i < j (jest spełniony, więc przechodzimy dalej).
Porównujemy litery wskazywane przez indeks i oraz j - ('a' = 'a') obie są takie same.
Zwiększamy indeks i oraz zmniejszamy indeks j (i = 3, j = 3).
Sprawdzamy warunek i < j - nie jest spełniony, więc sprawdzany wyraz jest palindromem.

Sprawdzimy czy wyraz „rower” jest palindromem.
Ustawiamy i na 1 oraz j na długość (5).
sprawdzamy warunek i < j (jest spełniony, więc przechodzimy dalej)
Porównujemy litery wskazywane przez indeks i oraz j - ('r' = 'r') obie są takie same.
Zwiększamy indeks i oraz zmniejszamy indeks j (i = 2, j = 4).
sprawdzamy warunek i < j (jest spełniony, więc przechodzimy dalej)
Porównujemy litery wskazywane przez indeks i oraz j - tym razem są różne ('o' <> 'e') co oznacza, że wyraz „rower” nie jest palindromem.

W przypadku gdy chcemy sprawdzić czy palindromem jest zdanie, algorytm ten musi ignorować znaki nie będące literami. W takim wypadku schemat jego działania wyglądać będzie następująco:

schemat blokowy - palindrom (zdanie)


Przykład:

Posługując się powyższym schematem sprawdźmy czy zdanie "Kobyła ma mały bok" jest palindromem. Najłatwiej będzie zapisać to zdanie w tablicy:

123456789101112131415161718
Kobyła ma mały bok

Postępujemy zgodnie z algorytmem:
Do zmiennej i przypisujemy 1, natomiast do j długość, czyli 18.
Sprawdzamy warunek, 1 jest mniejsze od 18.
Zarówno pod indeksem i, jak i j znajduje się litera, więc przechodzimy do porównywania.
zdanie[i] = 'K' a zdanie[j] = 'k' – ignorujemy wielkość liter i widzimy, że znaki są takie same.
Zwiększamy indeks i i zmniejszamy indeks j.
Ponownie sprawdzamy warunek i < j.
Zarówno pod indeksem i, jak i j znajduje się litera, więc przechodzimy do porównywania.
zdanie[i] = 'o' a zdanie[j] = 'o' – znaki są takie same.
Zwiększamy indeks i i zmniejszamy indeks j.
Sprawdzamy warunek i < j.
Zarówno pod indeksem i, jak i j znajduje się litera, więc przechodzimy do porównywania.
zdanie[i] = 'b' a zdanie[j] = 'b' – znaki są takie same.
Zwiększamy indeks i i zmniejszamy indeks j.
Ponownie sprawdzamy warunek i < j.
Tym razem pod indeksem j znajduje się spacja, więc zmniejszamy indeks j o 1 i wracamy do sprawdzania warunku i < j.
Postępujemy analogicznie do momentu, gdy i i j będą wskazywały na tą samą literę – w naszym przypadku, jest to 'a' pod indeksem 9. Oznacza to, że zdanie jest palindromem.

Przykład w JavaScript:

Podaj wyraz/zdanie:

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
MarianC/C++Sprawdzanie wyrazów (C++)
.cpp
.cpp
***** / 37
MarianC/C++Sprawdzanie zdań (C++)
.cpp
.cpp
***** / 10
Bartosz BednarczykC/C++Sprawdzanie wyrazów
.cpp
.cpp
***** / 5
Tomasz LubińskiJavaScript
.js
.js
***** / 3
Nikodem SolarzRubyRozwiązanie szybkie. Porównanie z odwróconym ciągiem.
.rb
.rb
***** / 0
Nikodem SolarzRubyRozwiązanie dłuższe. Porównanie każdego znaku z kolei
.rb
.rb
***** / 0
Nikodem SolarzRubyRozwiązanie dłuższe. Wersja dla zdań
.rb
.rb
***** / 0
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 29 września 2012 16:36
Komentarze
photo
+2 # Piter71, Wrocław 2014-02-05 09:38
A nie prościej przeczytać od tylu i sprawdzić, czy jest tak samo brzmiące, jak od przodu?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Jurek 2014-07-30 10:45
Jest jeszcze jeden fajny sposób jak zrobić sprawdzanie czy słowo jest palindromem w C++.
Potrzebna jest do tego biblioteka algorithms.
Robimy tak:

string x = nasze_słowo;
y = x; reverse(y.begin(), y.end());
if(x == y) //... x jest palindromem
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz