Jak pisać algorytmy

Definicja

Algorytm jest to zbiór czynności, który pozwala osiągnąć cel. Głównym zadaniem algorytmu jest przekształcić dane wejściowe na końcowe dane. Wszystko jest wykonywane w skończonej liczbie kroków. Ten sam problem można rozwiązywać na wiele różnych sposobów. Czasami nie można stwierdzić, które rozwiązanie jest najlepsze dopóki nie zostaną określone dodatkowe założenia.

Rozwiązywanie zadania

Specyfikacja

Przed przystąpieniem do zadania należy określić cel jaki chcemy osiągnąć. Składają się na to dane wejściowe oraz dane wyjściowe. W tym kroku należy określić w jakiego typu zmiennych będą przechowywane dane. Można też się zastanowić czy nie istnieję lepsze typy zmiennych od zazwyczaj używanych (przykładowo w C++ dla liczby naturalnej użyć nie int, a unsigned int).

Poszukiwanie rozwiązania

Drugi krok polega na poszukiwaniu algorytmu, który będzie dokładnie wykonywał kroki określone w specyfikacji. Pierwszy szkic algorytmu nie musi być optymalny. Jednak należy pamiętać, aby na tym etapie zastanowić się czy nie istnieje szansa, aby niektóre kroki pominąć, albo wykonać je w inny sposób. Ten proces nazywany jest wyborem odpowiedniego algorytmu. Oczywiście należy już na tym etapie wiedzieć ile algorytm będzie miał do dyspozycji pamięci RAM czy jaki procesor. Często istnieje możliwość optymalizacji, że wykonywany program zużyje mało pamięci kosztem czasu, albo odwrotnie.

Pseudokod

Trzeci krok polega na zapisaniu swoich przemyśleń z poprzedniego kroku w wybranej formie. Nie musi to być od razu kod ostateczny. Może to być lista kroków, zwykły opis słowny, schemat blokowy algorytmu, programu lub w jakikolwiek inny sposób. Chodzi o to, żeby mieć po tym kroku prócz jasno określonego celu wstępną wersją algorytm. Można też użyć formy mieszanej tj. niektóre fragmenty np. w schemacie blokowym zacząć zapisywać używając zapisu w wybranym języku programowania.

Dowód poprawności

Rozpisane rozwiązanie może nie działać dla niektórych zestawów danych, dlatego należy dokonać analizy i dowodu poprawności algorytmu. Jeśli algorytm radzi sobie ze wszystkimi możliwymi zestawami danych określonymi przez specyfikację (w tym danych "skrajnych" tj. duża ilość elementów, albo nietypowe dane) to znaczy, że rozwiązanie jest właściwe i można przejść do pisanie programu.

Pisanie aplikacji

Po dowodzie poprawności algorytmu można przejść do pisania kodu. Bardzo ważne jest, aby napisany program przetestować. Nawet dla danych rozpatrywanych w poprzednim punkcie. Pozwoli to wyeliminować podejrzenie popełnienia błędu w rozważaniach, a przede wszystkim dowiedzie poprawności algorytmu. Ze względu na pisanie kodu ostatecznego należy dokładnie ocenić efektywność algorytmu: złożoności obliczeniowej czasowej i pamięciowej. Oczywiście czasem znalezienie lepszego rozwiązania jest niemożliwe, ale zawsze warto spróbować to uargumentować. Często prowadzi to do drobnej aczkolwiek sensownej optymalizacji.

Przykład

Przypuśćmy, że chcemy znaleźć największą liczbę pośród trzech podanych liczb rzeczywistych a, b i c.

1. Na początek określamy dane wejściowe: otrzymujemy trzy liczby rzeczywiste a, b i c. Na wyjście mamy zwrócić największą liczbę pośród podanych.
2. Najprostsze rozwiązanie to znaleźć maksimum z a i b oraz b i c, a następnie maksimum z wyników. Należy stwierdzić, że istnieje również potrzeba, aby zaimplementować funkcję maksimum.
3. Zapisujemy algorytm w postaci listy kroków:
   1. Wczytaj dane a, b i c
   2. Znajdź maksimum a i b oraz b i c
   3. Znajdź maksimum ze znalezionych maksimów
   4. Zwróć znalezione maksimum
4. Algorytm jest poprawnie wykonywany dopóki wprowadzone dane znajdują się w zakresie użytego typu zmiennej.
5. Kod właściwy zapisany w C++:
   1. function max(double a, double b){
   2.   return (a > b) ? a : b;
   3. }
   1. function max_z_trzech(double a, double b, double c){
   2.   return max(max(a, b), max(b, c));
   3. }

6. Dokonujemy analizy podanego rozwiązania. Jego efektywność pamięciowa jest minimalna i wykonujemy trzy operacje porównania. Okazuje się, że można wykonać tylko dwa porównania: należy znaleźć np. maksimum a i b, a potem większą liczbę porównać z c. Wracamy do oceny poprawności nowego sposobu rozwiązania okazuje się również poprawny, więc należy wrócić do poprzedniego punktu i napisać nowy kod.
7. Końcowy algorytm wygląda tak:
   1. function max(double a, double b){
   2.   return (a > b) ? a : b;
   3. }
   1. function max_z_trzech(double a, double b, double c){
   2.   return max(max(a, b), c);
   3. }

   Jest to najlepsze rozwiązanie, ponieważ wykonujemy tylko 2 porównania, a nie jak poprzednio 3. Tej złożoności już nie można poprawić ze względu na fakt, że wśród 3 elementów mamy dwie kolejne pary liczb. Użycie tylko jednego porównania jest niemożliwe. Algorytm został ukończony.