Jak wiesz z poprzedniej lekcji, NWD dwóch liczb możemy policzyć za pomocą algorytmu Euklidesa
z odejmowaniem. Na dzisiejszej lekcji poznasz trochę szybszy algorytm - algorytm Euklidesa z
użyciem reszty z dzielenia. Sposób z użyciem modulo, nie różni się zbytnio od tego z odejmowaniem,
ale znacznie przyspiesza jego działanie. Wynika to z tego, że wielokrotne odejmowanie w tym algorytmie
jest zastępowane działaniem reszty z dzielenia, które wykonujemy tylko jeden raz.
Algorytm ten możemy napisać na dwa sposoby - rekurencyjnie i iteracyjnie.
Iteracyjny algorytm Euklidesa z modulo
def nwd_iteracyjnie(a,b):
while b!=0:
c=b
b=a%b
a=c
return a
a=int(input())
b=int(input())
print(nwd_iteracyjnie(a, b))
Tworzymy funkcje i umieszczamy w niej dwa argumenty - liczby, których NWD szukamy.
Następnie tworzymy pętle while, w której umieszczamy warunek sprawdzający, czy b jest równa od 0,
w przeciwnym wypadku funkcja zwróci wartość a, gdyż NWD liczby a i 0 jest równe a.
Kolejnym krokiem jest stworzenie zmiennej pomocniczej c, która przechowa dla nas wartość b, po to aby
móc ją później przypisać zmiennej a. Zmienna b przyjmuje nową wartość - resztę z dzielenia a przez b.
Taki algorytm działa, gdyż NWD(a, b)=NWD(a%b, b).
12
30
6
6
9
3
Rekurencyjny algorytm Euklidesa z modulo
def nwd_rekurencyjnie(a, b):
if(b!=0):
return nwd_rekurencyjnie(b,a%b)
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ą, w której umieszczamy warunek sprawdzający, czy b jest różne od 0,
jeżeli będzie ono równe 0 to funkcja zakończy swoje działanie i zwróci a, gdyż NWD(a, 0)=a.
Kolejnym krokiem jest odłowanie się rekurencyjnie do funkcji, ale o mniejszych argumentach.
Funkcja będzie się tak długo wywoływać, aż b osiągnie wartość 0.
12
30
6
6
9
3