[Algorytmy] Algorytm Euklidesa - rekurencja

[sandra-91]

Jest podany algorytm Euklidesa:

Kod: Zaznacz cały

while a <> b
    do if a > b
          then a <-- a − b
          else b <-- b − a
return a

Zadaniem jest go zapisać jako rekurencyjnie.



Ja bym tak to zapisała:

Kod: Zaznacz cały

if a<>b
  if a>b
    return nwd(a-b,b)
  else
    return nwd(b-a,a)
return a

A wzór wyglądałby tak:

\(\displaystyle{ (a,b) = \begin{cases} a, \hbox{ dla } b=0 \\ (a-b, b), \hbox{ dla } b>0 \\ \end{cases}}\)

Jest ok.?

Na końcu mam pytanie, ten pierwszy algorytm jest napisany iteracyjnie?
-------
EDIT:

Jeszcze jedno, jak zapisać ten algorytm w postaci \(\displaystyle{ T(n)}\) czyli liczbę porównań?

[Rjiuk]

Mam nadzieję iż albo znalazlaś już odp. albo moja coś ci pomoże.

Jeżeli możesz modulować ( a raczej tak jest ) to lepiej zrobić

\(\displaystyle{ (a,b)=\begin{cases} a &\text{dla } b = 0\\(b,b \mod a) &\text{dla } b>0 \end{cases}}\)
No dobra , pytanie dlaczego?

Otóż przy odejmowaniu pesymistyczny przypadek skrajnie się zwiększy np. \(\displaystyle{ a = 10^n , \ b=1}\) . Słabo by wyszło co ? Modulowanie, bardzo przyśpiesza .

Tak , pierwszy algorytm jest napisany iteracyjnie .

... 87_czasowa

[sandra-91]

Dziękuję za wyjaśnienie Rzeczywiście, ten wzór jest lepszy.

Czy algorytm jest dobrze napisany rekurencyjnie? Czy musi być w algorytmie \(\displaystyle{ mod}\), tak jak jest we wzorze?

No i oprócz tego, było pytanie, czy da się zapisać ten algorytm (ten rekurencyjny) w postaci \(\displaystyle{ T(n)}\)czyli liczbę porównań? Mimo mamy napisany ten wzór, ale musi być w postaci coś takiego \(\displaystyle{ \lfloor \frac{n}{2}\rfloor}\) czy \(\displaystyle{ \lceil \frac{n}{2}\rceil}\)

[royas]

Powiedziałbym, że nie może być mod, bo jest to już wtedy algorytm znacząco różny od danego. Twoja wersja rekurencyjna nie jest poprawna. Wersja rekurencyjna musi mieć zdefiniowaną jakąś funkcję rekurencyjną, Ty niby używasz nwd ale gdzie to jest zdefiniowane?
Poza tym Twoja wersja nie jest wierna wersji pierwotnej, tu w każdym obiegu pętli modyfikujesz albo a albo b. W rekurencyjnej wersji (zakładając definicję nwd(a,b)) w przypadku a>b modyfikujesz tylko a, a w przeciwnym razie a i b.

[sandra-91]

A zapomniałam zdefiniować nwd, już napisałam:

Kod: Zaznacz cały

nwd(a,b)
if a=b then
        return a
if a>b then 
        return nwd(a-b,b)
       else 
        return nwd(a,b-a)

Teraz jest ok.?

[royas]

Teraz ok.

[sandra-91]

Dzięki za sprawdzenie. A teraz chcę spróbować napisać algorytm Euklidesa przez dzielenie - rekurencyjnie oraz iteracyjnie.

Kod: Zaznacz cały

nwd(a,b)
while a>0 and b>0
    do if a > b
          then a <-- a mod b
          else b <-- b mod a
return nwd(a,b)

Natomiast rekurencyjnie:

Kod: Zaznacz cały

nwd(a,b)
if b<>0 then
         return a
       else 
         return nwd(b,a mod b)

Czy dobrze napisałam?

A wzór wyglądałby tak:

\(\displaystyle{ (a,b)=\begin{cases} a &\text{dla } b = 0\\(b,a \mod b) &\text{dla } b>0 \end{cases}}\)

Hmm.. strasznie podobnie do tego wzoru, którego napisałeś.-- 30 gru 2012, o 22:03 --Hej, czy ktoś może sprawdzić, czy są dobrze napisane? Jeśli jest źle, byłabym wdzięczna, żeby ktoś napisał.