1. Definicja algorytmu
- Algorytm to jednoznaczny przepis obliczenia w skończonym czasie pewnych danych wejściowych do pewnych danych wynikowych.
Zgodnie z założeniem o jednoznaczności dla identycznego zestawu danych początkowych, algorytm zdefiniowany klasycznie zawsze zwróci identyczny wynik.
2. Rodzaje algorytmów
- algorytm liniowy
Algorytm liniowy to taki, w którym nie określono żadnych warunków. Jest też nazywany sekwencyjnym, gdyż każdy z kroków w tym algorytmie następuje sekwencyjnie, czyli wykonanie jednej sekwencji powoduje przejście bezpośrednio do następnej.
- algorytm warunkowy
Algorytm warunkowy to taki, w którym wykonanie instrukcji uzależnione jest od spełnienia lub niespełnienia warunku.
- algorytm iteracyjny
Algorytm z iteracją to taki, w którym trzeba wielokrotnie powtarzać instrukcję, aby warunek został spełniony.
- algorytm rekurencyjny
Algorytm rekurencyjny, algorytm, który wywołuje sam siebie do rozwiązania tego samego problemu.
3. Sposoby reprezentowania algorytmu
- lista kroków
Przykład:
Algorytm warunkowy w postaci listy kroków – obliczanie obwodu prostokąta
Dane: bok a i b
Lista kroków:
1.
Początek algorytmu
2.
Podaj bok a
3.
Podaj bok b
4.
Czy bok a>0?
jeśli tak idź do kroku 5,
jeśli nie podaj komunikat wyjściowy: "nie można obliczyć obwodu" i zakończ algorytm.
jeśli tak idź do kroku 5,
jeśli nie podaj komunikat wyjściowy: "nie można obliczyć obwodu" i zakończ algorytm.
5.
Czy bok b>0?
jeśli tak idź do kroku 6
jeśli nie podaj komunikat wyjściowy: "nie można obliczyć obwodu" i zakończ algorytm.
jeśli tak idź do kroku 6
jeśli nie podaj komunikat wyjściowy: "nie można obliczyć obwodu" i zakończ algorytm.
6.
Oblicz obwód Ob:=2*a+2*b
7.
Wyprowadź wartość Ob
6.
Koniec algorytmu
- schemat blokowy
Przykład:
Algorytm liniowy w postaci schematu blokowego – obliczanie obwodu prostokąta
- drzewa
- pseudokod
Pseudokodem nazywany jest taki sposób zapisu algorytmu, który, zachowując strukturę charakterystyczną dla kodu zapisanego w języku programowania, rezygnuje ze ścisłych reguł składniowych na rzecz prostoty i czytelności. Pseudokod nie zawiera szczegółów implementacyjnych (jak np. inicjalizacja zmiennych, alokacja pamięci), często też opuszcza się w nim opis działania podprocedur (jeśli powinien być on oczywisty dla czytelnika), zaś nietrywialne kroki algorytmu opisywane są z pomocą formuł matematycznych lub zdań w języku naturalnym.NWD(liczba całkowita a, liczba całkowita b)
dopóki b != 0
c := reszta z dzielenia a przez b
a := b
b := c
zwróć a
- kod właściwy
Przykład kodu właściwego algorytmu Floyda-Warshalla:this.path = path;
next = new int[len, len];
for (int i = 0; i < len; i++)
for (int j = 0; j < len; j++)
if (path[i, j] == INF)
next[i, j] = INF;
else
next[i, j] = i;
for (int k = 0; k < len; k++)
for (int i = 0; i < len; i++)
for (int j = 0; j < len; j++)
if (path[i, k] != INF && path[k, j] != INF &&
path[i, k] + path[k, j] < path[i, j])
{
path[i, j] = path[i, k] + path[k, j];
next[i, j] = k;
}
for (int i = 0; i < len; i++)
if (path[i, i] < 0)
throw new ArgumentException("Negative cycles");
