Lekcja programowania: Algorytm Euklidesa w Python

Utworzono: 16-04-2021

Docelową formą prezentacji algorytmu jest język wysokiego poziomu. Wybrałem Pythona ze względu na prostotę i rosnącą popularność  zarówno na rynku jak i w edukacji. W Python  można tworzyć algorytmy na maturze. Do kodu dodałem zmienną licznik, która nie ma bezpośredniego związku z algorytmem Euklidesa , ale jej zadaniem będzie policzenie ilości przebiegu pętli wskazującej NWD . Sprawdzimy w ten sposób wydajność obu wersji algorytmu.

Kod Python algorytmu Euklidesa  -  wyznaczanie NWD metodą przez odejmowanie.

  1. liczba1=int(input('podaj pierwszą liczbę: '))
  2. liczba2=int(input('podaj drugą liczbę: '))
  3. licznik=0

#  początek pętli

  1. while liczba1!=liczba2:
  2.     licznik+=1
  3.     if liczba1>liczba2:
  4.         liczba1=liczba1-liczba2 
  5.     else:
  6.         liczba2=liczba2-liczba1

#  koniec pętli

  1. print ("pętla wykonana {} razy".format(licznik))
  2. print("NWD to:", liczba1 )

Wyjaśnienie poszczególnych linii kodu:

  1. Wczytuję z klawiatury zmienną liczba1. Funkcja input wyświetla komunikat i czeka na wprowadzenie wartości. Funkcja int zamienia wprowadzoną wartość (domyślnie string) na liczbę typu integer.
  2. Jak w pk.1 ze zmienną liczba2.
  3. Tworzę zmienną licznik z wartością początkową O po to aby sprawdzić wydajność algorytmu. Zmienna będzie zliczała przebiegi pętli.
  4. Początek pętli dopóki liczba1 jest różna od liczba2 (!= operator nie są sobie równe).
  5. Dodaję 1 do wartości zmiennej licznik, jest to skrót zapisu licznik = licznik+1.
  6. Początek instrukcji warunkowej jeżeli liczba1 jest większa od liczba2.
  7. Jeżeli warunek z pk. 6 jest spełniony podstaw do liczba1 wartość liczba1-liczba2.
  8. W przeciwnym wypadku (do warunku z pk6).
  9. Jeżeli warunek z pk. 6 nie jest spełniony, podstaw do liczba2 wartość liczba2-liczba1.
    Koniec pętli.
  10. Wyprowadź na ekran komunikat, zastosowałem funkcję format, która wstawi wartość zmiennej licznik do nawiasu {}.
  11. Wyprowadź wartość NWD. Można byłoby użyć funkcji format. Kod tej linijki wyglądałby tedy tak: print("NWD to : {}".format(liczba1) ).

Kod Python algorytmu Euklidesa  -  wyznaczanie NWD metodą przez dzielenie.

  1. liczba1=int(input('podaj pierwszą liczbę: '))
  2. liczba2=int(input('podaj drugą liczbę: '))
  3. licznik=0
  4. if liczba2==0:
  5.   print("NWD to:",liczba1)
  6.   else:

# początek pętli

  1.   while liczba2>0:
  2.     licznik+=1
  3.     reszta=liczba1%liczba2
  4.     liczba1=liczba2
  5.     liczba2=reszta

# koniec pętli

  1. print("pętla wykonana {} razy".format(licznik))
  2. print("najwiekszy wspolny dzielnik to:",liczba1)

Wyjaśnienie poszczególnych linii kodu:

  1. Wczytuję z klawiatury zmienną liczba1. Funkcja input wyświetla komunikat i czeka na wprowadzenie wartości. Funkcja int zamienia wprowadzoną wartość (domyślnie string) na liczbę typu integer.
  2. Jak w pk.1 ze zmienną liczba2.
  3. Tworzę zmienną licznik z wartością początkową O po to aby sprawdzić wydajność algorytmu. Zmienna będzie zliczała przebiegi pętli.
  4. Jeżeli liczba 2 jest równa 0 to przejdź do pk.5.
  5. Wyprowadź komunikat NWD to : wartość liczba1.
  6. W przeciwnym wypadku przejdź do pk.7.
  7. Początek pętli dopóki liczba2 jest większa od O.
  8. Dodaję 1 do wartości zmiennej licznik, jest to skrót zapisu licznik = licznik+1.
  9. Wstawiam do zmiennej reszta, resztę z dzielenia liczba1 przez liczba 2 (% operator modulo)
  10. Wstawiam wartość zmiennej liczba2 do liczba1
  11. Wstawiam wartość zmiennej reszta do liczba2
    Koniec pętli.
  12. Wyprowadź na ekran komunikat, zastosowałem funkcję format, która wstawi wartość zmiennej licznik do nawiasu {}.
  13. Wyprowadź wartość NWD. Można byłoby użyć funkcji format. Kod tej linijki wyglądałby tedy tak: print("NWD to : {}".format(liczba1) ).

Algorytm metodą przez odejmowanie wykona dla pary liczb 123456789 i 2 pętlę 61728395 razy, a algorytm metodą przez dzielenie dla tej samej pary liczb wyświetli wartość 2 licznika pętli.

Czas działania algorytmu bazującego na metodzie przez odejmowanie przy dużych liczbach jest znaczący, wykonanie takiej ilości operacji musi trwać.

Zapraszam na warsztaty z cyklu jaku uczyć programowania organizowane przez nasz ośrodek.

Marek Wróblewski
m.wroblewski@odn.slupsk.pl