Implementacja algorytmów

Algorytmy to dokładny opis sposobu postępowania prowadzącego do określonego wyniku. Kolejne kroki algorytmu zapisuje się sekwencyjnie (jeden po drugim). Środki używane do tego opisu mogą być różne. Najstarsze opisy miały charakter słowny. Na przykład starożytny matematyk grecki Euklides zauważył, że największy wspólny podzielnik dwóch liczb nie zmienia się, gdy od większej odejmiemy mniejszą. Ta informacja wystarczy do sformułowania algorytmu znajdowania największego wspólnego mianownika (nazwanego algorytmem Euklidesa): odejmuj od większej liczby mniejszą, aż obie będą równe – wtedy każda z nich jest równa największemu wspólnemu mianownikowi pierwotnych liczb.

Na stronach I LO w Tarnowie opisano dokładnie ten algorytm, podając kilka innych niż słowne jego opisów. W czasach rozwoju algorytmiki współczesnej dużą popularność zdobyły opisy rysunkowe algorytmów, zwane schematami blokowymi lub schematami przepływu. Na stronie http://www.otwartaedukacja.pl/programowanie/schematy/ dostępne jest oprogramowanie do rysowania takich schematów (w planach jest jego rozwój – tak aby uzyskać możliwość zapamiętywania prac i generowania kodu programu). Nim narysowano poniższy diagram:

Strzałki pokazują kierunek przepływu, a romby podejmowane decyzje. Znakami := oznaczamy operację podstawienia do zmiennej (a:=9 oznacza, że zmienna a otrzymuje wartość 9). Analizując krok po kroku taki diagram możemy zrozumieć działanie algorytmu.

Rysowanie algorytmów

Aby takie diagramy móc prosto przekształcić na programy, muszą one składać się ze schematów, którym można przyporządkować instrukcje programów. W zasadzie wystarczy trzy rodzaje schematów:

- instrukcja warunkowa (wykonanie czegoś jeśli sprawdzony jest warunek); - powtarzanie pod zadanym warunkiem; - powtarzanie aż osiągnie się oczekiwany efekt (postawiony warunek).

