Powtórka: Algorytm Euklidesa

Algorytm Euklidesa

Metoda obliczania największego wspólnego dzielnika (NWD) dwóch liczb całkowitych.

Największy wspólny dzielnik (NWD)

Największa liczba, która dzieli obie liczby bez reszty.

Zastosowanie algorytmu

Używany w matematyce i informatyce, np. w redukcji ułamków.

Rekurencyjna wersja algorytmu

Oblicza NWD, stosując $\displaystyle NWD(a, b) = NWD(b, a \bmod b)$.

Iteracyjna wersja algorytmu

Zastosowanie pętli do obliczenia NWD zamiast rekurencji.

Złożoność czasowa

Algorytm Euklidesa ma złożoność czasową $\displaystyle O(log(min(a, b)))$.

Prawda czy fałsz: NWD(0, b) = b

Prawda, ponieważ zero nie wpływa na dzielenie.

Prawda czy fałsz: NWD(a, 0) = a

Prawda, ponieważ każda liczba dzieli samą siebie.

Jakie są dwie metody obliczania NWD?

Rekurencyjna i iteracyjna.

Różnica między NWD a NWW

NWD to największy wspólny dzielnik, a NWW to najmniejsza wspólna wielokrotność.

Uzupełnij zdanie: NWD(a, b) = ...

$\displaystyle NWD(b, a \\bmod b)$.

Które NIE jest przykładem zastosowania algorytmu?

Obliczanie sumy dwóch liczb.