Page 19 - informatyka 8

2. Pracując w parach, przeanalizujcie algorytm Euklidesa zaprogramowany w środowisku Scratch. Poprawcie błędy
w przedstawionym skrypcie i sprawdźcie działanie programu.

3. Pracując w parach, porównajcie schemat blokowy algorytmu Euklidesa wyko- Ciekawe!
nany w programie JavaBlock (s. 16) oraz skrypt zaprogramowany w środowisku
Scratch (s. 17). Omówcie różnice.

Ocena działania algorytmu polega na sprawdzeniu, czy jest poprawny i skoń-
czony (zatrzymuje się i daje oczekiwany wynik), jednoznaczny (przy tych samych
danych wejściowych zawsze daje te same wyniki), sprawny (działa krótko i zajmuje
mało pamięci).
Przedstawiona wersja algorytmu Euklidesa (z odejmowaniem) nie jest doskona-
ła, bo jeśli różnica pomiędzy liczbami jest duża, odejmowanie należy powtarzać
wiele razy. Szybciej i efektywniej znajdziemy największy wspólny dzielnik dwóch
liczb, jeśli odejmowanie zastąpimy wyznaczaniem reszty z dzielenia. Chociaż Euklides zyskał sławę
Algorytm wyszukiwania największego wspólnego dzielnika (z resztą z dzielenia) wielkiego uczonego, niewiele wie-
rozpoczynamy od podzielenia większej z wybranych liczb przez mniejszą. Następ- my o jego życiu. Prawdopodobnie
nie mniejszą z wybranych liczb (dzielnik) dzielimy przez resztę z dzielenia otrzy- studiował w Akademii Platońskiej
maną w poprzednim dzieleniu. Czynności te wykonujemy tak długo, aż reszta w Atenach. Nauczał w słynnej
z dzielenia osiągnie wartość zero. Wówczas dzielnik tej pary liczb jest największym Szkole Aleksandryjskiej i założył
wspólnym dzielnikiem (NWD). własną szkołę matematyki.

17