NWD(a, b) - największy wspólny dzielnik z dwóch dowolnych liczby naturlanych - a i b, jest równy największej możliwej liczbie, która dzieli a i b.
NWD możemy policzyć wypisując wszystkie dzielniki obu liczb i poszukać największego z nich.
Niestety ten sposób, w przypadku wielkich liczb może być bardzo czasochłonny.
Aby obliczyć NWD dwóch liczb możemy posłużyc się algorytmem Euklidesa.
Sprawdza on czy podane dwie liczby są takie same - w takim wypadku NWD tych liczb jest równe tym liczbą.
W przeciwnym wypadku odejmujemy mniejszą z nich od większej, NWD tych liczb się nie zmienia, gdyż jeśli dzieli ono dwie liczby to dzieli również ich różnicę.
Powtarzamy tą czynność tak długo, aż liczby nie będą równe.
Ten algorytm, nazywamy algorytmem Euklidesa z odejmowaniem, gdyż operację, którą najczęściej wykonujemy jest odejmowanie.
Algorytm ten możemy napisać na dwa sposoby - rekurencyjnie i iteracyjnie.
Iteracyjny algorytm Euklidesa z odejmowaniem
def nwd_iteracyjnie(a, b):
while a!=b:
if a>b:
a=a-b
else:
b=b-a
return a
a=int(input())
b=int(input())
print(nwd_iteracyjnie(a, b))
Aby zaprogramować algorytm Euklidesa potrzubujemy sworzyć funkcję i umieścić w niej dwa argumenty - liczby, których NWD szukamy.
Następnie tworzymy pętle while, w której umieszczamy warunek sprawdzający, czy liczba a jest różna od b,
jeżeli liczby będą równe to pętla się zakończy, a funkcja zwróci NWD.
Kolejnym krokiem jest stworzenie instrukcji warunkowej if sprawdzającej, która liczba jest większa, abyśmy mogli odjąć
mniejszą z liczb od większej. Pętla będzie powtarzać się dopóki liczby a i b nie będą równe.
Kiedy pętla zakończy się funkcja zwraca wartość a - nie ma różnicy czy zwórci a czy b, gdyż ich wartości są równe.
Zrócona liczba jest równa NWD liczb a i b.
12
30
6
6
9
3
Rekurencyjny algorytm Euklidesa z odejmowaniem
def nwd_rekurencyjnie(a, b):
if a!=b:
if a>b:
return nwd_rekurencyjnie(a-b, a)
else:
return nwd_rekurencyjnie(a, b-a)
return a
a=int(input())
b=int(input())
print(nwd_rekurencyjnie(a, b))
Aby stworzyć funkcję rekurencyjną, która oblicza NWD dwóch liczb potrzebujemy zdefiniować funkcję i umieścić w niej
dwa argumenty - liczby, których NWD szukamy.
Następnie tworzymy instrukcję warunkową if, w której umieszczamy warunek sprawdzający, czy a jest różne od b,
jeżeli będą one równe to funkcja zwróci ich wartość, gdyż NWD tych samych liczb jest im równe.
Kolejnym krokiem jest stworzenie instrukcji warunkowej if sprawdzającej, która liczba jest większa.
Następnie wywołujemy funkcję rekurencyjnie, która wywołuje funkcję dla mniejszej liczb i większej liczb pomniejszonej o mniejszą.
Funkcja będzie się wywoływać dopóki liczby a i b nie będą równe.
12
30
6
6
9
3