Zamiana rekursji na iteracje

Odpowiedz Nowy wątek
2019-10-20 22:50
0
type  TElem = integer;
        PNode = ^TNode;
        TNode = record
                         data:TElem
                         prev:PNode
                         next:PNode
                     end;
          TList = record
                        head:PNode;
                        tail:PNode;
                    end;

        procedure BSTtoDLL(root:PNode;var L:TList);
        begin
           if root <> NIL then
           begin
               BSTtoDLL(root^.next,L);
               root^.next := L.head;
               if L.head <> NIL then
                  L.head^.prev := root;
               L.head := root;
               BSTtoDLL(root^.prev,L);
           end;
        end;
  1. Ostatnie wywołanie wygląda na ogonowe i prawdopodobnie da się zamienić na iterację
    ale co z pierwszym ?
    Na co je zamienić aby algorytm miał złożoność czasową O(n)
  2. Tak napisana procedura prawdopodobnie nie ustawi ogona
    Jak to zmodyfikować

Pozostało 580 znaków

2019-10-20 23:54
0

Ad 1, Nie ustawi czego?
Ad 2. Co to ma wspólnego? Spróbuj sprecyzować pytanie.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
Ta procedura ma przekształcać drzewo binarne w listę dwukierunkową ale napisana jest rekurencyjnie poza tym nie ustawi ogona listy dwukierunkowej Co do wersji iteracyjnej to ostatnie wywołanie wygląda na ogonowe a jeśli tak jest to wtedy łatwo zamienić je na iterację Jeśli chodzi o pierwsze wywołanie to myślałem nad stosem tylko nie bardzo wiem jak to miałoby wyglądać poza tym zdaje mu się że zamiast stosu można zastosować iterację Jest jeszcze ograniczenie czasowe O(n) Ciekaw jestem czy programowałeś kiedyś bo mam wrażenie że nabijasz sobie posty - nowy121105 2019-10-21 13:15
Ona nie jest napisana, to nawet się nie skompiluje! - _13th_Dragon 2019-10-21 13:18
No sama procedura się nie skompiluje ale jak dopisałem pozostałe procedury to się skompilowała - nowy121105 2019-10-21 13:24
Ot tak się skompilowała bez średników w deklaracji? - _13th_Dragon 2019-10-21 13:25

Pozostało 580 znaków

2019-10-21 10:56
0

Nie znam Pascala, ale widzę, że Masz tu double linked list, Napisz co ten kod, w ogóle ma robić, bo wydaje mi się, że wszystkie algorytmy na listach można zapisać iteracyjnie.


Pokaż pozostałe 3 komentarze
@_13th_Dragon: To jest to ten przypadek, gdy to co OP stara się zrobić nie ma sensu, bo złożoność takiego algorytmu będzie O(nlogn) - czyli większa niż wyszukiwania liniowego. EDIT: Oczywiście ma sens, moja pomyłka, nie chodzi o wyszukiwanie liniowe, tylko o zamianę drzewa na listę, to jest O(n). - lion137 2019-10-21 11:32
@WhiteLightning: Hanoi nawet rekurencyjnie nie kojarzę ;-] Tym niemniej taka zmiana przeważnie nie jest turbo trudna - robisz sobie sztuczny stos w zmiennej i wsio. https://stackoverflow.com/que[...]n-be-converted-into-iteration - Patryk27 2019-10-21 11:45
Funkcja rekurencyjna działa Napisałem program w którym z węzłów listy dwukierunkowej buduje drzewo BST a następnie konwertuje to drzewo do listy dwukierunkowej przechodząc je w kolejności "in order" czyli L->P->R (left->parent->right) Procedura przechodzi po węzłach najpierw na prawo najprawdopodobniej dlatego że poza wywołaniami rekurencyjnymi występuje kod wstawiający węzeł na początek listy - nowy121105 2019-10-21 21:26
Ze co, to co przedstawiłeś działa? A może przypadkiem wyczarowanie smoka tobie też działa? - _13th_Dragon 2019-10-22 00:30
@WhiteLightning a quicksort da przechodzenie preorder. Z tymi wieżami hanoi to tak funkcja rekurencyjna wygląda podobnie ale nie wiem czy ta iteracyjna wersja jest równoważna rekurencyjnej , czy nie skorzystali z jakichś extra własności itp Ostatnio się trochę bawiłem kodem i wzorując się na zamianie rekurencyjnego quick sorta na iteracyjnego quick sorta dostałem przechodzenie preorder - nowy121105 2019-10-29 23:43

Pozostało 580 znaków

2019-10-21 13:11
1
function treeToList(tree:TTree):TList;
var curr:PBranch;
begin
  Result.head:=nil;
  Result.tail:=nil;
  curr:=tree.root;
  if curr=nil then Exit;
  while curr^.lf<>nil do curr:=curr^.lf;
  while curr<>nil do
  begin
    appendList(Result,curr^.data);
    if curr^.rt<>nil then
    begin
      curr:=curr^.rt;
      while curr^.lf<>nil do curr:=curr^.lf;
    end
    else
    begin
      while (curr^.up<>nil)and(curr^.up^.rt=curr) do curr:=curr^.up;
      curr:=curr^.up;
    end;
  end;
end;

https://ideone.com/LMKnSr


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
A jaka jest złożoność tej funkcji ? Widzę dwie zagnieżdzone pętle while i mam wątpliwości czy będzie działać w czasie O(n) ? - nowy121105 2019-10-21 13:28
Narysuj sobie przejścia dokonywane przez ten kod ... - _13th_Dragon 2019-10-22 00:16

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0