I_P_W14_M04_C++ Algorytm Euklidesa
W tym e‑materiale częściowo powtarzamy treści ze szkoły podstawowej.
Algorytm Euklidesa został przedstawiony około 300 r. p.n.e. i jest wciąż wykorzystywany! Algorytm Euklidesa to jedno z najstarszych i najpiękniejszych rozwiązań w historii informatyki – prosty, elegancki i zaskakująco skuteczny, 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.
Czy wiesz, że algorytm Euklidesa znalazł zastosowanie nie tylko w matematyce i informatyce, ale także… w muzyce? W 2005 roku Godfried Toussaint, matematyk i muzykolog, odkrył, że wiele tradycyjnych rytmów muzycznych z różnych kultur (np. kubańskich, afrykańskich czy indyjskich) można wygenerować za pomocą algorytmu Euklidesa!
Jak to działa? Algorytm rozkłada rytm na równe części i rozmieszcza uderzenia (np. bębna) w najbardziej równomierny sposób. Dzięki temu powstają znane i przyjemne dla ucha wzorce rytmiczne – jak np. rytm tresillo, który znajdziesz w wielu popularnych utworach.
Zatem następnym razem, gdy usłyszysz chwytliwy bit, pomyśl: może to właśnie Euklides gra na perkusji
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.