• przedstawianie algorytmu słownie, za pomocą schematu blokowego i pseudokodu,
• zaimplementowanie algorytmu Euklidesa w postaci programu komputerowego.

Z algorytmami często miewasz do czynienia na lekcjach matematyki. Podczas tej lekcji poznasz róĹźne sposoby zapisu algorytmu na przykładzie znajdowania największego wspólnego dzielnika dwóch liczb całkowitych i zaprogramujesz ten algorytm w Scratchu.

ALGORYTM ZNAJDOWANIA NWD

Algorytm Euklidesa, który opiera się na następującym spostrzeĹźeniu: jeśli od większej liczby odejmie się mniejszą, to mniejsza liczba i otrzymana róĹźnica będą miały taki sam największy wspólny dzielnik jak pierwotne liczby. Gdy wynikiem kolejnego odejmowania będzie para takich samych liczb, to liczba ta stanowi NWD.

ZAPIS SŁOWNY

Język naturalny umoĹźliwia zapis słowny algorytmu w formie logicznego ciągu kroków, które naleĹźy wykonać, aby osiągnąć pożądany efekt. Zaletą takiego sposobu zapisu jest prostota (nie trzeba zapamiętywać formalnych konstrukcji), do wad należą niedostateczna zwięzłość oraz moĹźliwość błędnej interpretacji. W przypadku algorytmu Euklidesa taki słowny plan działań moĹźe przedstawiać się następująco:

1. Wybieramy dwie liczby naturalne.
2. Jeśli liczby są równe, to NWD jest np. pierwszą z nich i to oznacza koniec działań.
3. Jeśli liczby nie są równe, to trzeba:
   • zbadać, która jest większa;
   • odjąć od niej mniejszą i zastąpić większą przez otrzymaną róĹźnicę;
   • wrócić do sprawdzenia warunku w punkcie 2 (pętla).

SCHEMAT BLOKOWY

Przedstawienie algorytmu w postaci graficznej z wykorzystaniem strzałek wskazujących kolejność wykonywania poszczególnych instrukcji umoĹźliwiają schematy blokowe. Elementy blokowe, które stosuje się podczas tworzenia schematu, to:

Schemat blokowy opisujący algorytm Euklidesa można przedstawić następująco:

ZAPIS W JĘZYKU PROGRAMOWANIA

Zapis algorytmu w konkretnym języku programowania jest bardzo formalny i precyzyjny, ale niekiedy mało przejrzysty albo zrozumiały wyłącznie dla programisty. Jeśli wykonasz zadanie 2, to obejrzysz te programy w całości.

Przeanalizuj powyższe zapisy i zbuduj w Scratchu skrypt realizujący algorytm Euklidesa. Elementy składające się na skrypt zamieszczono na zrzucie poniżej.

Pomoc: Film na You Tube

https://www.youtube.com/watch?v=id07HLpspOc&t=129s