Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

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.

Wartość $$i$$ Wartość $$j$$ Litera na i-tej pozycji Litera na j-tej pozycji Status
$$i=0$$ $$j=6$$ A A ok
$$i=1$$ $$j=5$$ L L ok
$$i=2$$ $$j=4$$ A A ok

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

$$BCDSCB$$

Wartość $$i$$ Wartość $$j$$ Litera na i-tej pozycji Litera na j-tej pozycji Status
$$i=0$$ $$j=5$$ B B ok
$$i=1$$ $$j=4$$ C C ok
$$i=2$$ $$j=3$$ D S źle

Tu natomiast widzimy, że w ostatniej iteracji para liter 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;
}