Od problemu do programu - 3h

Specyfikacja algorytmu (specyfikacja zadania)

Specyfikacja algorytmu (specyfikacja problemu algorytmicznego) to dokładny opis problemu algorytmicznego, który ma zostać rozwiązany, oraz podanie danych wejściowych (dane) i danych wyjściowych (wynik).

Oto kilka przykładów specyfikacji problemów algorytmicznych, często nazywanych również specyfikacjami zadania.
Problem: Obliczanie ilorazu dwóch liczb rzeczywistych
Dane:
a – liczba rzeczywista
b – liczba rzeczywista

Wynik:
il – iloraz liczb a i b (a/b) – liczba rzeczywista

Co to jest algorytm ?

Na lekcjach matematyki czy fizyki często słyszymy zdanie „rozwiąż zadanie”. Większość tych zadań 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ć.

Czym jest algorytm?

Algorytm to przepis na rozwiązanie zadania, który zawiera opis danych wraz z opisem czynności, które należy wykonać z tymi danymi, aby osiągnąć zamierzony cel.

Cechy algorytmu

Co powinniśmy wiedzieć jeszcze zanim zabierzemy się za tworzenie algorytmu? Poznajmy cechy, które powinien posiadać algorytm.

Algorytm musi być:

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

Etapy rozwiązywania problemów

Wiemy już co to jest algorytm, jakie cechy powinien posiadać. Jak wygląda zatem tworzenie algorytmu?

W procesie rozwiązywania każdego zadania możemy wyróżnić pewne etapy, które nas do niego prowadzą. Tak samo postępujemy tworząc algorytm.

Etapy rozwiązywania problemów:

• Sformułowanie zadania
• Określenie danych wejściowych
• Określenie celu, czyli wyniku
• Poszukiwanie metody rozwiązania, czyli algorytmu
• Przedstawienie algorytmu w postaci: opisu słownego, listy kroków, schematu blokowego, języka programowania
• Analiza poprawności rozwiązania
• 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 algorytmu.

Co raz częściej do działań niealgorytmicznych zaliczamy także gotowanie. Niby mamy przepis na daną potrawę, ale tak naprawdę jest on „luźny”, mogę modyfikować lekko składniki, ich ilość czy czas przygotowania.

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?
Algorytm zawiera 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.

Algorytmy z życia codziennego

Załóżmy, że ugotowanie jajka to działanie algorytmiczne, czyli możemy utworzyć dla niego algorytm.

Zastanów się jak ugotować jajko na miękko. Na początku opracowywania algorytmu przyjmijmy, ż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 gotująca nie wie co to garnek.

Przykład algorytmu. Przykład algorytmu z życia codziennego, przykład algorytmu liniowego
Opracuj algorytm gotowania jaja na miękko.

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

Algorytmy powinny być tak przedstawiane, aby było możliwe ich jednoznaczne odczytanie i zastosowanie.

Niektóre algorytmy można opisać słownie korzystając z języka potocznego. Jest to proste zwłaszcza wtedy, gdy algorytm jest prosty, a jego wykonawcą ma być człowiek. Pamiętajmy jednak, iż informatyka zajmuje się opracowywaniem algorytmów, których wykonanie powierzone zostaje komputerom. Dlatego taki sposób zapisu nie zawsze jest wystarczający. Musimy sięgnąć po inne metody.

Z czego składa się algorytm?

Algorytm zawiera opis danych, opis wyników oraz plan działania, czyli przetworzenia danych. Możemy to przedstawić tak:

Przejdźmy teraz do tego, jak możemy zapisać algorytm, a w zasadzie tą główną jego część, czyli plan działania, przetworzenia danych. Będziemy to robić zapisując ciąg czynności (działań), które muszą być wykonane w określonej kolejności. Opis czynności występujących w algorytmie nazywamy instrukcjami.

Sposoby zapisu algorytmów:

• opis słowny
• lista kroków
• pseudojęzyk (pseudokod)
• schemat blokowy
• drzewo (drzewo algorytmu)
• język programowania

Załóżmy, że naszym celem jest przedstawienie algorytmu obliczania średniej dwóch liczb. Algorytm ten przedstawimy teraz korzystając z podanych wyżej wszystkich sposobów zapisywania algorytmu.

Zadanie

Napisz algorytm obliczający średnią arytmetyczną dwóch liczb rzeczywistych.

Przykładowe rozwiązania zawierające wszystkie sposoby zapisu algorytmu zaprezentuję poniżej.

Opis słowny

