Co to jest palindrom?

Palindrom to słowo lub ciąg wyrazów, które zapisane i czytane od lewej do prawej strony brzmią tak samo, jak zapisane i czytane od prawej do lewej. Przykładami palindromów są:

• łapał za kran, a kanarka złapał,

• wół utył i ma miły tułów.

Poznaliśmy już dwa sposoby implementacji algorytmu sprawdzającego, czy dane słowo jest palindromem. Zapiszemy obie implementacje i dokonamy porównania, by ocenić, która z nich jest efektywniejsza.

Komputerowa realizacja w języku Java

Przed rozpoczęciem implementacji algorytmu sprawdzającego, czy dane słowo jest palindromem, warto przypomnieć kilka aspektów związanych ze składnią języka Java.

• pętla – to w niej będziemy porównywać słowa indeks po indeksie,

• funkcja wbudowanafunkcja wbudowanafunkcja wbudowana charAt() umożliwia dostęp do pojedynczego znaku typu String, co okaże się niezwykle przydatne,

• funkcje – najpierw napiszemy program, wykorzystując główną funkcję programu main(), a następnie dokonamy modyfikacji i wykonamy osobną funkcję do rozwiązania tego problemu,

• operacje wejścia/wyjścia – w szczególności użycie klasy Scanner, która umożliwi użytkownikowi samodzielne wpisanie słowa do sprawdzenia w naszym programie.

$\text{I}$ sposób

Zaimplementujemy sposób z porównywaniem znaków o skrajnych indeksach. Przypomnijmy, na czym on polegał: słowo, które jest palindromem, napisane od przodu i od tyłu wygląda tak samo. Oznacza to, że konkretne pary znaków muszą być takie same: pierwsza i ostatnia, druga i przedostatnia itp. Zacznijmy od napisania kodu, który umożliwi użytkownikowi wpisanie własnego słowa w celu sprawdzenia, czy jest ono palindromem. Zrobimy to z pomocą klasy Scanner. Przeanalizujmy następujący fragment kodu:

Scanner scanner = new Scanner(System.in);

System.out.println("Podaj słowo do sprawdzenia");

String slowoTest = scanner.nextLine();

Najpierw deklarujemy obiekt klasy Scanner – tu został on nazwany scanner. Standardowe wejście System.in pozwala na sczytywanie tego, co wpisujemy z klawiatury. Następnie tworzymy zmienną typu String o nazwie slowoTest, do której zapisujemy to, co podał użytkownik za pomocą funkcji wbudowanej nextLine(). Jej dokładne działanie polega na pobieraniu tego, co się wpisuje aż do wciśnięcia przycisku Enter na klawiaturze.

Kolejnym krokiem będzie zadeklarowanie pętli, w której będą porównywane skrajne znaki.

for (int i = 0, j = slowoTest.length() - 1; i < slowoTest.length() && j >= 0; i++, j--) {

}

Jest to nietypowa pętla for. Czy widzisz dlaczego?

Posiada ona dwie zmienne sterującezmienna sterującazmienne sterujące: i oraz j. Pozwala to na jednoczesne porównywanie liter danego słowa. Zmienna i startuje od pierwszego indeksu słowa i zwiększa się, natomiast zmienna j zaczyna od ostatniego i zmniejsza się. To w zasadzie jeden z najważniejszych aspektów w implementacji tego sposobu.

Wypełnijmy teraz blok tej pętli i dodajmy zmienną boolean czyPalindrom.

boolean czyPalindrom = false;

for (int i = 0, j = slowoTest.length() - 1; i < slowoTest.length() && j >= 0; i++, j--) {
	if (slowoTest.charAt(i) != slowoTest.charAt(j)) {
		czyPalindrom = false;
		break;
	} else {
		czyPalindrom = true;
	}
}

Dodaliśmy blok if-else, który w przypadku niewykrycia zgodności liter od razu przerywa pętlę (słowo kluczowe break). W przeciwnym razie, jeżeli po przejściu całej pętli, zmiennej logicznej czyPalindrom nie zostanie przypisana wartość false, to oznacza, że wprowadzone słowo na pewno jest palindromem.

Ostatnią częścią naszego programu będzie wypisanie użytkownikowi komunikatu tekstowego powiadamiającego, czy słowo jest palindromem, czy nie.

if (czyPalindrom == true) {
	System.out.println("Wyraz jest palindromem");
} else {
	System.out.println("Wyraz nie jest palindromem");
}

Zobaczmy teraz cały program.

import java.util.Scanner;

public class Palindrom {
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);

		System.out.println("Podaj słowo do sprawdzenia");

		String slowoTest = scanner.nextLine();
		boolean czyPalindrom = false;
		
		for (int i = 0, j = slowoTest.length() - 1; i = 0; i++, j--) {
			if (slowoTest.charAt(i) != slowoTest.charAt(j)) {
				czyPalindrom = false;
				break;
			} else {
				czyPalindrom = true;
			}
		}
		
		if (czyPalindrom == true) {
			System.out.println("Wyraz jest palindromem");
		} else {
			System.out.println("Wyraz nie jest palindromes");
		}
	}
}

Wersja z funkcją

Zobaczmy, jak wygląda cały program, ale napisany przy pomocy funkcji.

import java.util.Scanner;

public class Palindrom {
	public static boolean czyPalindrom(String slowo) {
		for (int i = 0, j = slowo.length() - 1; i < slowo.length() && j >= 0; i++, j--) {
			if (slowo.charAt(i) != slowo.charAt(j)) {
				return false;
			}
		}

		return true;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		System.out.println("Podaj słowo do sprawdzenia");

		String slowoTest = scanner.nextLine();

		if (czyPalindrom(slowoTest) == true) {
			System.out.println("Wyraz jest palindromem");
		} else {
			System.out.println("Wyraz nie jest palindromem");
		}
	}
}

Program napisany przy pomocy funkcji posiada więcej zalet w porównaniu do wcześniejszej implementacji. Niepotrzebna nam jest dodatkowa zmienna boolean czyPalindrom. Teraz cała funkcja zwraca typ logicznego boolean. Dodatkowo, gdybyśmy chcieli sprawdzić kilka słów, w poprzedniej implementacji musielibyśmy powielać ten sam kod – tu wystarczy wywołać jeszcze raz funkcję i przekazać sprawdzane słowo jako parametr.

II sposób

Drugi sposób polega na tym, że w nowej zmiennej zapisujemy słowo, które podamy do sprawdzenia – od tyłu. Jeżeli oba słowa są równe, to wyraz ten jest palindromem.

W następnej sekcji zaimplementujemy algorytm i dokładnie go omówimy.

Słownik