INF.04Algorytmika i Struktury Danych
Algorytm Euklidesa (NWD)
Klasyczny algorytm wyznaczania największego wspólnego dzielnika (NWD) dwóch liczb całkowitych za pomocą operacji reszty z dzielenia (modulo) lub odejmowania.
Wersja optymalna (z resztą z dzielenia modulo):
Dopóki b ≠ 0, zastępuj parę (a, b) parą (b, a mod b). Gdy b = 0, wynikiem jest a.
CSHARP
int NWD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}Obliczanie NWW (Najmniejsza Wspólna Wielokrotność):
NWW(a, b) = (a · b / NWD(a, b))
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Algorytm Euklidesa (NWD) lub rozpocznij trening.