Jak obiecałem tak robię. Czyli kursów ciąg dalszy. Kolejnym omawianym przeze mnie tematem będą podstawy algorytmiki. Nie mówię, że jestem ekspertem od algorytmów ale postaram się w miarę przystępnie wyjaśnić czym są i jak działają te najbardziej podstawowe.
Weźmy jakiś prosty przepis. Powiedzmy na herbatę. Otóż co musimy mieć aby ją zrobić? Wodę powiedzie zapewne i herbatę. No dobrze ale to jeszcze nie wszystko. Po pierwsze musi to być woda zagotowana, czyli najpierw musimy tę wodę zagotować, ba musimy ją wlać do czajnika z kranu, czyli potrzebujemy także czajnik i jakieś źródło wody. Lecz nie rozdrabniajmy się za bardzo bo moglibyśmy iść tym tropem w nieskończoność. Czyli co robimy? Bierzemy czajnik, wlewamy do niego wodę, czekamy aż się zagotuje, następnie bierzemy szklankę, wkładamy do niej woreczek z herbatą, zalewamy wrzątkiem i czekamy aż się zaparzy. Możemy ją też później ewentualnie wymieszać.
Wróćmy więc do naszego pytania czym są algorytmy. Są one właśnie takimi przepisami jak coś zrobić. Są one bardzo precyzyjne, nie ma w nich ogólników. Służą one do opisania rozwiązania jakiegoś problemu np.: posortowania zbioru liczb, znalezienia najmniejszej liczby czy też czegoś bardziej złożonego jak szyfrowanie danych. Algorytmy same w sobie są starsze niż komputery.
Algorytmy przedstawiane są najczęściej za pomocą schematu blokowego lub listy kroków. Na razie skupmy się może na liście kroków a schemat blokowy opiszę w następnej części. Otóż jeśli chcemy przedstawić algorytm potrzebujemy dwóch rzeczy: specyfikacji algorytmu oraz algorytmu, że tak to nazwę, właściwego.
Specyfikacja algorytmu składa się z trzech części: problemu, danych oraz wyniku. Bazując na naszym przykładzie robienia herbaty problem możemy określić następująco:
Problem: Przygotowanie herbaty.
Naszymi danymi w tym wypadku (czyli tym co jest potrzebne na wstępie, zanim zaczniemy wykonywać algorytm) są woda i torebka z herbatą. Wynikiem jest z kolei zdatna do picia herbata. Całość specyfikacji mogłaby wyglądać następująco:
Specyfikacja:
Problem: Zrobienie herbaty.
Dane: Woda i torebka z herbatą.
Wynik: Przygotowana herbata.
Mając już określoną specyfikację problemu, możemy przystąpić do próby stworzenia jego rozwiązania. Przedstawimy to jako listę kroków potrzebnych do wykonania aby zrobić herbatę.
Krok 1: Nalej wodę do czajnika.
Krok 2: Ustaw czajnik na (włączonym!) gazie i poczekaj aż się zagotuje woda.
Krok 3: Włóż torebkę z herbatą do szklanki.
Krok 4: Gdy woda się zagotuje wlej ją do szklanki.
Krok 5: Poczekaj aż herbata się zaparzy. Po zaparzeniu herbaty zakończ algorytm.
Oczywiście ten algorytm jest bardzo uproszczony, proces robienia herbaty jest bardzo złożony, co jeśli osoba która nie ma torebki z herbatą tylko np. herbatę sypaną spróbuje go wykonać. Utknie ona na trzecim kroku gdyż nie będzie mogła tej torebki tam włożyć. Albo wyobraźmy sobie coś gorszego: zamiast zwykłego czajnika osoba ta ma czajnik elektryczny. Zgodnie z algorytmem powinna ona postawić ten czajnik na gazie a wtedy będzie katastrofa!
Jak się zabezpieczyć przed czymś takim? Można stosować tzw. wyrażenia warunkowe. Polegają one na tym, że przed wykonaniem jakiegoś kroku sprawdzamy czy dany warunek jest spełniony. Jeśli tak to wykonujemy jedno a jeśli nie to robimy coś innego. Wracając do naszego przykładu z herbatą i czajnikiem elektrycznym to krok drugi moglibyśmy zmodyfikować następująco:
Krok 2: Jeśli czajnik jest zwykły to ustaw go na gazie.
No dobrze ale co jeśli jednak ktoś ma ten czajnik elektryczny a chce zrobić herbatę? Wtedy możemy zastosować następujący trik:
Krok 2: Jeśli czajnik jest zwykły to ustaw go na gazie a jeśli czajnik jest elektryczny to postaw go na podstawce (nie mam pojęcia jak się to fachowo nazywa, mea culpa) i włącz.
Krok ten nam się strasznie rozpisał a to nie dobrze robić zajmujące dużo miejsca kroki. Zmniejszają one przejrzystość algorytmu i wygodę korzystania z niego. Dobrze jest więc to zapisać w ten sposób.
Krok
2: Jeśli czajnik jest zwykły to wykonaj krok 3, natomiast jeśli jest elektryczny krok 4.
Krok 3: Ustaw czajnik na gazie.
Krok 4: Ustaw czajnik na podstawce i włącz.
Tak naprawdę jest to jednak tylko estetyka i to od nas zależy jak ten algorytm przedstawimy. Cały algorytm ze specyfikacją może być następujący.
Specyfikacja:
Problem: Zrobienie herbaty.
Dane: Woda i torebka z herbatą.
Wynik: Przygotowana herbata.
Krok 1: Nalej wodę do czajnika.
Krok
2: Jeśli czajnik jest zwykły to wykonaj krok 3, natomiast jeśli jest elektryczny krok 4.
Krok 3: Ustaw czajnik na gazie i przejdź do kroku 5.
Krok 4: Ustaw czajnik na podstawce i włącz.
Krok 5: Gdy woda się zagotuje wlej ją do szklanki.
Krok 6: Poczekaj aż herbata się zaparzy. Po zaparzeniu herbaty zakończ algorytm.
Jeśli byśmy chcieli moglibyśmy rozbudować ten algorytm o sprawdzanie czy jest to torebka z herbatą, czy herbata sypana oraz o wiele innych warunków i kroków ale nie to jest naszym celem. Ogólnie jedną z podstawowych zasad algorytmiki i programowania jest zasada "Keep it simple", czyli w chamskim tłumaczeniu: utrzymaj to proste. Powinniśmy po prostu starać się aby nasze algorytmy i kod były jak najprostsze w wykonaniu i przeglądaniu, gdyż im bardziej są one złożone i dłuższe tym trudniej będzie nam się w nich połapać.
Jak na wstęp to myślę, że to wystarczy. W późniejszych częściach kursu postaram się rozwinąć temat algorytmów, zaprezentuję proste algorytmy i może nawet obiecany w tym poście Schemat Hornera. Jeśli to przeczytałeś i się spodobało to miłe będzie zostawienie komentarza lub "zalajkowanie". Jestem młodym bloggerem i takie rzeczy, nawet krytyczne uwagi, będą dla mnie mile widziane.
Brak komentarzy:
Prześlij komentarz
Pamiętaj aby Twoje komentarze były zawsze kulturalne i zgodne z obowiązującą Netykietą. Nie przeklinaj, nie obrażaj i nie wyzywaj innych użytkowników. PS: Nie karm troli.