W jaki sposób obliczymy średnią dwóch liczb? Weźmiemy dwie liczby i je zsumujemy, a otrzymany wynik podzielimy przez 2. Wystarczy teraz po prostu to zapisać.

Rozwiązanie 1. Opis słowny:
Weź dwie liczby i dodaj je do siebie. Otrzymany wynik podziel przez 2.

Lista kroków

Lista kroków to najprostsza i jednocześnie najbardziej naturalna metoda zapisywania algorytmu. Polega na opisie reguł postępowania za pomocą kolejnych kroków, punktów. Jest to sposób, z którym prawdopodobnie spotkałeś się na lekcjach matematyki, na których nauczyciel podaje schemat rozwiązania zadania danego typu.

Elementem charakterystycznym w tym sposobie zapisu jest numeracja poszczególnych kroków.

Rozwiązanie 2a. Lista kroków:

Krok 1. Pobierz pierwszą liczbę.
Krok 2. Pobierz drugą liczbę.
Krok 3. Dodaj liczby do siebie.
Krok 4. Wynik sumowania podziel przez 2.
Krok 5. Wyświetl wynik.
Krok 6. Zakończ

Powyższy algorytm możemy zapisać również za pomocą listy kroków pomijając słowo krok:

Rozwiązanie 2b. Lista kroków:
1. Pobierz pierwszą liczbę.
2. Pobierz drugą liczbę.
3. Dodaj liczby do siebie.
4. Wynik sumowania podziel przez 2.
5. Wyświetl wynik.
6. Zakończ

Pseudojęzyk, pseudokod

Pseudojęzyk (zwany również pseudokodem) to sposób pośredni między listą kroków, a językiem programowania. Zwykle zapis podobny jest do któregoś z popularnych języków programowania, ale jest mniej formalny.

Rozwiązanie 3a. Pseudokod:

Początek
				Rzeczywiste a
				Rzeczywiste b
				suma:= a+b
				średnia:= suma/2
				Wypisz(średnia)
				Koniec

W powyższym pseudokodzie widzimy dwa działania (instrukcje): obliczającą sumę i średnią. Tak naprawdę możemy przecież połączyć je w jedno.

Rozwiązanie 3b. Pseudokod:

Początek 
				Rzeczywiste a 
				Rzeczywiste b 
				średnia:= (a+b)/2 
				Wypisz(średnia) 
				Koniec

Schemat blokowy

Schemat blokowy to graficzny sposób przedstawienia algorytmu. Składa się on z bloków, zawierających określone działania, oraz połączeń wskazujących kolejność ich wykonywania.

My teraz wracamy do naszego przykładu ze średnią. Jak będzie teraz wyglądał nasz algorytm?

Schemat blokowy algorytmu

Język programowania

Aby zrealizować algorytm za pomocą komputera, zapisujemy go w postaci odpowiednio dobranego języka programowania. Mówiąc w skrócie, piszemy program.

Algorytmy można przedstawiać na różne sposoby. Od prostego, czyli po prostu opowiedzeniu o algorytmie, poprzez narysowanie schematu blokowego, aż po język programowania i ostateczną realizację w postaci programu komputerowego. Sposób zapisu dobieramy do konkretnego przypadku.

Struktura programu w C++

Ogólna struktura programu w C++ (generowana automatycznie) składa się z kilku części, które zostaną opisane poniżej:

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])

{
	/* instrukcje funkcji main */
	return 0;
}
				

Część I - trochę o bibliotekach

Ta część programu opisuje biblioteki jakie mają być dołączone do programu. Biblioteki to pliki, których zawartość jest dołączana do programu za pomocą dyrektywy preprocesora #include. Biblioteka to plik o nazwie podanej w nawiasie "< nazwa biblioteki >", który posiada między innymi definicje przydatnych funkcji.

				#include <cstdlib>
				#include <iostream>
				//dodanie biblioteki cmath, w której znajduje się 
				//definicja funkcji pierwiastkującej sqrt
				#include <cmath>

				using namespace std;

				int main()
				{

					//użycie funkcji sqrt wyznaczającej 
					//pierwiastek z liczby 2 
					cout<<sqrt(2)<<endl;

					return 0;
				}
				

Np. biblioteka cstdlib zawiera funkcje ogólne takie jak konwersje, alokacja pamięci czy funkcje matematyczne. Biblioteka iostream (input/output stream) jest standardową biblioteką wejścia/wyjścia w C++. Jeśli chcemy coś wyświetlać na ekranie (za pomocą obiektu cout i przeciążonego operatora "<<"), lub pobierać dane z klawiatury (za pomocą obiektu cin i przeciążonego operatora ">>") musimy ją dodać do nagłówka programu.

