Algorytmy, C++, Matura z informatyki - nauka i materiały.

Największy wspólny dzielnik

W celu wyliczenia największego wspólnego dzielnika dla dwóch liczb posłużymy się algorytmem stworzonym przez greckiego matematyka Euklidesa.


Największym wspólnym dzielnikiem dwóch liczb jest największa z liczb, która dzieli obie te liczby bez reszty. Euklides założył, że odejmując od większej mniejszą, NWD dwóch liczb nie zmienia się.

Przykłady:
-dla 15 i 21 NWD to 3
-dla 999 i 81 NWD to 27

Proste algorytmy wykorzystujące podzielnośc to absolutny must have jeśli chodzi o maturę z informatyki.

Oto moja interpretacja programu na NWD, wykorzystująca resztę z dzielenia (modulo).

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *