I_R_W14_M04 Algorytm Euklidesa
W tym materiale powtarzamy wiadomości ze szkoły podstawowej. Możesz je sobie przypomnieć korzystając z modułowego e‑podręcznika do szkoły podstawowej Cyfrowi tubylcy to my, watek 8: Lekcje programowania.
Algorytm Euklidesa został przedstawiony około 300 r. p.n.e. Jest on jednym z najstarszych wciąż wykorzystywanych algorytmów, a służy do znajdowania największego wspólnego dzielnika dwóch liczb całkowitych. Ten e‑materiał poświęcimy właśnie algorytmowi Euklidesa i różnym sposobom jego realizacji.
Ćwiczenie na rozgrzewkę:
Więcej informacji o wyznaczaniu największego wspólnego dzielnika znajdziesz w modułowym e‑podręczniku do matematyki: Wątek 1, moduł 1: NWD, NWW
Powtórzysz informacje o algorytmie Euklidesa.
Przeanalizujesz dwa warianty implementacji algorytmu Euklidesa.
Prześledzisz algorytm Euklidesa zapisany za pomocą schematu blokowego.
Zaimplementujesz algorytm Euklidesa, wykorzystujący metodę odejmowania.
Zaimplementujesz zoptymalizowany algorytm Euklidesa.
Porównasz efektywność obu wersji algorytmu Euklidesa.