Temat: Euklides poprawiony

• jak poprawić algorytm Euklidesa, żeby działał szybciej,
• jak zapisać poprawiony algorytm Euklidesa w formie programu komputerowego,
• różnice między programowaniem wizualnym a tekstowym

ALGORYTMY BLOKOWO, WIZUALNIE I TEKSTOWO

Algorytm w formie schematu blokowego można zakodować w dowolnym języku. Poniższe zestawienie pokazuje zaimplementowanie schematu blokowego w językach wizualnym i tekstowym.

Klasyczny algorytm Euklidesa, opisany w lekcji 3.1, ma pewną wadę – jeśli liczby znacznie różnią się wielkością, trzeba wykonać bardzo dużo działań. W przypadku liczb 1002 i 6 odejmowanie wykonywane jest sto kilkadziesiąt razy. A przecież łatwo zauważyć, że 1002 jest podzielne przez 2, suma cyfr wynosi 3, więc jest również podzielna przez 3. To wystarczy, żeby stwierdzić, iż NWD wynosi 6. Czy algorytm Euklidesa może to policzyć równie szybko? Tak, ale trzeba go poprawić.

DRUGA WERSJA ALGORYTMU EUKLIDESA

Algorytm Euklidesa można zrealizować szybciej – za pomocą operacji modulo. Odejmowanie trzeba zastąpić sprawdzaniem reszty z dzielenia większej liczby przez mniejszą. Gdy reszta ta osiągnie zero, należy skończyć działanie i jako wynik wziąć drugą liczbę. Kolejne kroki można opisać następująco:

• • Wybierane są dwie liczby naturalne.
  • Dopóki żadna z liczb nie jest równa 0:
    • jeśli pierwsza liczba jest większa, to zastępuje się ją przez resztę z dzielenia całkowitego pierwszej liczby przez drugą;
    • w przeciwnym razie zastępuje się drugą liczbę przez resztę z dzielenia całkowitego drugiej liczby przez pierwszą (pętla);
  • Jako wynik (NWD) podawana jest suma liczb (po zakończeniu pętli).

Jak będzie to wyglądało dla liczb 1002 i 6?

Zamiast 1002 należy wziąć 6, a zamiast 6 (1002 modulo 6), czyli 0. NWD wynosi więc 6. Nowy algorytm wykonał tylko jeden krok obliczeń.

• Oblicz za pomocą tego algorytmu NWD dla liczb: 152 i 57, 1025 i 725, 132 i 44.

ZADANIE

Ułóż poprawiony algorytm Euklidesa w Scratchu. W razie potrzeby skorzystaj z poniższego zrzutu, na którym umieszczono potrzebne bloki.