Co to jest algorytm ?

Na lekcjach matematyki czy fizyki często słyszymy zdanie "rozwiąż zadanie. Większość ich
rozwiązujemy według pewnych schematów. Najpierw wypisujemy dane i zastanawiamy się do
jakiego celu dążymy, a więc jaki ma być wynik. Następnie wypisujemy wzory łączące dane z
szukanymi bądź twierdzenia, które można zastosować.
Przed koniecznością rozwiązywania zadań stajemy również poza szkołą. Robimy to w każdej
innej dziedzinie naszego życia, na przykład:
 telefonując do koleżanki i zapraszając ją na ciasto
 gotując jajko na twardo
 kupując piłkę w sklepie
 znajdując najniższego ucznia w klasie
 pisząc wypracowanie
Również przy takim typie zadań musimy określić dane i warunki, które muszą one spełniać.
formułujemy także wynik, który pragniemy uzyskać.

Algorytm to przepis rozwiązania zadania, zawierający opis danych wraz z

opisem czynności, które należy wykonać z tymi danymi, aby osiągnąć zamierzony
cel.

Algorytm musi być:

1. poprawny, tzn. dla każdego poprawnego zestawu danych, po wykonaniu skończonej liczby
czynności, prowadzi do poprawnych wyników,
2. jednoznaczny- w każdym wypadku jego zastosowania, dla tych samych danych uzyskamy
ten sam wynik,
3. szczegółowy, aby wykonawca algorytmu rozumiał opisane czynności i potrafił je wykonać,
4. uniwersalny, aby służył do rozwiązywania pewnej grupy zadań, a nie tylko jednego
konkretnego przypadku zadania.

Etapy rozwiązywania problemów

W procesie rozwiązywania każdego zadania możemy wyróżnić pewne etapy, które nas do niego
prowadzą.

Etapy rozwiązywania problemów:

 1. Sformułowanie zadania
2. Określenie danych wejściowych
3. Określenie celu, czyli wyniku
4. Poszukiwanie metody rozwiązania, czyli algorytmu
5. Przedstawienie algorytmu w postaci:
 opisu słownego
 listy kroków
 schematu blokowego
 języka programowania
6. Analiza poprawności rozwiązania
7. Testowanie rozwiązania dla różnych danych. Ocena efektywności przyjętej
metody.

Działania niealgorytmiczne
Zastanów się: Czy wszystkie działania są algorytmiczne ?
Czy dla każdego zadania można skonstruować algorytm? Czy rozwiązanie każdego zadania
polega na wykonywaniu jednoznacznie opisanych, ściśle określonych czynności? Oczywiście, że
nie. Istnieją zadania, których realizacji nie można ująć w ramy jakiegoś planu działania. Taki
charakter ma np. każda twórczość artystyczna. Konieczna jest do tego wyobraźnia i twórcze
działanie, a na to nie ma przepisu.

Budowa algorytmów
Algorytmy powinny być tak przedstawiane, aby było możliwe ich jednoznaczne odczytanie i
zastosowanie. Niektóre algorytmy można opisać w języku potocznym, zwłaszcza wtedy, gdy
jego wykonawcą ma być człowiek (w informatyce zajmujemy się opracowywaniem algorytmów,
których wykonanie powierzamy komputerom).
Z czego składa się algorytm?
Zawiera on opis danych, opis wyników oraz plan działania, czyli przetworzenia danych. Plan ten
można przedstawić w postaci ciągu czynności, które muszą być wykonane w określonej
kolejności. Opis czynności występujących w algorytmie nazywamy instrukcjami.
 Algorytm liniowy
Ćwiczenie 1
Opracuj algorytm gotowania jaja na miękko.
Zastanów się jak ugotować jajko na miękko. Na początku opracowywania algorytmu przyjmijmy
założenie, że używamy kuchenki gazowej, posiadamy garnek i wodę. Oczywiście niezbędne jest
też samo jajko. Zakładamy również, że nic nie utrudni samej czynności, to znaczy np. w trakcie
gotowania nie zostaniemy pozbawieni dopływu gazu, czy też osoba nie wie co to garnek.

Algorytm ten ma postać:

1. Wlać do garnka zimną wodę.
2. Zapalić gaz.
3. Gotować wodę do wrzenia.
4. Włożyć jajko.
5. Odczekać trzy minuty.
6. Zgasić gaz.
7. Wyjąć jajko
Ma on prostą 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. Taki algorytm nosi nazwę
algorytmu liniowego ( sekwencyjnego).

