I_P_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.
Zaimplementujesz algorytm Euklidesa, wykorzystujący metodę odejmowania.
Zaimplementujesz zoptymalizowany algorytm Euklidesa.
Porównasz efektywność obu wersji algorytmu Euklidesa.