Algorytm Euklidesa — NWD i NWW

Algorytm Euklidesa to jeden z najstarszych i najbardziej eleganckich algorytmów w informatyce, służący do wyznaczania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych. Jego analiza na maturze rozszerzonej z informatyki łączy elementy matematyki dyskretnej z praktyką programistyczną — implementacją iteracyjną i rekurencyjną.

Lekcja przedstawia dwie wersje algorytmu. Wersja z odejmowaniem opiera się na własności matematycznej $NWD(a,b)=NWD(a-b,b)$ dla $a>b$ — zastępujemy większą liczbę różnicą większej i mniejszej, powtarzając operację, aż obie liczby staną się równe. Wersja z modulo (znacznie efektywniejsza dla dużych liczb) zastępuje parę $(a,b)$ parą $(b,a<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>b)$, dopóki $b\mathrm{\ne }0$ — wynikiem jest wtedy wartość $a$. Uczeń ćwiczy ręczne obliczanie NWD dla konkretnych par liczb, np. $NWD(1071,462)=21$, krok po kroku śledząc kolejne dzielenia z resztą.

Materiał szczegółowo wyjaśnia zależność między NWD a najmniejszą wspólną wielokrotnością (NWW): iloczyn dwóch liczb jest zawsze równy iloczynowi ich NWD i NWW, skąd wynika praktyczny wzór $NWW(a,b)=\frac{a\cdot b}{NWD(a,b)}$ — pozwalający obliczyć NWW bez konieczności rozkładu liczb na czynniki pierwsze.

Ważnym elementem jest analiza złożoności obliczeniowej — algorytm Euklidesa ma złożoność logarytmiczną względem wartości wejściowych, co czyni go niezwykle wydajnym nawet dla bardzo dużych liczb, w przeciwieństwie do naiwnego podejścia wypisywania wszystkich dzielników. Uczeń poznaje też przypadki brzegowe, np. $NWD(0,b)=b$, oraz definicję liczb względnie pierwszych — takich, których NWD wynosi dokładnie 1 (co nie oznacza, że muszą to być liczby pierwsze, np. 8 i 9 są względnie pierwsze).

Materiał obejmuje obie implementacje: iteracyjną (za pomocą pętli while) oraz rekurencyjną (funkcja wywołująca samą siebie z nowymi argumentami), z warunkiem bazowym rekurencji przy osiągnięciu reszty równej zero.

Ten zestaw pytań i fiszek buduje solidne podstawy zarówno teorii liczb, jak i praktycznej implementacji jednego z najważniejszych algorytmów klasycznych — regularnie pojawiającego się na egzaminie maturalnym z informatyki.

• Uczeń opisuje zasadę działania algorytmu Euklidesa w wersji z odejmowaniem i z modulo
• Uczeń oblicza ręcznie NWD dla konkretnych par liczb metodą dzielenia z resztą
• Uczeń zna i stosuje wzór wiążący NWD i NWW: NWW(a,b) = (a·b)/NWD(a,b)
• Uczeń rozumie złożoność logarytmiczną algorytmu Euklidesa
• Uczeń zna definicję liczb względnie pierwszych (NWD=1)
• Uczeń rozróżnia iteracyjną i rekurencyjną implementację algorytmu
• Uczeń rozpoznaje przypadki brzegowe, np. NWD(0, b) = b

Materiał tematyczny (bez dokumentu źródłowego): algorytmy — iteracyjne i rekurencyjne metody obliczania NWD (największego wspólnego dzielnika) i NWW (najmniejszej wspólnej wielokrotności), algorytm Euklidesa, analiza kroków algorytmu dla konkretnych par liczb, zgodnie z zakresem matury rozszerzonej z informatyki.