Jak policzyć NWW dwóch liczb – intuicyjnie przez wielokrotności i szybko ze wzoru z NWD.
Najmniejsza wspólna wielokrotność liczb a i b (w skrócie NWW) to najmniejsza dodatnia liczba, która dzieli się jednocześnie przez a i przez b. Na przykład NWW(4, 6) = 12, bo 12 to pierwsza liczba, którą da się podzielić i przez 4, i przez 6.
Sposób „szkolny" – wypisz wielokrotności. Piszemy po kolei wielokrotności obu liczb i szukamy pierwszej wspólnej. Dla 4: 4, 8, 12, 16, …; dla 6: 6, 12, 18, …. Pierwsza, która pojawia się w obu ciągach, to 12. To bardzo poglądowe, ale dla dużych liczb bywa wolne.
Sposób szybki – przez NWD. W programach liczymy NWW ze wzoru:
NWW(a, b) = (a · b) / NWD(a, b)
gdzie NWD to największy wspólny dzielnik. Najpierw liczymy NWD (najlepiej algorytmem Euklidesa), a potem dzielimy przez niego iloczyn a · b. Dzięki temu wynik dostajemy w kilku krokach, nawet dla dużych liczb.
Dlaczego ten wzór działa? Iloczyn a · b na pewno jest wspólną wielokrotnością (dzieli się przez obie liczby), ale zwykle za dużą. Dzieląc go przez to, co obie liczby mają wspólne (czyli NWD), usuwamy nadmiar i dostajemy właśnie najmniejszą wspólną wielokrotność.
Na maturze: klasyka. Zwykle trzeba samodzielnie napisać nwd, a nww policzyć ze wzoru – nie wolno używać funkcji wbudowanych.
Prześledź krok po kroku najprostszą metodę na NWW: wypisywanie wielokrotności. Dokładamy kolejną wielokrotność zawsze po tej stronie, która jest w danej chwili mniejsza. Pierwsza liczba, która pojawi się w obu rzędach naraz, to najmniejsza wspólna wielokrotność.
Naciśnij „Krok", aby dołożyć kolejną wielokrotność, albo „Auto".
funkcja nwd(a, b): dopóki b ≠ 0: pomocnicza ← b b ← a mod b a ← pomocnicza zwróć a funkcja nww(a, b): // najpierw dzielimy, żeby iloczyn nie urósł za bardzo zwróć (a div nwd(a, b)) * b
def nwd(a, b):
"""Największy wspólny dzielnik – algorytm Euklidesa."""
while b != 0:
a, b = b, a % b
return a
def nww(a, b):
"""Najmniejsza wspólna wielokrotność ze wzoru a*b / NWD."""
return a // nwd(a, b) * b # najpierw dzielenie, potem mnożenie
# Przykłady użycia
print(nww(4, 6)) # Wynik: 12
print(nww(12, 18)) # Wynik: 36
print(nwd(48, 36)) # Wynik: 12#include <iostream>
using namespace std;
long long nwd(long long a, long long b) {
while (b != 0) {
long long pom = b;
b = a % b;
a = pom;
}
return a;
}
long long nww(long long a, long long b) {
return a / nwd(a, b) * b; // najpierw dzielenie, potem mnożenie
}
int main() {
cout << nww(4, 6) << "\n"; // Wynik: 12
cout << nww(12, 18) << "\n"; // Wynik: 36
}NWD to największa liczba, która dzieli obie liczby (szukamy „w dół"). NWW to najmniejsza liczba, którą obie liczby dzielą (szukamy „w górę"). To dwa różne pytania o tę samą parę liczb.
Bo to szybkie i pewne. Wypisywanie wielokrotności działa, ale dla dużych liczb trwa długo. Wzór a · b / NWD daje wynik od razu, w kilku krokach.
Tak – NWW prawie zawsze liczy się przez NWD, a NWD najwygodniej policzyć właśnie Euklidesem. Bez niego zostaje wolniejsze wypisywanie wielokrotności.
Zapis (a * b) / nwd przy dużych liczbach – iloczyn potrafi przekroczyć zakres typu. Dziel najpierw, mnóż potem.
Policz NWW i wpisz wynik, potem kliknij Sprawdź.
NWW(4, 6) to , NWW(3, 5) to , a NWW(6, 8) to .
Uzupełnij tabelę:
| Para liczb | NWW |
|---|---|
| 2 i 7 | |
| 5 i 10 | |
| 9 i 6 |
We wzorze NWW(a, b) = (a · b) / X w miejsce X wstawiamy .
O(log min(a,b))O(1)Cały czas pracy zjada policzenie NWD algorytmem Euklidesa, a to działa w czasie O(log min(a, b)) – w każdym kroku reszta szybko maleje. Samo podstawienie do wzoru to jedno mnożenie i jedno dzielenie. Pamięci używamy stałą ilość, czyli O(1).
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: