średni NWDrekurencjamatura rozszerzona z informatyki

NWD – algorytm Euklidesa

Wyznacza największy wspólny dzielnik dwóch liczb metodą Euklidesa z modulo lub odejmowaniem.

Opis

Algorytm Euklidesa to jeden z najstarszych znanych algorytmów (ok. 300 r. p.n.e.). Służy do wyznaczania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych.

Wersja klasyczna (z odejmowaniem): jeżeli a = b, to NWD to a. W przeciwnym wypadku odejmujemy mniejszą liczbę od większej i powtarzamy proces.

Wersja zoptymalizowana (z modulo): zamiast wielokrotnie odejmować, wykonujemy a mod b. To znacznie szybsze, szczególnie gdy jedna liczba jest dużo większa od drugiej.

Powiązanie: mając NWD, łatwo policzyć NWW (najmniejszą wspólną wielokrotność) ze wzoru NWW(a, b) = a · b / NWD(a, b).

Na maturze: NWD pojawia się bardzo często – w zadaniach o ułamkach, podzielności, wspólnych dzielnikach, rozkładzie na czynniki pierwsze.

Pseudokod

// Wersja iteracyjna z modulo
funkcja NWD(a, b):
  dopóki b ≠ 0:
    reszta ← a mod b
    a ← b
    b ← reszta

  zwróć a


// Wersja klasyczna z odejmowaniem
funkcja NWD_odejmowanie(a, b):
  dopóki a ≠ b:
    jeżeli a > b:
      a ← a - b
    w przeciwnym razie:
      b ← b - a

  zwróć a

Implementacja w Pythonie i C++

def nwd(a, b):
    """NWD – algorytm Euklidesa z modulo (wersja iteracyjna)."""
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a


def nwd_rekurencyjnie(a, b):
    """NWD – wersja rekurencyjna."""
    if b == 0:
        return abs(a)
    return nwd_rekurencyjnie(b, a % b)


def nwd_odejmowanie(a, b):
    """NWD – wersja klasyczna (z odejmowaniem) - wolniejsza."""
    a, b = abs(a), abs(b)
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    return a


def nww(a, b):
    """NWW liczone na podstawie NWD."""
    return abs(a * b) // nwd(a, b)


# Przykłady
print(nwd(48, 18))                  # 6
print(nwd_rekurencyjnie(252, 105))  # 21
print(nww(12, 18))                  # 36

#include <iostream>
using namespace std;

long long nwd(long long a, long long b) {
    a = (a < 0) ? -a : a;
    b = (b < 0) ? -b : b;
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

long long nww(long long a, long long b) {
    return (a / nwd(a, b)) * b;
}

int main() {
    cout << nwd(48, 18)   << "\n";  // 6
    cout << nwd(252, 105) << "\n";  // 21
    cout << nww(12, 18)   << "\n";  // 36
}

Złożoność obliczeniowa

ModuloO(log min(a,b))

OdejmowanieO(max(a,b))

PamięciowaO(1)

↗

Powiązane zagadnienia

Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem:

NWW – Najmniejsza Wspólna WielokrotnośćLiczby Ciąg Fibonacciego (rekurencyjny)Ciągi Dzielniki liczbyLiczby Konwersja binarno-dziesiętnaLiczby Konwersja dziesiętno-binarnaLiczby Rozkład na czynniki pierwszeLiczby