Lekcja programowania: Algorytm Euklidesa w Python

Fragment podstawy programowej z informatyki klas VII i VIII:

1. Rozumienie, analizowanie i rozwiązywanie problemów. Uczeń:

1. Stosuje różne sposoby przedstawiania algorytmów, w tym w języku naturalnym, w postaci schematów blokowych, listy kroków;
2. stosuje przy rozwiązywaniu problemów podstawowe algorytmy:

1. na liczbach naturalnych: bada podzielność liczb, wyodrębnia cyfry danej liczby, przedstawia działanie algorytmu Euklidesa w obu wersjach iteracyjnych (z odejmowaniem i z resztą z dzielenia),
2. wyszukiwania i porządkowania: wyszukuje element w zbiorze uporządkowanym i nieuporządkowanym oraz porządkuje elementy w zbiorze metodą przez proste wybieranie i zliczanie;

 

Podstawa programowa z informatyki podkreśla znaczenie algorytmicznego myślenia. Algorytm Euklidesa poszukiwania największego wspólnego dzielnika dwóch liczb naturalnych (NWD), jako jedyny jest wymieniony z nazwy w podstawie programowej klas VII i VIII. Jego realizacja w obu wersjach iteracyjnych, metodą przez odejmowanie i metodą przez dzielenie, jest obowiązkowa. Z zapisów podstawy programowej wynika, że uczeń powinien stosować różne sposoby przedstawiania algorytmów w tym w postaci schematów blokowych – to zagadnienie zostało przeze mnie  omówione   w poprzednich wydaniach Informatora Oświatowego (schemat blokowy –nr 2/2021, implementacje w Sctatch –nr 3/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 programistycznym i w edukacji. W Python można rozwiązywać zadania algorytmiczne 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

4. while liczba1!=liczba2:
5.     licznik+=1
6.     if liczba1>liczba2:
7.         liczba1=liczba1-liczba2 
8.     else:
9.         liczba2=liczba2-liczba1

#  koniec pętli

10. print ("pętla wykonana {} razy".format(licznik))
11. 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

7.   while liczba2>0:
8.     licznik+=1
9.     reszta=liczba1%liczba2
10.     liczba1=liczba2
11.     liczba2=reszta

# koniec pętli

12. print("pętla wykonana {} razy".format(licznik))
13. 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) ).

Porównajmy wydajność algorytmu metodą przez odejmowanie i przez dzielenie.

Dla  pary liczb:

• liczba1: 123456789  
• liczba2: 2,

 

 

Pętla wskazująca NWD zostanie wykonana:

• przy zastosowaniu metody przez odejmowanie : 61728395 razy,
• przy zastosowaniu metody przez dzielenie : 2 razy.

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

Zapraszam na  warsztaty z cyklu jak uczyć programowania organizowana w naszym ośrodku doskonalenia.

 

Marek Wróblewski

marek.wroblewski@podn.slupsk.pl