Algorytm Euklidesa — zadania w Pythonie

Algorytm Euklidesa wyznacza największy wspólny dzielnik (NWD) dwóch liczb i jest jednym z najstarszych algorytmów, które wciąż się stosuje. Na lekcji uczniowie porównują dwie wersje — z odejmowaniem i z resztą z dzielenia — liczą kroki i widzą, dlaczego druga jest szybsza. Przy okazji powtarzają pętlę while.

Scenariusz jest przeznaczony na 45 minut dla klasy znającej pętle i funkcje. Pasuje do lekcji algorytmiki w liceum, na przykład po sortowaniu bąbelkowym.

Przygotowanie stanowisk

Potrzebny jest Python 3 i edytor lub IDLE. Rozpakuj pakiet z sekcji materiałów do osobnego folderu. Program uruchomisz przez Run → Run Module albo poleceniem python start.py, python3 start.py lub py start.py.

Cele i plan lekcji

Po zajęciach uczeń potrafi:

• wykonać algorytm Euklidesa na kartce i zapisać kolejne kroki;
• zapisać obie wersje algorytmu w Pythonie;
• porównać liczbę kroków dla małych i dużych liczb;
• wyznaczyć najmniejszą wspólną wielokrotność (NWW) ze wzoru z NWD.

Wersja z odejmowaniem

a = 48
b = 18
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
print("NWD =", a)

Idea: NWD dwóch liczb się nie zmienia, gdy od większej odejmiemy mniejszą. Dla 48 i 18 kolejne pary to (30, 18), (12, 18), (12, 6), (6, 6) — program kończy, gdy liczby się zrównają, i wypisuje NWD = 6. Zapis na kartce wygląda tak samo, więc uczniowie łatwo porównują swoje wyniki z programem.

Wersja z resztą z dzielenia

Wiele odejmowań można zastąpić jednym dzieleniem z resztą: w pętli podstawiamy a, b = b, a % b, aż b będzie równe 0. Wtedy NWD to a. Dla 48 i 18: (48, 18) → (18, 12) → (12, 6) → (6, 0), czyli trzy kroki zamiast czterech. Różnica robi się bardzo duża dla liczb różniących się rzędem wielkości.

NWW dwóch dodatnich liczb to a · b / NWD(a, b); w Pythonie piszemy a * b // nwd, żeby dostać liczbę całkowitą.

Trzy zadania

Zadanie 1. Odejmowanie. Napisz funkcję nwd_odejmowanie(a, b) zwracającą parę (NWD, liczba kroków). Sprawdź (48, 18) i (35, 14).

Zadanie 2. Reszta. Napisz nwd_reszta(a, b) zwracającą tę samą parę. Porównaj liczbę kroków obu wersji dla (1071, 462).

Zadanie 3. NWW. Napisz nww(a, b) korzystającą z NWD. Sprawdź (12, 18) i (4, 9) oraz NWD dla liczb względnie pierwszych (17, 5) i dla pary (0, 7).

Dla chętnych: napisz funkcję skroc(licznik, mianownik) skracającą ułamek i sprawdź ją na 18/48, 7/21 i 5/9.

Rozwiązanie i wyniki

def nwd_odejmowanie(a, b):
    kroki = 0
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
        kroki = kroki + 1
    return a, kroki


def nwd_reszta(a, b):
    kroki = 0
    while b != 0:
        a, b = b, a % b
        kroki = kroki + 1
    return a, kroki


# Zadanie 1
print(nwd_odejmowanie(48, 18))
print(nwd_odejmowanie(35, 14))

# Zadanie 2
print(nwd_reszta(48, 18))
print(nwd_reszta(1071, 462))
print(nwd_odejmowanie(1071, 462))

# Zadanie 3
def nww(a, b):
    return a * b // nwd_reszta(a, b)[0]


print(nww(12, 18), nww(4, 9))
print(nwd_reszta(17, 5)[0], nwd_reszta(0, 7)[0])

Program wypisze:

(6, 4)
(7, 3)
(6, 3)
(21, 3)
(21, 11)
36 36
1 7

Dla (48, 18) wersja z odejmowaniem robi 4 kroki, a wersja z resztą 3. Dla (1071, 462) odejmowanie wymaga aż 11 kroków, a reszta — tylko 3, co dobrze pokazuje przewagę drugiej wersji (liczby zweryfikowano uruchomieniem programu). Liczby względnie pierwsze mają NWD równe 1, a nwd_reszta(0, 7) daje 7. Uwaga: wersja z odejmowaniem nie działa dla zera, bo pętla nigdy by się nie zakończyła — dlatego w zadaniu 3 używamy wersji z resztą. Zadanie dla chętnych (rozszerzenie.py) wypisuje:

(3, 8) (1, 3) (5, 9)

Typowe błędy

Pytania kontrolne i punktacja

1. Ile wynosi NWD(36, 24)?
2. Podaj pierwsze dwa kroki algorytmu z resztą dla (36, 24).
3. Co znaczy, że liczby są względnie pierwsze?

Odpowiedzi: 12. (36, 24) → (24, 12) → (12, 0), więc pierwszy krok to (24, 12), drugi (12, 0). Ich NWD wynosi 1.

Proponowana punktacja (razem 10 punktów): zadanie 1 — pętla i wynik 2 pkt, liczba kroków 1 pkt; zadanie 2 — pętla z resztą 2 pkt, porównanie kroków 1 pkt; zadanie 3 — wzór NWW 2 pkt, wyniki dla par 2 pkt. Zadanie dla chętnych nie jest wymagane do pełnej oceny.

Materiały do pobrania

• Pakiet Python: plik startowy, rozwiązanie, rozszerzenie i karta pracy
• Karta pracy ucznia — otwórz i wydrukuj

Rozpakuj ZIP przed otwarciem skryptów. Materiały są dostępne bez logowania; publiczne rozwiązanie służy nauce i samodzielnemu sprawdzeniu, a nie poufnemu sprawdzianowi.

Co dalej po algorytmie Euklidesa?

Następne tematy to liczby pierwsze, rekurencyjna wersja algorytmu i złożoność obliczeniowa. Ten materiał rozwija dział o algorytmach w kursie Informatyka w TablicaPro, gdzie znajdziesz prezentacje, ćwiczenia i testy do prowadzenia lekcji.

Źródła techniczne: algorytm Euklidesa w Wikipedii oraz pętla while w tutorialu Pythona. Zobacz też lekcję o instrukcjach warunkowych.