Laboratorium Podstaw Informatyki
Kierunek Elektrotechnika
Ćwiczenie 3.3
Algorytmy iteracyjne i rekurencyjne
Zakład Metrologii AGH
Kraków 1997
Wprowadzenie
Iteracyjny sposób przetwarzania danych polega na stosowaniu bloku instrukcji zorganizowanych w pętlę programową do kolejnych danych. W sposobie rekurencyjnym w wykonywanej funkcji istnieje wywołanie tej samej funkcji dla innych lub tych samych danych. Dla zapewnienia zakończenia ciągu wywołań funkcja jest wołana w instrukcji warunkowej. Parametry działania bloku instrukcji i koniec jego wykonywania w przypadku iteracyjnym określa instrukcja pętli programowej (np. for lub while). W przypadku rekurencyjnym określa je sam blok instrukcji zawarty w funkcji rekurencyjnej.
Przykładem porównania zasady iteracji i rekurencji może być proces zbierania informacji w środowisku ludzi z określoną hierarchią. Przypuśćmy, że dyrektor przedsiębiorstwa zleca swojej sekretarce policzenie pracowników lubiących kiełbaski i piwo (chce poprawić stosunki z pracownikami przez zorganizowanie ogniska, ale nie chce narażać się na zbyt duże koszty). Sekretarka działająca w sposób iteracyjny, dla której zatrudnione osoby są niezwiązanym wewnętrznie zbiorowiskiem ludzi, skomunikuje się z każdym z pracowników i zapyta go o jego preferencje konsumpcyjne związane z ogniskiem. Ta potrafiąca wykorzystać istniejące powiązania między pracownikami, zsumuje liczby uzyskane przez zlecenie policzenia ww. osób w każdym pionie przedsiębiorstwa sekretarkom w odpowiednich pionach. Te z kolei otrzymają liczby od sekretarek w odpowiednich działach. Proces zapytań/odpowiedzi zakończy się wtedy, gdy na ostatnim poziomie hierarchii przedsiębiorstwa ostatni pracownik udzieli odpowiedzi na pytanie kierownika zespołu, wszyscy kierownicy przekażą odpowiednie liczby w górę hierarchii, a te, sumowane przez sekretarki, trafią do dyrektora przedsiębiorstwa. Jakościowa różnica w zmianie organizacji procesu zbierania informacji ma swój skutek w ilości danych przetwarzanych przez daną sekretarkę. Przyspieszenie przeprowadzenia całej operacji nie wynika z własności rekurencji, a z jednoczesnego (równoległego) wykonywania zadania w pionach, poziomach i zespołach. W wyniku stosowania rekurencji nie należy oczekiwać przyspieszenia wykonania programu (choć są wyjątki), a jedynie, w określonych przypadkach, uproszczenia kodu źródłowego i schematu przetwarzania danych.
Zastosowania
Nieprzypadkowa jest struktura hierarchiczna występująca w przedstawionym przykładzie. Algorytmy rekurencyjne mają najbardziej naturalne zastosowanie w przypadku przetwarzania danych uporządkowanych hierarchicznie w postać struktur dynamicznych. Związane jest to z problemami iteracyjnej implementacji algorytmów grafowych, wymagającej pomocniczych struktur danych. Implementacja rekurencyjna ogranicza ilość widzianych węzłów w danym wywołaniu do ilości bezpośrednich sąsiadów aktualnego węzła.
Również wielkości matematyczne zdefiniowane rekurencyjnie, jak np. silnia czy liczby Fibonnaciego, w sposób naturalny koduje się rekurencyjnie. W większości takich przypadków podejście iteracyjne jest możliwe, ale daje mniej czytelny kod programu.
Zadanie 1 - algorytmy wyznaczania silni
Wg. [Bronsztejn, Siemiendiajew]:
„Silnią n! liczby naturalnej n nazywamy iloczyn 1⋅2⋅...⋅n. Iloczyn ten można też zapisać krótko w postaci: . Przyjmuje się ponadto, że 1!=1 i 0!=1.
Podstawowa własność silni: n!=n⋅(n-1)!”
W zależności od wykorzystywanej przez algorytm zależności, możliwa jest realizacja iteracyjna lub rekurencyjna.
Algorytm rekurencyjny
Wersja rekurencyjna funkcji obliczania silni korzysta z jej podstawowej własności n!=n⋅(n-1)! i założenia o wartości silni dla liczby 0.
Opracuj rekurencyjnie wywoływaną funkcję obliczania wartości silni dla danej liczby. Deklaracja funkcji ma postać: int silnia(int n); Testuj wartość przekazanej parametrem liczby - silnia jest zdefiniowana tylko dla liczb naturalnych i zera. Dla błędnej wartości parametru zwróć wartość -1. Warunkiem zakończenia ciągu wywołań rekurencyjnych jest wartość parametru równa zero. Przetestuj opracowaną funkcję przez kompilację z funkcją main() programu silnia. |
Algorytm iteracyjny
Algorytm iteracyjny wyznaczania silni wykorzystuje definicję n!=1⋅2⋅...⋅n, oraz założenie o wartości silni dla liczby 0.
Opracuj iteracyjną wersję funkcji obliczania wartości silni dla danej liczby. Deklaracja funkcji ma postać: int silnia(int n); Testuj wartość przekazanej parametrem liczby - silnia jest zdefiniowana tylko dla liczb naturalnych i zera. Dla błędnej wartości parametru zwróć wartość -1. Przetestuj opracowaną funkcję przez kompilację z funkcją main() programu silnia. |
Zadanie 2 - algorytmy dla struktur dynamicznych
Jak napisano we wprowadzeniu, algorytmy rekurencyjne mają naturalne zastosowanie w przypadku danych opisanych w strukturze dynamicznej. Ich siła ujawnia się przy ilości dowiązań w węźle struktury większej od 1. Decydują o niej zdolność do powrotu w miejsce wywołania po przejściu dowolnej ścieżki i tworzone ciągi wywołań rekurencyjnych dla każdej ze ścieżek wychodzących z danego węzła. Dzięki tym własnościom większość algorytmów rekurencyjnych dla struktur dynamicznych obywa się bez dodatkowych struktur danych tam, gdzie algorytmy iteracyjne ich wymagają.
Drukowanie struktury drzewa
Dynamiczna struktura binarnego drzewa uporządkowanego może być wykorzystana do rozwiązania zadania sortowania. Dla danego nieposortowanego ciągu liczb tworzymy strukturę drzewa wg. następujących zasad. Jeśli drzewo jest puste, to pierwszy element ciągu tworzy korzeń drzewa. Jeśli drzewo jest niepuste, to podążamy ścieżką wybraną w wyniku porównania wartości liczby z liczbą w danym węźle. Jeśli liczba z ciągu jest mniejsza to wybieramy lewe dowiązanie, w przeciwnym wypadku prawe. Jeśli wybrane dowiązanie jest puste to tworzymy nowy element, dowiązujemy go przez wybrane dowiązanie i wpisujemy wartość liczby z ciągu do elementu.
Program dsort realizuje sortowanie zbioru liczb typu int wg. opisanego algorytmu. Brak w tym programie zachowywania posortowanego ciągu liczb w oryginalnej tablicy liczb. Wypełnij funkcję ZachowajDane(EL_DRZEWA* WezelDrzewa, int Tablica[], short Jak) wypisującą na ekranie posortowany ciąg liczb i zachowującą go w tablicy Tab. W zależności od wartości parametru jak, zachowaj i wypisz liczby w porządku od najmniejszej do największej (jak == NATURAL) lub w odwrotnej (jak == ODWROT). Przy wypisywaniu liczb zaznacz wcięciem, numerem poziomu, lub w inny sposób, położenie w drzewie węzła zawierającego liczbę. |
Efektywność podanego algorytmu sortowania jest silnie zależna od sortowanego ciągu. W najlepszym przypadku wymaga maksymalnie log2N porównań kluczy. W najgorszym przypadku wymaga N porównań. Dodatkowy koszt to tworzenie elementów struktury dynamicznej i przenoszenie danych ze struktury drzewa do tablicy. Metoda sortowania stogowego [Wirth] realizuje zmodyfikowany algorytm sortowania drzewiastego, operujący na tablicowej reprezentacji drzewa i wykorzystujący operacje przenoszenia elementów. Złożoność tej metody, nawet w najgorszym przypadku, jest rzędu N⋅log2N operacji.
Przeszukiwanie grafu acyklicznego
Zadanie przeszukania grafu jest jednoznaczne z zadaniem dotarcia dokładnie raz do każdego węzła w grafie. W przypadku grafu zawierającego cykle (zamknięte ścieżki) nie jest to zadanie trywialne. Nawet z użyciem rekurencji wymaga dodatkowej struktury danych opisującej węzły już odwiedzone. Przypadek grafu acyklicznego sprowadza się do prostego rekurencyjnego przechodzenia ścieżek.
Program rzeki zawiera grafowy opis polskich rzek należących do zlewni Bałtyku. Element podstawowy (węzeł grafu) zawiera nazwę rzeki i dowiązanie do listy jej bezpośrednich dopływów. Jest to graf acykliczny. Wypełnij rekurencyjną funkcję WypiszRzeki(RZEKA* rzeka, char* wzorNazwy, int wciecie) wypisującą na ekranie wszystkie nazwy rzek o początkowej części nazwy wzorNazwy. Wcięciem zaznacz hierarchię dopływów. Pusty wzorzec oznacza brak wzorca. Zastosuj opracowaną funkcję dla pustego wzorca i dla wzorca „W”. |
Przeszukiwanie grafu cyklicznego jest tematem zadania dodatkowego.
Zadanie 3 - szybkie sortowanie
Proste algorytmy sortowania typu proste wybieranie czy algorytm bąbelkowy są kosztowne. Wymagają rzędu N2 operacji typu porównanie lub przesunięcie. Algorytm szybkiego sortowania wynaleziony przez C. A. Hoare'a wymaga rzędu N⋅log2N operacji. Jednak, jak pisze Wirth, „sortowanie oparte na metodzie sortowania szybkiego jest pewnego rodzaju loterią, na której można dużo stracić, jeżeli nie będzie się miało dużo szczęścia”.
Metoda QuickSort opiera się na porządkowaniu sortowanego zbioru danych w dwóch podzbiorach. Pierwszy zawiera elementy o kluczu mniejszym od wybranego, zwanego kluczem granicznym, drugi zawiera elementy o kluczu mniejszym. Powyższa procedura jest następnie powtarzana dla podzbiorów, aż do uzyskania podzbiorów jednoelementowych. Kluczem do osiągnięcia dużej szybkości sortowania jest równomierny podział na podzbiory, co można osiągnąć przez odpowiedni wybór klucza granicznego. Nie jest to zadanie trywialne. Najczęściej stosuje się losowy wybór klucza, lub algorytm znajdowania mediany opracowany przez A. C. Hoare'a.
W najgorszym przypadku wyboru klucza granicznego, kiedy w każdym kroku jeden z podzbiorów jest jednoelementowy, algorytm szybkiego sortowania wymaga rzędu N2 operacji, podobnie jak algorytmy proste.
QuickSort - algorytm rekurencyjny
Ze względu na powtarzanie tego samego procesu podziału zbioru danych na dwa podzbiory wg. zadanego algorytmu, naturalną jest stosowanie w tym przypadku rekurencji. Algorytm iteracyjny daje bardziej złożony kod programu i wymaga dodatkowej struktury danych (stosu) do pamiętania podzbiorów do posortowania.
Algorytm szybkiego sortowania można opisać następująco:
1. Wybierz klucz graniczny dla zbioru danych.
2. Podziel zbiór danych na dwa podzbiory elementów o kluczach mniejszych i większych od granicznego.
3. Powtórz punkty 1, 2, 3 dla utworzonych podzbiorów, jeśli zawierają więcej niż jeden element.
Dla danych do posortowania zawartych w tablicy, podział na podzbiory można zrealizować przez wyszukanie elementu o kluczu większym od granicznego począwszy od początku tabeli, wyszukanie elementu o kluczu mniejszym od graniczego od końca tabeli i wymianę wartości elementów. Sygnałem zakończenia procesu podziału jest zrównanie się indeksów wyszukiwania od początku i końca tabeli. W tym momencie w lewej części tabeli są elementy o kluczu równym lub mniejszym od granicznego, a w prawej elementy o kluczu równym lub większym od granicznego.
Opracuj rekurencyjnie wywoływaną funkcję sortowania tablicy liczb zmiennoprzecinkowych typu double wg. algorytmu QuickSort. Za element graniczny przyjmuj element środkowy z sortowanego przedziału tabeli. Wygeneruj tablicę 20 zmiennoprzecinkowych liczb losowych i przetestuj na niej działanie funkcji. Porównaj swoją implementację z kodem programu w książce „Algorytmy + struktury danych=programy” [Wirth]. |
Dla tych, którzy chcą wiedzieć więcej - informacje dodatkowe
Ograniczenia rekurencji
Rekurencja jest metodą wykorzystującą stos do przekazywania parametrów wywołania funkcji i adresów powrotu. Ze względu na zagłębiający schemat wywołania z powrotem po zakończeniu ścieżki wywołań, rekurencja jest ograniczona wielkością pamięci przeznaczonej na stos. W segmentowanej architekturze PC stos, łącznie ze stertą i danymi statycznymi, zajmuje maksymalnie 64 kB. Domyślny rozmiar stosu wynosi kilka kB, zależnie od typu kompilatora.
Przykład błędnego wykorzystania rekurencji, przy poprawności składniowej kodu, przedstawia funkcja interakcji z użytkownikiem fikcyjnego programu (np. wspomagania nawigacji na morzu).
void ObslugaPozycji(POZYCJA ostatniaPozycja) {
POZYCJA pozycja=PobraniePozycji(ostatniaPozycja);
if(CzyZakonczycWyborPozycji(pozycja))
ZakończenieWyboruPozycji(pozycja);
else {
ReakcjaNaWyborPozycji(pozycja);
ObslugaPozycji(pozycja); /* Wywolanie rekurencyjne */
}
return;
}
Błąd tkwi w pozostawieniu użytkownikowi decyzji o przerwaniu ciągu wywołań rekurencyjnych. Nie potrafimy w takim przypadku przewidzieć ilości wyborów pozycji do obsłużenia, w programie nie ma również ograniczenia tej ilości. W przypadku kompilatora firmy Microsoft, umieszczającego stos nad danymi statycznymi i pod stertą, w momencie przekroczenia granicy stosu zostaną zniszczone dane statyczne (stos w komputerach z procesorami typu 80x86 przyrasta w kierunku niższych adresów).
Sekwencja wywołania funkcji w języku C na poziomie kodu maszynowego
Elementem różniącym kody wykonywalne generowane kompilatorami poszczególnych języków programowania jest m. in. konwencja przekazywania parametrów do funkcji. W języku C przyjęto zasadę umieszczania parametrów na stosie w kolejności od ostatniego do pierwszego. Zdejmowanie parametrów wywołania ze stosu to zadanie funkcji wywołującej. Dla przykładowego wywołania funkcji z podaną deklaracją:
int funkcja(int parametr1, parametr2);
funkcja(1, 2);
sekwencja rozkazów asemblerowych wywołania funkcji po kompilacji w środowisku Visual C/C++ ma postać:
PUSH 02
PUSH 01
CALL funkcja
ADD SP, 04
Poza parametrami wywołania, na stosie jest również umieszczany adres powrotu do funkcji wywołującej. Operacja ta jest wykonywana przez procesor w momencie napotkania rozkazu CALL. Adres może być dwubajtowy dla wywołania bliskiego lub czterobajtowy dla wywołania dalekiego. Adres powrotu jest ładowany do licznika rozkazów (IP) w momencie wykonania rozkazu RET powrotu z funkcji. Wynik działania funkcji typu int jest zawsze przekazywany w akumulatorze. Dane o większych rozmiarach są przekazywane w innych, określonych rejestrach, lub w pamięci wskazywanej przez określone rejestry.
Dla tych, którzy chcą być najlepsi - zadania dodatkowe
Iteracyjna wersja algorytmu Quick-Sort
Opracuj wersję iteracyjną tego algorytmu sortowania. Sortowanymi elementami będą pary liczb zmiennoprzecinkowych (X, Y), zawarte w N-elementowej tablicy. Celem sortowania jest uzyskanie narastających wartości X. Porównaj swoją implementację z implementacją zawartą w pozycji [Wirth]. |
Sprawdzanie acykliczności grafu skierowanego
Sprawdzenie acykliczności grafu można uważać za szczególny przypadek przeszukiwania grafu cyklicznego [Lipski]. Podobnie jak w tym algorytmie, konieczne jest utworzenie pomocniczej struktury danych opisującej węzły już odwiedzone na danej ścieżce. Napotkanie w czasie przeszukiwania węzła już odwiedzonego oznacza istnienie cyklu w grafie.
W tym zadaniu tropić będziemy afery gospodarcze. Struktura grafu skierowanego opisywać ma transakcje między firmami. Węzeł jest przeznaczony na opis firmy, powiązanie na opis przedmiotu transakcji. Jest to graf skierowany i może zawierać cykle. Wykrywanym procederem jest sprzedaż towarów przez firmę dla siebie, również przez pośredników. Zakładamy tylko jeden rodzaj towaru sprzedawanego w jednostkowej ilości. Zdefiniuj typ dla węzła i połączenia grafu. Zbuduj przykładową strukturę dynamiczną, graf transakcji zawierający cykle, czyli poszukiwane zamknięte transakcje łańcuchowe. Opracuj funkcję sprawdzania acykliczności grafu. W razie napotkania transakcji zamkniętej funkcja powinna wypisać nazwę firmy na początku cyklu. Przetestuj działanie opracowanej funkcji. |
Moduł analizy posunięć w grze w warcaby
Hipotetyczny program do interakcyjnej gry w warcaby jest zbudowany z trzech modułów: interfejsu z użytkownikiem, generowania ruchów i analizy sytuacji. Moduł interfejsu z użytkownikiem jest odpowiedzialny za przedstawianie graczowi sytuacji w grze i za pobieranie ruchów gracza. Opracowywanie ruchów komputera dokonuje się w module generowania możliwych ruchów. Każda sytuacja na planszy po serii N posunięć jest analizowana funkcją z modułu analizy sytuacji. Przyjmowany do wykonania jest pierwszy ruch serii, która otrzymała najwyższą ocenę w wyniku analizy.
Zajmiemy się modułem generowania ruchów na planszy gry w warcaby. Generowanie N posunięć pionkami można zaimplementować schematem rekurencyjnym. Jedno wywołanie funkcji wykonuje wszystkie dopuszczalne ruchy pionkiem wskazanym przez parametr i woła rekurencyjnie tę samą funkcję dla wszystkich pionków na planszy. Konieczne jest przy tym pamiętanie ruchów wykonanych w danym ciągu wywołań rekurencyjnych. Po N wywołaniach wołana jest funkcja analizy sytuacji i wynik analizy jest porównywany z najlepszym dotąd osiągniętym. Jeśli uzyskano lepszy wynik, to zachowywana jest nowa najlepsza seria ruchów. Opracuj moduł generowania ruchów wg. opisanych zasad. Przyjmij głębokość wywołań rekurencyjnych (ilość ruchów w serii) równą 3. Przetestuj działanie modułu przez pokazywanie sytuacji na planszy po każdym generowanym ruchu. |
Literatura
Bronsztejn I. N., Siemiendiajew K. A.: Matematyka. Poradnik encyklopedyczny; PWN, Warszawa 1995
Kernighan B. W., Ritchie D. M.: Język C; WNT, Warszawa 1988
Lipski W.: Kombinatoryka dla programistów; WNT, Warszawa 1989
Wirth N.: Algorytmy + Struktury Danych = Programy; WNT, Warszawa 1989