Spis treści
Rodzaje algorytmów:
- algorytmy sekwencyjne, czyli z nierozgałęzioną linią przebiegu aktywności programu,
- algorytmy warunkowe, czyli algorytmy z rozgałęzieniami linii przebiegu aktywności,
- algorytmy iteracyjne, czyli algorytmy z pętlą, inaczej algorytmy cykliczne,
- algorytmy rekurencyjne, czyli algorytmy samo-zagnieżdżające się.
Algorytmy sekwencyjne – liniowe
Algorytm sekwencyjny to algorytm mający prostą liniową postać. Składa się z ciągu instrukcji, które są wykonywane jedna po drugiej w kolejności, jaka wynika z ich następstwa w zapisie algorytmu.
Algorytmy sekwencyjne mają opisy składające się z kroków, które nie zależą od żadnych warunków i są wykonywane w zapisanej kolejności.
Istnieją jednak sytuacje, w których postępowanie w algorytmie zależy od spełnienia, bądź nie, określonych warunków. Czasami też np. musimy powtórzyć pewne kroki algorytmu kilka razy. Powoduje to konieczność użycia narzędzi programistycznych takich jak warunek czy pętla.
Algorytmy warunkowe (algorytm rozgałęziony)
Kolejny rodzaj algorytmów to algorytmy warunkowe, zwane inaczej algorytmami rozgałęzionymi.
W rzeczywistości, większość algorytmów nie jest sekwencyjna, ma bardziej rozbudowaną strukturę. Często występują w nich instrukcje, których wykonanie uzależnione jest od spełnienia pewnego warunku lub też spełnienie pewnego warunku powoduje wykonanie jednej instrukcji, a niespełnienie go innej. Taką instrukcję nazywamy instrukcją warunkową.
Na powyższym przykładzie mamy algorytm sprawdzania czy dana liczba jest liczbą parzystą. Realizowane jest to poprzez sprawdzenie czy dzielenie całkowite danej liczby przez 2 jest równe jej dzieleniu bezwzględnemu przez 2. Jeśli wynik tych dwu działań jest równy to liczba badana musi być liczbą parzystą (w przeciwnym wypadku wynikiem dzielenia bezwzględnego będzie niecałkowita liczba rzeczywista, która przez oczywistość jest nierówna innej liczbie całkowitej).
Algorytm iteracyjny, inaczej algorytm cykliczny lub algorytm z pętlą.
Wielokrotne powtarzanie niektórych instrukcji jest cechą charakterystyczną wielu algorytmów, jednak nie zawsze (tak jak w tym algorytmie) możemy określić dokładnie liczbę powtórzeń. Może ona zależeć od spełnienia pewnych warunków. Wielokrotne powtarzanie instrukcji umożliwiają instrukcje iteracyjne (pętle) . Działa ona według schematu:
Wykonuj instrukcję „Czekaj 1s” dokładnie A razy.
Algorytm rekurencyjny
W informatyce możemy realizować również szczególny rodzaj powtórzeń bez konieczności stosowania pętli. Jest to technika rekurencji, czyli samo-zagnieżdżania programu. Polega to na tym, że algorytm oblicza część założonego równania, a obliczone wyniki stają się niejaka danymi źródłowymi dla kolejnej iteracji tego samego algorytmu. Dopóki istnieje warunek spełniający potrzebę ponownych uruchomień algorytmu, są uruchamiane kolejne instancje tego algorytmu, każda obliczając częściowe wyniki, aż do wyczerpania (niespełnienia warunku) potrzeby iteracji. Po ostatniej iteracji następuje kaskadowe zakończenie iteracji poprzednich, aż do zakończenia pierwotnej instancji programu.
Algorytmy rekurencyjne mają swoją zaletę – prostotę i czytelność kodu. Całą pracę związaną z przygotowaniem środowiska do pracy „zrzucają” na automatykę oprogramowania środowiska pracy programu. Stanowią też istotne zagrożenie dla poprawnego funkcjonowania systemu komputerowego. Źle napisany warunek końca samo-zagnieżdżania może doprowadzić do zapętlenia zagnieżdżania i w efekcie nieskończonego „wchodzenia” w coraz głębsze uruchamiania algorytmu. Program się nigdy nie skończy, ale też każde zagnieżdżenie powoduje zajęcie pewnych zasobów komputera i doprowadzi do ich wyczerpania, co z kolei spowoduje nieprawidłową pracę programu i/lub komputera (obecne systemy operacyjne mają zabezpieczenie w postaci pamięci chronionej i wydzielanie programowi uruchamianemu ściśle określonych zasobów, co przy ich wyczerpaniu powinno mieć wpływ tylko na program uruchamiany, a nie całe środowisko).
Zadanie do samodzielnego wykonania: Przygotuj (wymyśl) po 4 różne przykłady algorytmów dla każdego z 3 pierwszych rodzajów algorytmów. Dla algorytmu rekurencyjnego spróbuj znaleźć jeden inny przykład.