Autor Wątek: Szukanie cyklu Eulera  (Przeczytany 1111 razy)

Offline giersz2

  • Użytkownik

# Czerwiec 06, 2011, 17:49:43
Próbuje znaleźć cykl Eulera, korzystam z implementacji na tej stronie: http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol024.php
Korzystałem z devcpp oraz netbeans z kompilatorem mingw. Program wysypuje się dla grafów dla liczby wierzchołków ok 380 i nasyceniu 0.6. Jest wtedy ok. 43000 krawędzi. Sprawdziłem, że funkcja wykonuje się to samą ilość (+-1) razy. Dla większej ilości wierzchołków następuje przepełnienie stosu. Jest to normalne? Należy jakoś usprawnić program aby działał dla większych grafów?

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Kos

  • Użytkownik
    • kos.gd

# Czerwiec 06, 2011, 18:33:49
Jest normalne, bo ta implementacja jest rekurencyjna, a rozmiar stosu (przekładający się na max. ilość zagnieżdżeń funkcji) jest stały.

Najprościej: Zwiększyć rozmiar stosu? ;)

Jakby to nie wystarczyło, to da się w jakiś okrutny sposób przerobić funkcję tak, by zamiast na stosie trzymała backtrace gdzieś na stercie, w np. dynamicznym wektorze lub talii.
« Ostatnia zmiana: Czerwiec 06, 2011, 18:36:30 wysłana przez Kos »