Stanie się to jasne, gdy przeanalizujemy przykłady (więcej szczegółów - zobacz kurs Pascala, który opublikował Aleksander Smywiński-Pohl: http://www.apohllo.pl/dydaktyka/wdi/pascal).

1. Instrukcja warunkowa (if)

Przykład:

if wyr_log then
  {instrukcja_1}
else
  {instrukcja_2};
{instrukcja_3};

2. Powtarzanie pod zadanym warunkiem - pętla while

Przykład:

var 
 znak : char;
begin 
 while not EOF do begin // poki jest coś do przeczytania - czytaj ze standardowego urządzenia wejście i zapisz na wyjście.
   read(znak);
   write(znak);
 end;
end.

3. Powtarzanie aż osiągnie się oczekiwany efekt - pętla repeat

Przykład:

var 
 znak: char;

begin
 repeat 
   writeln("Wprowadź znak i naciśnij [enter]. Aby zakończyć wprowadź 'k'");
   readln(znak);
   write("Wprowadziłeś ");
   writeln(znak);
 until znak = 'k';
end.

Od schematu do programu

Zobaczmy na przykładzie jak przekształcić najpierw diagram na postać standardową (złożoną wyłącznie z powyższych wzorców), a następnie na instrukcje.

Schemat algorytmu NWP po przekształceniu na postać standardową:

Schemat ten stworzony na portalu http://www.otwartaedukacja.pl/programowanie/schematy/

Większe możliwości daje (angielski) portal http://www.js-graph.net/demos/jsgdemoext/.

Poniższy rysunek pokazuje algorytm „rozkomponowany”. Wydzielono dwie „instrukcje”: pętlę powtarzania pod warunkiem (while - zielony) oraz instrukcję warunkową (wykonaj coś pod warunkiem, if, kolor popielaty).

Możemy już zamienić te schematy na instrukcje Pascala. Zastosujemy metodę od ogółu do szczegółu.

1. Najpierw szkielet programu:

// start

czytaj(a,b);

// szukaj_nwp

wypisz_wynik;

//stop

2. Teraz sam algorytm :

schemat zielony: while a<>b do [schemat szary]
schemat szary: if a<b then b:=b-a else a:=a-b;

3. Składamy to wszystko razem:

// start

czytaj(a,b);

// szukaj_nwp

while a<>b do if a<b then b:=b-a else a:=a-b;

wypisz_wynik;

//stop

4. Na koniec wypełniamy szczegóły

// start
var a,b : integer;

begin
//czytaj(a,b);
write('a=');readln(a);
write('b=');readln(b);

// szukaj_nwp
while a<>b do if a<b then b:=b-a else a:=a-b;

// wypisz_wynik;
writeln('NWP=',a);

//stop
end.

Składanie programu z klocków

Początkującym programistom może pomóc układanie programów z klocków – podobnych nieco do klocków Lego. Pomysł pochodzi z amerykańskiego projektu Scratch - przeznaczonego do nauki programowania przez dla dzieci.

Pod adresem http://www.otwartaedukacja.pl/programowanie/bl/code/ przygotowano taki graficzny edytor programów, który wykorzystuje projekt Blocky rozwijany przez Google.

Powyższy algorytm Euclidesa może zostać poskładany z klocków następująco:

Ten portal umożliwia między innymi generowanie kodu w różnych językach programowania. Na przykład w języku Python. Wśród bloczków nie ma operacji pobierania danych. Po ich dopisaniu (dwie pierwsze linijki - w miejsce zainicjowania konkretnymi liczbami) uzyskamy program:

a=int(input('liczba a='))
b=int(input('liczba b='))
while b != a:
  if a < b:
    b = b - a
  else:
    a = a - b
print(a)

Wyjaśnienia wymagają zapisane w pierwszych linijkach operacje pobierania danych. Zapis int() oznacza wprowadzanie liczby całkowitej, input() odczyt tego co użytkownik komputera pisze na klawiaturze, a napisy (łańcuchy znaków) 'liczba ...=' - co się wyświetli przed pobraniem danych.

Programowanie w Pythonie

Porównując przejrzystość zapisu schematów blokowych, bloczków, programu w Pascalu i Pythonie, dyskusyjne wydaje się twierdzenie, że reprezentacja graficzna jest lepsza. Jeśli dodatkowo weźmie się pod uwagę, że programiści zaprzestali pisania programów w sposób mało przejrzysty – wydaje się, że nauczanie nawet małych dzieci programowania w takim języku jak Python jest lepszym pomysłem, niż zabawa z bloczkami. Choćby dlatego, że możemy liczyć na pomoc olbrzymiej społeczności programistów Pythona. Przeglądając kody programów dostępnych w internecie raczej rzadko trafimy na tak mało przejrzysty zapis, jak powyżej. Częściej będzie to coś w rodzaju:

pierwsza_liczba=int(input('Podaj pierwszą liczbę całkowitą='))
druga_liczba=int(input('Podaj drugą liczbę całkowitą='))
while druga_liczba != pierwsza_liczba:
  if pierwsza_liczba < druga_liczba:
    druga_liczba = druga_liczba - pierwsza_liczba
  else:
    pierwsza_liczba = pierwsza_liczba - druga_liczba
print('Największy wspólny podzielnik=',pierwsza_liczba)

Pewną trudność sprawia fakt, że dostępne podręczniki programowania uczą konkretnych języków. Brakuje podręcznika, który pomagałby w nauce programowania, umożliwiając poznawanie języka niejako przy okazji. Dlatego taki podręcznik jest przygotowywany na zasadach otwartych.

Implementacja algorytmów

Spis treści