Ćwiczenie 2
Opracuj algorytm telefonicznego zaproszenia koleżanki na ciasto. Numer telefonu : 666-22-88.
Wiesz już jak wyglądał poprzedni algorytm oraz co to jest algorytm liniowy. W tym przypadku
zrobimy założenie, że nic nie utrudni połączenia (a więc już za pierwszym razem zostaniemy
połączeni z wybraną osobą), a wykonawca czynności zna cyfry i wie jak wybiera się je z tarczy
telefonu.

Oto jak wygląda algorytm (wersja 1):

1. Podnieś słuchawkę.
2. Wybierz cyfrę 6.
3. Wybierz cyfrę 1.
4. Wybierz cyfrę 6.
5. Wybierz cyfrę 2.
6. Wybierz cyfrę 2.
 7. Wybierz cyfrę 2.
8. Wybierz cyfrę 2.
9. Przekaż informacje.
10. Odłóż słuchawkę.
Algorytmy liniowe 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 dalsze postępowanie
w algorytmie zależy od spełnienia, bądź nie, określonych warunków. Czasami musimy
powtórzyć pewne kroki algorytmu kilka razy.

Instrukcja warunkowa
W rzeczywistości, większość algorytmów 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ą. Działa ona według jednego z dwóch
przedstawionych schematów:
Jeśli spełniony jest warunek W, wykonaj instrukcję A.

Jeśli spełniony jest warunek W, to wykonaj instrukcję A; w przeciwnym razie wykonaj instrukcję B.
Instrukcja A i B opisuje jedną instrukcję lub instrukcję składającą się z ciągu instrukcji
wykonywanych sekwencyjnie. Instrukcja warunkowa pozwala dokonać wyboru jednej z dwóch
dalszych dróg wykonania algorytmu.

Ćwiczenie 2
Popraw opracowany wcześniej algorytm tak, aby uwzględniał sytuację, gdy po wybraniu numeru
jest on zajęty lub połączenie okazało się błędne.
Kiedy słychać sygnał zajętości numeru, a więc nie udało się uzyskać połączenia trzeba Odłożyć
słuchawkę. Tak samo postępujemy, gdy nawiązane zostało połączenie z innym Numerem.
Aby zrealizować taką sytuację zastosujemy instrukcję warunkową. Zrobimy to po to, aby opisać
czynności, powinny być wykonane wtedy kiedy zostało nawiązane poprawne połączenie, jak
również nie zostało nawiązane. Zauważ, że wtedy wykonawca znajdzie się w punkcie wyjścia,
czyli jakby w ogóle nie podjął próby telefonowania.

Algorytm może mieć postać taką (wersja 2):

1. Podnieś słuchawkę.
2. Wybierz cyfrę 6.
 3. Wybierz cyfrę 1.
4. Wybierz cyfrę 6.
5. Wybierz cyfrę 2.
6. Wybierz cyfrę 2.
7. Wybierz cyfrę 2.
8. Wybierz cyfrę 2.
9. Czy połączyłeś się z koleżanką ?
A. Jeśli TAK, to przejdź do kroku 10.
B. Jeśli NIE, to przejdź do kroku 11.
10. Zaproś koleżankę.
11. Odłóż słuchawkę.

Instrukcja iteracyjna
Instrukcja iteracyjna - ze znaną ilością powtórzeń
Przyjrzyj się uważnie algorytmowi. Zauważyłeś, że istnieją tu powtarzające się instrukcje, aż
czterokrotnie występuje "Wybierz cyfrę 2".
Takie 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ę A dokładnie n razy.

Ćwiczenie
Popraw opracowany wcześniej algorytm tak, aby sekwencję jednakowych czynności zastąpić
pętlą.

Oto algorytm (wersja 3):

1. Podnieś słuchawkę.
2. Wybierz cyfrę 6.
3. Wybierz cyfrę 1.
4. Wybierz cyfrę 6.
5. Wykonaj czynność cztery razy
 A. Wybierz cyfrę 2.
6. Czy połączyłeś się z koleżanką ?
A. Jeśli tak, to przejdź do kroku 7.
B. Jeśli nie, to przejdź do kroku 8.
7. Zaproś koleżankę.
8. Odłóż słuchawkę.
Działanie algorytmu może zakończyć się na dwa różne sposoby, albo uzyskamy połączenie z
koleżanką i zaprosimy ją na ciasto, albo nie połączymy się i wykonanie algorytmu ograniczy się
tylko do wykręcenia numeru.
Jak widzisz zastosowanie pętli zmienia sposób zapisu algorytmu, nie zmienia się jednak jego
działanie.

