Metoda zstępująca

Projektowanie algorytmów – zgodne z metodą zstępującą – polega na rozbijaniu głównego problemu na mniejsze podproblemy. Zanim zaczniemy pisać kod, powinniśmy dokładnie wiedzieć, jakich funkcjonalności potrzebujemy i w jaki sposób mają one ze sobą współdziałać.

Dla lepszego zrozumienia tej koncepcji przeanalizujmy przykład rekurencyjnej metody obliczania wartości elementu ciągu Fibonacciego o indeksie n (więcej informacji o tym zagadnieniu znajdziesz w e‑materiale Ciąg FibonacciegoPMu9Wf5p9Ciąg Fibonacciego).

By obliczyć wartość elementu o indeksie n, najpierw ustalamy wartość elementu o indeksie n - 1 itd.

Na ilustracji zaprezentowano przykład obliczania elementu ciągu Fibonacciego o indeksie 5.

R1aysrpZyBaBW

Drzewo wywołań rekurencyjnych.
1: F5, 2: strzałka w lewo: F4. 3: Strzałka w prawo: F2, 4: strzałka w prawo: F0, 5: strzałka w lewo: F1, 2: strzałka w lewo F3, 3: strzałka w prawo F1, 3: strzałka w lewo: F2, 4: strzałka w lewo: f1, 4: strzałka w prawo: F0.
2: strzałka w prawo: F3, 3: strzałka wprawo: F1, 3: strzałka w lewo: F2, 4: strzałka w lewo: F1, 4: strzałka w prawo F0.

Rozbijając każdy z kroków w taki sposób, przechodzimy do coraz bardziej podstawowych czynności. Postępujemy tak, dopóki nie dojdziemy do bardzo elementarnych operacji, których już nie jesteśmy w stanie podzielić.

Ten sposób projektowania algorytmów jest dosyć czasochłonny, ponieważ każdy krok powinien być dokładnie zaplanowany i przeanalizowany. Błąd w którymkolwiek kroku powoduje wystąpienie dalszych błędów na niższych poziomach. Należy również przemyśleć algorytm pod względem liczby rozwiązywanych podproblemów. Jeżeli będziemy wykonywać zbyt wiele operacji, złożoność algorytmu znacznie wzrośnie. Plusem tego sposobu jest intuicyjność kolejnych kroków algorytmu.

Metoda wstępująca

Jak sugeruje nazwa, tym razem będziemy tworzyć rozwiązanie, zaczynając od podstawowych funkcjonalności. Metoda ta polega na łączeniu oraz budowaniu zależności pomiędzy elementarnymi funkcjami. Nadajemy w ten sposób kształt coraz to bardziej skomplikowanym i zaawansowanym strukturom, aż dojdziemy do kompletnego programu rozwiązującego problem.

W przypadku obliczenia elementu ciągu Fibonacciego o indeksie 5 zaczynamy od obliczenia pierwszego elementu ciągu Fibonacciego – czyli elementu o indeksie 0 (n = 0). Następnie wykorzystujemy znajomość elementu o indeksie 0 do obliczenia elementu o indeksie 1 (n + 1) itd.

Inną analogią dla tej metody jest stawianie budowli z klocków. Do klocków możemy porównać elementarne i niezależne od siebie funkcje. Nie powstały one z myślą o konkretnych projektach, dzięki czemu są uniwersalne. Mając je do dyspozycji, jesteśmy w stanie zbudować różnorodne konstrukcje, dowolnie łącząc elementy w całość.

R4Tg3Vq6E9wCA

Grafika przedstawia konstruowanie figury z innych figur. Na samym dole znajdują się cztery trójkąty – dwa duże pomarańczowe oraz dwa małe fioletowe. Małe trójkąty łączą się w prostokąt, obok którego znajdują się kolejne dwa małe trójkąty. Te trójkąty łączą się w fioletowy trapez. Czerwone trójkąty łączą się w kwadrat, obok którego pojawia się turkusowy trójkąt. Trzy figury, trapez, trójkąt i kwadrat znowu się łączą tak, że kwadrat jednym bokiem łączy się z dłuższą podstawą trapezu, a drugim bokiem z jedną z przyprostokątnych trójkąta.

Przedstawiony schemat pokazuje, jak działa metoda wstępująca. Na najniższym poziomie mamy najbardziej podstawowe elementy, które łączymy w coraz bardziej skomplikowane systemy. Na najwyższym poziomie znajduje się cały gotowy system, złożony z elementów, które mieliśmy do dyspozycji na początku.

Paradygmatem programowaniaparadygmat programowaniaParadygmatem programowania korzystającym z metody wstępującej jest programowanie obiektowe.

Wady i zalety

W przypadku metody zstępującej jej największą wadą jest czas potrzebny do rozbicia problemu na mniejsze podproblemy. Kolejnym minusem jest brak możliwości przetestowania napisanego programu, dopóki nie powstanie jego większa część. Natomiast bardzo dużym plusem jest dokładne rozpatrzenie problemu i nabycie pewności, że wszystko, co implementujemy, ma cel oraz znajduje zastosowanie. Kolejnym plusem jest to, że niektóre podproblemy mogą okazać się wielokrotnego użytku – ich rozwiązań możemy użyć w więcej niż jednym miejscu, co pozwala zaoszczędzić czas.

Metoda wstępująca pozwala na wygodną przebudowę istniejących rozwiązań. Dodawanie nowych funkcji do istniejącego programu jest proste i nie wymaga edytowania całego kodu, co często ma miejsce w przypadku metody zstępującej. Kolejną zaletą jest łatwe testowanie poszczególnych obiektów w pisanym kodzie, ponieważ z założenia są one od siebie niezależne. Wadą takiego podejścia jest, że z początku może być ono bardzo chaotyczne. Bez dogłębnej analizy problemu nie jesteśmy w stanie stwierdzić, czego tak naprawdę potrzebujemy. Bardzo często zaczynamy zdawać sobie z tego sprawę wraz z pisaniem kodu.

W praktyce metody zstępującej używamy w językach strukturalnych takich jak np. C czy Fortran, natomiast metody wstępującej w językach obiektowych, np. Java czy C++.

Słownik