Opole, dn. 7 listopada 2005

Laboratorium Algorytmów i Struktur Danych

Temat:

Analiza algorytmu sprawdzania czy dany łańcuch jest palindromem

Autor: Dawid Najgiebauer

Informatyka, sem. II, grupa lab. 11

Prowadzący: dr inż. Jan Sadecki

1. Temat

Sprawdzić rekurencyjnie, czy podany łańcuch tekstowy jest palindromem (wygląda identycznie czytany od przodu i od tyłu, np. "kajak" lub "kobyła ma mały bok").

2. Analiza, projektowanie

Celem badania jest wykonanie algorytmu porównania, czy dany łańcuch tekstowy jest palindromem.

1. Porównywanie

Algorytm opierać się będzie na porównywaniu kolejnych znaków z badanego łańcucha pierwszy z ostatnim, drugi z przedostatnim itd., aż do momentu, gdy zostanie stwierdzona rozbieżność lub do momentu „dojścia” w ten sposób do środka badanego ciągu tekstowego.

Dodatkowymi założeniami są, iż wielkość liter nie ma znaczenia oraz wszystkie spacje będą ignorowane.

2. Implementacja algorytmu

int sprawdz(char *str, int start)

{

int koniec=strlen(str)-start-1;

while((start<koniec)&&(str[start]==' ')) start++;

while((start<koniec)&&(str[koniec]==' ')) koniec--;

if (start>=koniec) return 1;

if (str[start]!=str[koniec]) return 0;

else return sprawdz(str,start+1);

}

3. Wyniki i wnioski z badania

Dzięki zastosowaniu rekurencji w łatwy sposób możliwe było uzyskanie wypisywania liczby w postaci binarnej, gdzie pierwszą cyfrę tej liczby poznajemy dopiero przy ostatnim dzieleniu, drugą - przy przedostatnim itd.

4 Dawid Najgiebauer

Temat 5

Temat 3

równe

różne

sprawdz(str,start+1)

N

T

str[start]!=str[koniec]

N

T

start≥koniec

N

koniec--

T

N

start++

T

(start<koniec) i (str[start]==' ')

koniec=strlen(str)-start-1

Sprawdz(char *str, int start)

(start<koniec) i (str[koniec]==' ')

---