Palindromy

Palindrom

Palindromy są to wyrażenia, które brzmią tak samo czytane od lewej do prawej jak również od prawej do lewej. Powszechnie znanym przykładem palindromu jest wyrażenie Kobyła ma mały bok. Obecnie wyrażenia mające te cechę są raczej ciekawostką i używa się ich między innymi do gry słownej. Niemniej palindromy występują w każdym języku od zamierzchłych czasów. Można się natknąć na zapiski mówiące o magicznych właściwościach palindromów.

Przykład

Zasady porównywania wyjaśnię na podstawie wyrażenia Kobyła ma mały bok. Pierwsze co należy zrobić to usunąć wszystkie znaki interpunkcyjne czyli Kobyłamamałybok. Kolejny krok polega na zamianie dużych liter na małe (albo dużych na małe - zależy nam, aby był tylko jeden rodzaj): kobyłamamałybok. Teraz porównujemy ostatnią literę z pierwszą, przedostatnią z drugą i tak dalej...

Jak widać, aby porównać każdą literę z każdą musimy wykonać porównań w przypadku wyrazu o długości nieparzystej oraz w przypadku parzystej długości. W przypadku nieparzystej długości możemy pominąć sprawdzanie środkowego znaku - jest on równie odległy od prawej jak i od lewej strony, więc zawsze spełnia wymagania.

Implementacja

Funkcję, która sprawdza czy dane wyrażenie jest palindromem możemy zaimplementować przy pomocy pętli while oraz dwóch zmiennych:

1. bool palindrom (char* txt){
2.   int i = 0;
3.   int j = strlen(txt) - 1;
4.   while(i < j){
5.     if(txt[i] != txt[j])
6.       return false;
7.     i++;
8.     j--;
9.   }
10.   return true;

(1.) Funkcja palindrom() przyjmuje tylko jeden argument txt - jest to tablica, która zawiera wyrażenie do sprawdzenia. Jako wynik otrzymujemy wartość logiczną: true kiedy jest palindromem i false kiedy nie. (2., 3.) Ustalamy indeksy liter, które będziemy porównywać: jeden (i) jako pierwszy znak oraz (j) jako ostatni znak. (4.) Dopóki i jest mniejszy od j - czyli innymi słowy dopóki mamy znaki do porównywania to (5.) sprawdzamy czy porównywane znaki są różne. Jeśli tak jest to (6.) zwracamy fałsz. Zmieniamy indeksy porównywanych znaków: (7.) zwiększamy indeks i i zmniejszamy indeks j. Jeśli do zakończenia pętli while jej nie przerwiemy to oznacza, że jest to palindrom czyli (10.) zwracamy prawdę.

Inna implementacja

Funkcję palindrom() można też napisać przy pomocy pętli for:

1. bool palindrom (char* txt){
2.   int dl = strlen(txt);
3.   for(int i = 0; i < dl/2; i++)
4.     if(txt[i] != txt[dl - i - 1])
5.       return false;
6.   return true;
7. }

(1.) Nagłówek jest niezmieniony. (2.) Długość tekstu txt przechowamy w zmiennej dl. (3.) W pętli for sprawdzamy (4.) odpowiednie pary znaków. (5.) Jeśli znaki się różnią to zwracamy fałsz. (6.) Tak samo jak w przypadku pętli while jeśli nie przerwiemy pętli for to znaczy, że w argumencie txt jest palindrom czyli zwracamy prawdę.

Testowanie funkcji

Obydwie funkcje możemy przetestować przy pomocy poniższej funkcji main(). W celu ułatwienia sprawdzenia wyniku (4.) zwrócona wartość logiczna jest zamieniona na zrozumiały komunikat.

1. int main () {
2.   char* txt = new char[100];
3.   cin >> txt;
4.   cout << (palindrom(txt) ? "TAK" : "NIE") << endl;
5.   system("pause");
6.   return 0;
7. }

• Kod źródłowy Implementacja
• Kod źródłowy Inna implementacja

Zadania

Zadanie 1

Napisz funkcję, która sprawdzi czy wprowadzona liczba jest palindromem.

Przykładowo, gdy zostanie podana liczba 3748473 to na ekran zostanie wypisane:

1. TAK

• Kod źródłowy Zadanie 1