Instrukcja iteracyjna - ze spełnieniem warunku

Ćwiczenie
Uwzględnij w opracowanym wcześniej algorytmie przypadek braku połączenia lub nawiązanie
nieprawidłowego połączenia.
W poprzednim algorytmie w przypadku uzyskania nieprawidłowego połączenia bądź jego braku,
przechodziliśmy do ostatniego kroku , w którym odkładaliśmy słuchawkę. Kończyło się
Działanie algorytmu. W tej sytuacji powinniśmy rozpocząć raz jeszcze jego wykonywanie, nie
zostało to jednak opisane w konstrukcji.
Rozbudujemy teraz algorytm, tak by powtarzano wybieranie numeru aż do uzyskania połączenia.
Dopiszemy w tym celu polecenie będące drugim rodzajem instrukcji iteracyjnej:
Powtarzaj wykonywanie instrukcji A aż do spełnienia warunku W.
Czym jest instrukcja A, czym warunek W ?
Instrukcja A - podniesienie słuchawki, wybranie numeru
Warunek W - uzyskanie połączenia z wybranym numerem

Algorytm (wersja 4):

1. Czy słuchawka jest odłożona ?
A. Jeśli tak, to przejdź do kroku 2.
B. Jeśli nie, to odłóż słuchawkę.
2. Podnieś słuchawkę.
3. Wybierz cyfrę 6.
4. Wybierz cyfrę 1.
 5. Wybierz cyfrę 6.
6. Wykonaj czynność cztery razy
A. Wybierz cyfrę 2.
7. Czy połączyłeś się z koleżanką ?
A. Jeśli tak, to przejdź do kroku 8.
B. Jeśli nie, to przejdź do kroku 9.
8. Zaproś koleżankę.
9. Odłóż słuchawkę.
W algorytmie telefonicznego zaproszenia koleżanki dodaliśmy instrukcję, która uwzględniła, że
po nieudanej próbie uzyskanie połączenia należy odłożyć słuchawkę, a dopiero później
ponownie ją podnieść i spróbować raz jeszcze. W przypadku pierwszej próby nawiązania
połączenia również sprawdzamy odłożenie słuchawki.

Instrukcja iteracyjna
W naszym algorytmie sprawdzamy warunek uzyskania połączenia z koleżanką (krok 4).
Czasami zdarza się jednak, że już po podniesieniu słuchawki słychać, że linia jest zajęta.
Należałoby wtedy odłożyć słuchawkę i ponownie ją podnieść. Jeśli okazałoby się, że nadal
słychać w niej sygnał zajętości linii czynność należałoby powtórzyć. Musielibyśmy wykonywać
te czynności dopóki linia nie byłaby "czysta". W takim przypadku stosujemy instrukcję, która
działa według schematu:

Dopóki warunek W jest spełniony, wykonuj instrukcję A.

Algorytm (w wersji 5) wygląda tak :

1. Czy słuchawka jest odłożona ?
A. Jeśli tak, to przejdź do kroku 2.
B. Jeśli nie, to odłóż słuchawkę.
2. Podnieś słuchawkę.
3. Czy linia jest zajęta ?
A. Jeśli Tak, to:
a. Odłóż słuchawkę.
b. Podnieś słuchawkę.
c. Przejdź do kroku 3.
 B. Jeśli Nie, to przejdź do kroku 4.
4. Wybierz cyfrę 6.
5. Wybierz cyfrę 1.
6. Wybierz cyfrę 6.
7. Wykonaj czynność cztery razy
A. Wybierz cyfrę 2.
8. Czy połączyłeś się z koleżanką ?
A. Jeśli tak, to przejdź do kroku 9.
B. Jeśli nie, to przejdź do kroku 1.
9. Zaproś koleżankę.
10. Odłóż słuchawkę.
Jak widzimy w kroku 3 występuje pętla, w której sprawdzamy najpierw warunek, a dopiero
potem wykonywana jest instrukcja opisana przez kroki a, b. Jeśli warunek nie jest spełniony, to
instrukcja nie zostanie wykonana ani razu.
W informatyce możemy realizować szczególny rodzaj powtórzeń bez konieczności stosowania
pętli. Jest to technika rekurencji .