NWD, NWW i algorytm Euklidesa
Szybkie i poprawne obliczanie dzielników
NWD, NWW i algorytm Euklidesa to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Dlaczego dzielniki mają znaczenie
Wiele zadań konkursowych opiera się na wspólnych czynnikach dwóch liczb. Najbardziej przydatnym narzędziem jest tutaj NWD, czyli największy wspólny dzielnik. 🔢
Co oznacza NWD
NWD dwóch liczb całkowitych to największa liczba, przez którą obie dzielą się bez reszty. Dla liczb 12 i 18 jest to 6, ponieważ 6 dzieli obie bez reszty.
Powolny sposób
Można sprawdzać wszystkie liczby, zaczynając od mniejszej wartości i schodząc w dół, aż znajdzie się liczba dzieląca obie wartości. To działa, ale jest zdecydowanie zbyt wolne dla dużych danych wejściowych.
Wniosek z algorytmu Euklidesa
Algorytm Euklidesa to szybki sposób obliczania NWD. Jego kluczowa idea mówi, że NWD a i b jest równy NWD b oraz reszty z dzielenia a przez b.
Rekurencja
Należy powtarzać zamianę i operację modulo, aż reszta będzie równa zero. Ostatnia niezerowa wartość to wynik, czyli sam NWD.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aSamodzielna implementacja
Krótka pętla zastępuje parę wartości kolejnymi wartościami, aż b osiągnie zero. Działa to w około log krokach, niezwykle szybko nawet dla ogromnych liczb.
def gcd(a, b):
while b:
a, b = b, a % b
return aKorzystanie ze standardowej biblioteki
Rzadko trzeba implementować ten algorytm ręcznie. Python udostępnia funkcję math.gcd, która jest poprawna, szybka i sama obsługuje argumenty równe zero.
from math import gcd
print(gcd(12, 18))Od NWD do NWW
NWW, czyli najmniejsza wspólna wielokrotność, to najmniejsza liczba podzielna przez obie wartości. Jest bezpośrednio związana z obliczonym przed chwilą NWD.
Wzór na NWW
Należy pomnożyć obie liczby, a następnie podzielić iloczyn przez ich NWD. Zawsze należy najpierw dzielić, aby uniknąć przepełnienia przy bardzo dużych iloczynach.
def lcm(a, b):
return a // gcd(a, b) * bNWD całej listy
Aby obliczyć NWD dla wielu liczb, należy łączyć je parami. Funkcja reduce w Pythonie stosuje math.gcd od lewej do prawej do elementów listy.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Obsługa przypadku zera
Z definicji gcd(a, 0) jest równe a, a gcd(0, 0) jest równe 0. Znajomość tego przypadku brzegowego zapobiega nieprawidłowemu działaniu pętli dla pustych danych wejściowych.
Szybkie sprawdzenie
Proszę potwierdzić podstawowy krok algorytmu Euklidesa.
Podsumowanie
Można już obliczać NWD za pomocą algorytmu Euklidesa w logarytmicznej liczbie kroków, wyznaczać na jego podstawie NWW oraz stosować obie operacje do całej listy. ✅
Ucz się Python dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 30
- Lekcje
- 120
Często zadawane pytania
Czy lekcja „NWD, NWW i algorytm Euklidesa” jest bezpłatna?
Tak — pełny tekst „NWD, NWW i algorytm Euklidesa” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „NWD, NWW i algorytm Euklidesa”?
Szybkie i poprawne obliczanie dzielników Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „NWD, NWW i algorytm Euklidesa”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- NWD, NWW i algorytm Euklidesa
- Testowanie pierwszości do sqrt(n)
- Sito Eratostenesa
- Rozkład na czynniki pierwsze i dzielniki