Przystąp do egzaminu: Algorytm Euklidesa — NWD i NWW | Zestly

Question 1

Wybierz poprawne właściwości algorytmu Euklidesa.

Accepted Answer

Jest bardzo efektywny czasowo.

Accepted Answer

Działa dla dowolnych liczb całkowitych dodatnich.

Accepted Answer

Może być zaimplementowany iteracyjnie.

Answer

Wymaga wcześniejszego rozkładu liczb na czynniki pierwsze.

Question 2

Jeśli $NWD(a, b) = 1$, to co można powiedzieć o liczbach $a$ i $b$?

Accepted Answer

Są to liczby względnie pierwsze.

Answer

Są to liczby pierwsze.

Answer

Jedna z nich musi być równa 1.

Answer

Są to liczby parzyste.

Question 3

Jaka jest złożoność obliczeniowa algorytmu Euklidesa dla dwóch liczb $a$ i $b$?

Accepted Answer

Logarytmiczna względem wartości liczb.

Answer

Liniowa względem wartości liczb.

Answer

Wykładnicza.

Answer

Stała.

Question 4

Które z poniższych operacji są poprawne w iteracyjnej wersji algorytmu Euklidesa?

Answer

while $b 
eq 0$: $temp = b; b = a \pmod{b}; a = temp$

Answer

while $a 
eq b$: $a = a + b$

Answer

while $b > 0$: $a, b = b, a \pmod{b}$

Answer

while $a > 0$: $a = a - 1$

Question 5

Oblicz $NWW(12, 18)$ przy użyciu $NWD(12, 18)$.

Answer

12

Answer

24

Answer

36

Answer

72