Question

Proszę o napisanie algorytmu Euklidesa,NWW oraz NWD z wyjasnieniem co robi każda linijka

Answer 1

Algorytm Euklidesa jest algorytmem rekurecyjnym, chodziaż można go do formy iteracyjnej.Mając do powiczenia NWD (a,b) sprawdzamy czy b=0. Jeżeli tak jest to NWD (a,b)=a. Jeżeli jednak tak niejest wtedy wywołujemy rkurencyjnie algorytm dla liczby b i reszty z dzielenia a przez b.

przykład:
NWD (243,111)=?
243:111=2 reszta 21
111:21= 5 reszta 6
21:6= 3 reszta 3
6:3= 2 reszta 0
ostatnia niezerowa to nasz wynik: NWD (243,111)=3

Mam nadzieję że pomogłam... proszę o naj...