Rozwiąż quiz: Algorytm Euklidesa — NWD i NWW | Zestly

Question 1

Jaka jest podstawowa zasada działania algorytmu Euklidesa w wersji z odejmowaniem dla dwóch liczb naturalnych $a$ i $b$?

Accepted Answer

Zastępujemy większą liczbę różnicą większej i mniejszej, aż obie liczby będą równe.

Answer

Dodajemy mniejszą liczbę do większej, aż obie będą równe.

Answer

Dzielimy iloczyn liczb przez ich sumę.

Answer

Szukamy największego dzielnika wspólnego poprzez wypisanie wszystkich dzielników obu liczb.

Question 2

Wybierz poprawne stwierdzenia dotyczące zależności między $NWD(a, b)$ a $NWW(a, b)$ dla liczb naturalnych $a, b > 0$.

Accepted Answer

$NWD(a, b) \cdot NWW(a, b) = a \cdot b$

Accepted Answer

$NWW(a, b) = \frac{a \cdot b}{NWD(a, b)}$

Answer

$NWW(a, b) = \frac{a \cdot b}{a + b}$

Answer

$NWD(a, b) = NWW(a, b)$ dla dowolnych liczb $a, b$

Question 3

Które z poniższych cech charakteryzują rekurencyjną implementację algorytmu Euklidesa?

Accepted Answer

Wywołuje samą siebie z nowymi argumentami.

Accepted Answer

Warunek stopu następuje, gdy jedna z liczb wynosi 0.

Answer

Wymaga zawsze użycia stosu o rozmiarze $O(n^2)$.

Answer

Jest zawsze wolniejsza od wersji iteracyjnej.

Question 4

Jaki jest wynik $NWD(1071, 462)$ obliczony algorytmem Euklidesa?

Answer

7

Answer

14

Answer

21

Answer

42

Question 5

Co się stanie, jeśli w algorytmie Euklidesa (wersja z modulo) jako argumenty podamy $a=0$ oraz $b=5$?

Answer

Algorytm zwróci 5.

Answer

Algorytm zwróci 0.

Answer

Wystąpi błąd dzielenia przez zero.

Answer

Algorytm wpadnie w pętlę nieskończoną.