Palindrom

powrót

Zagadnienie to zostało już omówione w kategorii zadania>>tablice.

Link do zagadnienia jest tutaj.

W tym artykule przedstawię alternatywne rozwiązanie problemu.

Rozwiązanie rozpocznę od przykładu. Przeanalizujmy wyraz:

$$ALAMALA$$

Ustawię teraz dwa liczniki, jeden na pierwszej komórce w tablicy: 

$$ i = 0 $$

natomiast drugi na ostatniej komórce:

$$ j = strlen(tab) - 1$$

Pamiętajmy o tym, że komórki tablicy numerujemy od $$0$$, a funkcja strlen zwróci nam ilość liter w wyrazie. Żeby prawidłowo ustawić licznik $$j$$ na ostatnim znaku w tablicy, należy odjąć $$1$$ od ilości liter ciągu.

Następnie poruszamy się licznikami w stronę środka wyrazu: licznikiem $$i$$ w prawą stronę natomiast licznikiem $$j$$ w lewą stronę porównując na bieżąco kolejne znaki. Jeśli jakaś para nie będzie sobie równa, oznacza to, że wyraz nie jest palindromem. Gdy liczniki spotkają się na środku i wszystkie pary będą zgodne to mamy palindrom.

Dla powyższego wyrazu mamy palindrom. Przeanalizujmy ten przypadek.

W następnej iteracji liczników spowoduje nieprawdziwość warunku $$i<j$$ - dalej nie musimy sprawdzać. Przeanalizujmy jeszcze jeden przypadek dla wyrazu

$$BCDSCB$$

Tu natomiast widzimy, że w ostatniej iteracji para liter D i S jest niezgodna, a więc wryaz nie jest palindromem.

 Rozwiązanie:

#include<iostream>
#include<cstring>
using namespace std;

bool czy_palindrom(char tab[])
{
	//ustawiam liczniki "i" i "j" na pierwszy i ostatni znak wyrazu tab 
	int i=0, j = strlen(tab)-1; //pamiętajmy, że indeksujemy tablicę od 0
	
	while(i<j) //pętla wykonuje się do momentu spotkania liczników
	{
		if(tab[i]!=tab[j]) //gdy znaki nie będą się zgadzać, to wyraz nie jest palindromem
			return false;
		
		++i; //przejscie do następnej litery idąc w prawą stronę
		--j; //przejscie do poprzedniej litry idąc w lewą stronę
	}
	
	return true; //wyraz jest palindromem
}

int main()
{
	char tab[100];
	cout<<"Podaj wyraz: ";
	cin>>tab;
	
	if(czy_palindrom(tab)) //lub if(czy_palindrom(tab)==true) lub if(czy_palindrom(tab)==1)
		cout<<"Wyraz "<<tab<<" jest palindromem"<<endl;
	else
		cout<<"Wyraz "<<tab<<" nie jest palindromem"<<endl;
	
	return 0;
}