Wcześniejsze wersje bibliotek miały rozszerzenie "*.h". Język C++ odchodzi od takiego nazewnictwa, gdyż pliki z tym rozszerzeniem były początkowo wykorzystywane w języku C (oczywiście C++ może nadal korzystać z tych bibliotek) i dla rozdzielenia bibliotek kojarzących się z danym językiem, C++ przyjął nazwy bez rozszerzenia. Niektóre biblioteki zostały przekształcone z C na C++, i w takich przypadkach pozbyto się rozszerzenia, ale dodano literkę "c" na początku takiego pliku np.:

Część II - przestrzenie nazw

Dyrektywę using namespace musimy użyć w przypadku, gdy zamiast pliku iostream.h, będziemy używać iostream, w celu udostępnienia definicji zawartej w tym pliku. Generalnie chodzi o to, żeby nie pisać za każdym razem wywołanie obiektu cout czy cin z przedrostkiem std::. Np.:

				#include<iostream> 
				#include<cstdlib>

				int main()
				{

				//bez użycia dyrektywy using namespace std musimy 
				//do każdej definicji z biblioteki 
				//iostream dodać przedrostek std::

				std::cout<<"Ala ma kota"<<std::endl;

				system("pause");
				return 0;
				}
				

Wyobraźmy sobie, że mamy dwa pakiety, w których zdefiniowana jest funkcja o nazwie wspaniala(). Pierwszy pakiet jest od producenta JANEK, a drugi od MARCIN. Jeśli chcemy używać funkcji wspaniala() od MARCIN, bo uważamy, że jest lepsza, udostępniamy definicję przestrzeni nazw MARCIN:

using namespace MARCIN;

i nie musimy za każdym wywołaniem funkcji wspaniala(), pisać MARCIN::wspaniala().

Wiąże się to także z uproszczeniem uaktualnienia starszych wersji programu, dodając tylko odpowiednią dyrektywę bez konieczności dopisywania do każdego elementu przedrostka.

Część III - funkcja main

Funkcja main() jest charakterystyczną funkcją w C++, która musi występować w każdym konsolowym programie. Wszystko co zaczyna się dziać w danej aplikacji, jest określana w ciele właśnie tej funkcji. Oczywiście wszystkie inne funkcje mogą być wywoływane z wnętrza tej funkcji.

Funkcja main() ma kilka postaci:

• int main() lub int main(void) - postacie równoważne, oznaczające, że w ciele funkcji pojawia się informacja zwrotna (return 0 lub return EXIT_SUCCESS), która zwraca do systemu operacyjnego informacje o zakończeniu działania danej aplikacji
• void main() - nie posiada informacji zwrotnej o zakończeniu działania programu, niezalecane, a w niektórych systemach niedopuszczalne
• main() - to samo co int main()
• int main(int argc, char *argv[]) - funkcja z argumentami opisana poniżej.

Podczas uruchomienia programu za pomocą konsoli (w Windowsie: cmd.exe), oprócz podania nazwy programu, który chcemy uruchomić, możemy przekazać wstępne dane (parametry programu). Argument int argc, mówi ile tych danych jest, natomiast char *argv[] przechowuje te dane. Prześledźmy przykład programu program.exe, który wyświetli argumenty danego programu:

#include <cstdlib>
				#include <iostream>

				using namespace std;

				int main(int argc, char *argv[])
				{

				for(int i=1;i<argc;i++)
					cout<<i<<" argument to "<<argv[i]<<endl;
					
				

				return 0;
				}
				

Przykładowe wywołanie programu program.exe i wynik działania:

Wywołana została aplikacja z argumentami: arg1, arg2, x oraz 8991. Zauważmy, że argumenty oddzielamy spacją.

Jeśli program wywołujemy bez dodatkowych parametrów, listę argumentów funkcji main() można pominąć.

Część IV - życie programu

W tej części programu zaczyna się życie naszej aplikacji. Wszystko to co tu napiszemy, będzie rzutowało na sposób zachowania się naszego programu. Oprócz słowa kluczowego return, które zostało wyjaśnione w części III, domyślnie dopisana zostaje przez Dev-C++instrukcja system("pause"). Powoduje ona zatrzymanie się programu w tym miejscu i wyświetlenie komunikatu: "Aby kontynuować, naciśnij dowolny klawisz . . .".

Zauważmy, że blok funkcji main(), zaczynamy nawiasem "{" i kończymy nawiasem "}".