Przeczytaj
Implementacja algorytmu Euklidesa w języku C++
Zaimplementuj algorytm Euklidesa, wykorzystując:
odejmowanie,
resztę z dzielenia.
Specyfikacja problemu:
Dane:
a
,b
– liczby naturalne dodatnie dla których program będzie wyznaczał NWD
Wynik:
Na standardowym wyjściu program wypisuje NWD liczb a
i b
.
Porównaj swoje rozwiązanie z filmem.
![](https://static.zpe.gov.pl/portal/f/res-minimized/R12rgKYS7tEXF/1689532022/1i254blkdgq3G4ixjykHcDQkT2m0zz4a.jpg)
Film dostępny pod adresem /preview/resource/R12rgKYS7tEXF
Film nawiązujący do treści materiału algorytmu Euklidesa - zastosowanie różnych pętli.
Przeanalizuj prezentację. Porównaj ze sobą działanie dwóch wersji algorytmu dla różnych par liczb.
Podsumowanie
Wyznaczymy NWDNWD liczb 35
i 14
przy użyciu dwóch wariantów algorytmu Euklidesa.
Algorytm Euklidesa z odejmowaniem
W tej wersji algorytmu interesuje nas różnica liczb, których NWD chcemy znaleźć. Odejmujemy zawsze mniejszą liczbę od większej.
Szukając NWD liczb 35
i 14
, wykonamy następujące czynności:
Odejmiemy od – powstaje nowa para liczb: i .
Odejmiemy od – otrzymujemy następną parę: i .
Odejmiemy od – pozostaje nam para liczb i .
Cykl odejmowania i tworzenia nowych par kończymy w chwili, gdy otrzymamy dwie identyczne liczby; każda z nich to NWD. W przypadku 35
i 14
jest to 7
.
Implementacja w języku C++
Algorytm Euklidesa z resztą z dzielenia
Wykonujemy następujące działania:
Obliczamy resztę z dzielenia przez . Wynosi ona .
Obliczamy resztę z dzielenia 14 przez 7; wynik operacji to . Pozostały nam liczby i .
Ponieważ jedna z liczb ma wartość zero, druga z nich (czyli ) jest największym wspólnym dzielnikiem.
Implementacja algorytmu w języku C++
Słownik
akronim pojęcia „największy wspólny dzielnik”