NWW (Najmniejsza Wspólna Wielokrotność) na maturę - Szybki algorytm (Python i C++)

Wszyscy znamy NWD (Największy Wspólny Dzielnik), ale na maturze z informatyki bardzo często pojawia się jego "kuzyn" – NWW, czyli Najmniejsza Wspólna Wielokrotność. Co to takiego? Wyobraź sobie dwa koła zębate o różnej liczbie zębów . Zastanawiasz się, po ilu obrotach wrócą do swojej początkowej pozycji? Albo kiedy dwa autobusy o różnych rozkładach jazdy spotkają się ponownie na tym samym przystanku? Do rozwiązania tych problemów służy właśnie NWW.

Z matematycznego punktu widzenia, NWW(a, b) to najmniejsza możliwa liczba naturalna (większa od zera), która dzieli się bez reszty zarówno przez a, jak i przez b.

Kluczowy Wzór: NWW i NWD to najlepsi przyjaciele

Nie musimy wymyślać skomplikowanego algorytmu, który będzie w pętli sprawdzał kolejne wielokrotności. Matematyka przychodzi nam z pomocą! Istnieje piękna i prosta zależność łącząca NWW z NWD (które potrafimy już błyskawicznie liczyć za pomocą Algorytmu Euklidesa):

NWW(a, b) = (a * b) / NWD(a, b)

Oznacza to, że aby policzyć NWW, wystarczy pomnożyć przez siebie obie liczby, a następnie podzielić ten wynik przez ich Największy Wspólny Dzielnik.

Przykład na liczbach:

Weźmy liczby 24 i 36. Chcemy znaleźć najmniejszą liczbę, która dzieli się przez obie z nich.

1. Liczymy NWD(24, 36). Wiemy z algorytmu Euklidesa, że to 12.
2. Podstawiamy do wzoru: NWW(24, 36) = (24 * 36) / 12.
3. Obliczamy: NWW(24, 36) = 864 / 12 = 72.

I rzeczywiście, 72 to pierwsza liczba, która dzieli się bez reszty przez 24 (wynik 3) i przez 36 (wynik 2).

Pułapka na maturze: Przepełnienie zmiennej!

Na szczęście, z matematyki wiemy, że kolejność wykonywania działań możemy sprytnie zmodyfikować. Zamiast najpierw mnożyć, możemy najpierw podzielić jedną z liczb przez NWD (co na pewno da liczbę całkowitą, bo NWD z definicji jest dzielnikiem obu tych liczb!), a dopiero potem pomnożyć przez drugą.

Oto bezpieczna wersja wzoru, której należy używać w kodzie:

NWW(a, b) = (a / NWD(a, b)) * b

Implementacja - Gotowy Kod (Python i C++)

Kluczem do czystego i czytelnego kodu jest odpowiednia organizacja. Definicję funkcji wewnętrznych (pomocniczych), takich jak nasza funkcja NWD, przenosimy wyżej, jeszcze przed funkcją NWW i blokiem głównym programu. Dzięki temu kod jest ułożony logicznie i unika błędów niezadeklarowanych zmiennych w C++.

Kod - Python

# 1. Najpierw funkcja wewnętrzna NWD (algorytm Euklidesa z modulo)
def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 2. Następnie nasza funkcja NWW wykorzystująca bezpieczny wzór
def nww(a, b):
    # Używamy dzielenia całkowitego //, aby uniknąć zmiany typu na float
    return (a // nwd(a, b)) * b

# --- Główna część programu ---
liczba1 = 24
liczba2 = 36

wynik = nww(liczba1, liczba2)
print(f"NWW({liczba1}, {liczba2}) = {wynik}")

Kod - C++

#include <iostream>
using namespace std;

// 1. Definiujemy pomocniczą funkcję NWD wyżej
long long nwd(long long a, long long b) {
    while (b != 0) {
        long long pom = b;
        b = a % b;
        a = pom;
    }
    return a;
}

// 2. Funkcja NWW z bezpieczną kolejnością działań
long long nww(long long a, long long b) {
    return (a / nwd(a, b)) * b;
}

int main() {
    // Używamy long long dla pewności, że wynik zmieści się w pamięci
    long long a, b;
    
    cout << "Podaj dwie liczby: ";
    cin >> a >> b;
    
    cout << "NWW(" << a << ", " << b << ") = " << nww(a, b) << endl;
    
    return 0;
}

Kiedy wykorzystasz NWW na maturze?

Wyszukiwanie Najmniejszej Wspólnej Wielokrotności pojawia się na egzaminie w kilku konkretnych kontekstach:

• Dodawanie i odejmowanie ułamków: Gdy musisz sprowadzić ułamki z pliku do wspólnego mianownika (np. by sprawdzić, który wynik jest największy), optymalnym wspólnym mianownikiem jest właśnie NWW obu starych mianowników.
• Zadania cykliczne: Kiedy w zadaniu masz dwie maszyny produkujące detale co różną liczbę sekund, NWW odpowie Ci na pytanie: "W której sekundzie obie maszyny wyrzucą detal w tym samym momencie?".
• Szyfrowanie i algorytmy kluczy: W zadaniach zahaczających o kryptografię (np. wczesne kroki do algorytmu RSA) pojęcia NWD i NWW pojawiają się notorycznie.

NWW dla więcej niż dwóch liczb?

A co, jeśli musisz policzyć NWW dla trzech liczb: a, b, c? Nie musisz pisać nowej, skomplikowanej funkcji. NWW posiada własność łączności. Wystarczy policzyć NWW dla pierwszych dwóch, a potem użyć tego wyniku z trzecią liczbą!

nww_trzech = nww(nww(a, b), c)

Podsumowanie - Twoja Checklista

• Aby napisać NWW, zawsze potrzebujesz funkcji NWD.
• Definiuj funkcje wewnętrzne (takie jak NWD) wyżej w kodzie, by utrzymać logiczny układ programu.
• Używaj bezpiecznego wzoru zapobiegającego przepełnieniu: (a / NWD(a, b)) * b.
• W C++ deklaruj zmienne i zwracany typ funkcji jako long long, bo wyniki wielokrotności bardzo szybko rosną.

Szukasz więcej praktyki i zadań typu "cyklicznego"? Sprawdź pełny kurs do matury z informatyki.