Temat: Euklides zakodowany

• 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.