NWD - Algorytm Euklidesa na Maturze z Informatyki

def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Przykłady użycia
print(nwd(48, 18))   # Wynik: 6
print(nwd(100, 35))  # Wynik: 5
print(nwd(17, 19))   # Wynik: 1 (liczby względnie pierwsze)
print(nwd(1000, 500))# Wynik: 500

Najprostsza i najczęściej używana wersja. Pętla while działa dopóki b nie wyniesie 0. W każdej iteracji zamieniamy miejscami liczby: nowe a staje się starym b (a → b), a nowe b to reszta z dzielenia (b → a % b). Python pozwala na elegancką zamianę miejsc w jednej linii: a, b = b, a % b.

def nwd_rekurencja(a, b):
    if b == 0:
        return a
    return nwd_rekurencja(b, a % b)

# Przykład użycia
print(nwd_rekurencja(48, 18))  # Wynik: 6
print(nwd_rekurencja(100, 35)) # Wynik: 5

Elegancka wersja rekurencyjna - funkcja wywołuje samą siebie z nowymi parametrami, aż b osiągnie 0. Jest krótsza do napisania, ale dla bardzo dużych liczb może być ryzyko przepełnienia stosu wywołań (w praktyce na maturze to nie problem).

#include <iostream>
using namespace std;

int nwd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    cout << nwd(48, 18) << endl;   // Wynik: 6
    cout << nwd(100, 35) << endl;  // Wynik: 5
    cout << nwd(17, 19) << endl;   // Wynik: 1
    return 0;
}

W C++ musimy użyć zmiennej tymczasowej temp, bo nie mamy wygodnej zamiany miejsc jak w Pythonie. Zapisujemy b do temp, potem obliczamy nowe b (reszta z dzielenia), a następnie podstawiamy temp (stare b) do a.

#include <iostream>
using namespace std;

int nwd(int a, int b) {
    if (b == 0) return a;
    return nwd(b, a % b);
}

int main() {
    cout << nwd(48, 18) << endl;  // Wynik: 6
    cout << nwd(100, 35) << endl; // Wynik: 5
    return 0;
}

Wersja rekurencyjna jest krótsza i bardziej elegancka w C++. Całą logikę można zapisać w 2 liniach. Dla matury obie wersje (iteracyjna i rekurencyjna) są równie dobre.