Rozwiązane

1. Wyjaśnij na przykładzie liczb 36 i 8, dlaczego warunkiem zakończenia algorytmu Euklidesa w wersji odejmowania jest a=b.


2. Czym różni się wersja algorytmu Euklidesa z odejmowaniem od wersji z dzieleniem? Wyjaśnij na przykładzie liczb 36 i 8.


Na dzisiaj!!! Daje naj i 50 punktów więc się opłaca :).

Odpowiedź :

Odpowiedź:

1. Warunkiem zakończenia algorytmu jest a = b, ponieważ NWD dwóch tych samych liczb jest równe właśnie tej liczbie tzn. NWD(a,a) = a

Dla a = 36 i b = 8 od a będziemy odejmować b aż do momentu gdy

a = 4 i b = 8 (bo teraz b >a ) dlatego teraz od b odejmiemy a czyli

a = 4 i b = 4 -> NWD(4,4) = 4

2. Różnica jest taka, że wersja z dzieleniem jest szybsza czyli algorytm będzie bardziej wydajny. I tutaj mała poprawka nie wersja z dzieleniem tylko wersja z resztą z dzielenia:
a = 36 b = 8              36/8 = 4 r.4 (bo 36 = 8*4 + 4)

Teraz zamiast a wpisujemy resztę z dzielenia a przez b:
a = 4  b =8           8/4 = 2 r.0
a = 4  b =0
NWD(4,0) = 4  bo NWD(a,0) = a

Wyjaśnienie:

NWD(a,a) = a

NWD(a,0) = a

Viz Inne Pytanie