Informatyka UJ forum

Pandunia · Gość

[deleted]

Robson

Akurat to pojdzie szybko - tylko tzreba wygrzebać wykłady z wdi z zeszłego semestru, tak gdzies pod koniec. Tam olgorytm jest prawie gotowy do przeklejenia - wystarczy tylko beginy i endy dopisać i obsluge wejscia.

Madras

Fakt, kolejny algorytm z Cormena do wklepania.
Mała dygresja:
Przypomina mi się panika, jaka była przy zadaniu A. Ludzie myśleli jak tu wykombinować, żeby to działało szybciej, i szybciej, i szybciej... A się okazało, że zwykłe mnożenie szkolne, prosty algorytm pierwiastkowania i pisemne dzielenie spokojnie przechodzi. Dlatego bez przesady, niektóre rzeczy nie są takie trudne, jakie się nam wydają. I nie taki diabeł straszny, jak go malują.

Robson

Madras jak zwykle spokojny i z wyważonym zdaniem... ;) Normalnie jakbym jakiegoś Platona, czy innego filozofa, albo jakiegoś wyznawce filozofii Zen :P

jagm

hansu

Masz jakies tajne kontakty z drem Slusarkiem, jagm? ;) Czy taki hakier jestes?? (tzw. elementarny hacking :P).

jagm

po prostu zdążyłem skopiować notatki z asd z zeszłego roku szybciej niż dr Ślusarek je usunął ;] Taka elementrna zasada przydatna podczas jedzenia ze wspólnej miski ;)

Madras

Ja skopiowałem notatki z ASD2 jak coś ;].

Robson

hansu

No mieliscie racje - to zadanie jest naprawde prosciutkie. I nawet nie radze zrzynac sortowania topologicznego z wykladow z WDI. Naprawde, lepiej zerznac z wykladow z ASD :P A tak na serio to wystarczy zwykly DFS bez tych wszystkich "wodotryskow" jak czasy i drzewa i do tego jedna tablica na zapisanie wyniku (bo on sie tworzy "od konca"). Moj kod do tego zadania ma (nie liczac wypasionej obiektowej kolejki na liscie wskaznikowej ;)) jakies 60 linijek (a kolejka 90 - ale zaloze sie ze mozna to w 100 linijkach SPOKOJNIE upchnac).

Aha, jakby ktos testwowal na virgo to podpowiem ze tamtejsza wzorcowka daje w 90% przypadkow inne wyniki (oczywiscie nie mowimy o outach postaci CYKL :D) niz moj prog wiec nie sugerujcie sie zbytnio... Jakby byla potrzeba to moge udostepnic mojego execa...

Spectro

Ja mam w 57 linijkach, ale nie o tym chciałem napisać.

Otóż można popełnić bardzo głupi błąd w implementacji dfsa, który mi się zresztą zdarzył (co kosztowało mnie gwiazdkę i pół godziny). Wierzchołek, od którego zaczynamy zwiedzanie, musimy od razu po wejściu do niego ustawić na szary. U mnie był albo biały, albo czarny, przez co algorytm nie był w stanie wykryć cykli, które przechodziły przez ten wierzchołek.

mateo

trywialna

Skoro tutaj nie ma zestawów danych to nie trzeba chyba czyścić wskażników?

jagm

teoretycznie chyba nie. no ale nie zaszkodzi ;)

Madras

Na 99% nie. Ale jak dostaniesz Rxy, to będzie to pierwszy podejrzany ;].
Inna sprawa, że tego nie trzeba nawet robić wskaźnikowo. Tablica powinna zupełnie wystarczyć.

trywialna

No właśnie dostałam:) RCA. I się właśnie zastanawiam czy to z tego powodu bo to niby jest stack a nie heap

Madras

Pamięć na stos i na stertę jest liczona razem, więc jeśli obiekty utwórzone przez new zajmą 99% pamięci, a akurat wtedy zostanie wywołana procedura, która potrzebuje kolejne 2%, to wywalony zostanie 202 nawet, jeśli będą to pierwsze bajty zajęte na stosie.
Mimo to wydaje mi się, że jeśli nie ma zestawów danych, to program powinien po zakończeniu zostać ubity i uruchomiony od nowa... No chyba, że TCS'owcy robią to jakoś inaczej.
A może DFS Ci się pętli dla jakichś danych? Ja w sumie do tego zadania jeszcze nie siadłem, więc mogę rozważać tylko teoretycznie ;p.

trywialna

No wiesz... Prawde mówiąc to nie mam jak tego sprawdzić bo nie ma jeszcze testów;) A samemu mi się nie chce bawić w ich tworzenie. No ale poczyszcze te wskaźniki...

Madras

Osobiście uważam, że znacznie lepiej linia po linii przeczytać kod upewniając się, że wszystko jest napisane tak, jak chcieliśmy, niż szukać kolejnych testów i patrzeć na czym się wywala.
Poza tym na sprawdzarce Mateo są jakieś testy ;P, i to chyba nawet akceptują wszystkie poprawne odpowiedzi.

jagm

ostoj

a ja mam takie lamerskie pytanie - o co w tym zadaniu w ogole chodzi? :D bo o ile wczesniej w zyciu spotkalem sie z listami stosami czy drzewami i z tym jakis problemow nie bylo, o tyle co to jest graf to sie wlasnie dowiedzialem przegladajac notatki z wdi i czytajac cormena (bo cwiczen przed swietami nie mialem). ale w sumie nic mi to nie mowi :) tzn nie wiem jak w tym zadaniu zastosowac dfs aby otrzymac rozwiazanie. centralnie nie wiem jak zaimplementowac zadanie na godzine roboty :) dlatego bardzo prosze kogos o oswiecenie mnie o co tu chodzi i co tu trzeba zrobic i jak sie za to wziac (bo jak na razie wiem tyle co przeczytalem z tresci zadania :))

pawell

poczytaj w notatkach o grafach na ostatniej stronie napisane mniej wiecej jak zrobic sortowanie topologiczne to wlasnie o to chodzi...

ostoj

no tyle wiem, ale mi po tym ze se to posortuje? slepy jestem, ale nie widze jak skorzystac z wyniku sortowania :)

Robson

no wiesz jak masz iles tam czynności powiedzmy
a, b, c, d no i masz je wszystkie wykonać, no ale np. zeby wykonać a musisz najpierw wykonać c i d a zeby wykonać b musisz mieć a to musisz zacząc od c, pózniej zrobić d, jak juz to jest zrobione to mozesz zabireac sie za a, a na koncu jak a jest załatwione to bierzesz sie za b.
Przykład opisowy:
zeby przeszczepić pacjentowi A nerke dawcy B to najpierw musisz znieczulic A, znieczulic B, potem pobrać nerke od B i wszczepić ją na koncu A.
raczej nikt nie wszczepia najpierw nerki, potem pobiera jej od dawcy, a na koncu usypia obu pacjentów :P
To jest to szeregowanie czynności.
dla tego przykładu mamy taki graf:

pawell

heh... wiec ja to zrobilem tak ze w DFSie sprawdzam czy ma wsteczna czyli czy jest juz zakolorowana na szaro ( to tez jest w wykladach ) i jesli tak to po prostu koncze dzialanie wypisujac CYKL a jesli nie no to sobie dziala to sortowanie i po tym jak zaznacza na czarno to wpisuje sobie ta wartosc juz pokolorowana na czarno do tablicy.. a po zakonczeniu wypisuje te tablice od konca... to zreszta tez masz na wykladzie zeby po pokolorowaniu na czarno wpisac bodajze "u" na poczatek listy( dlatego wypisuje od konca ).. i tyle w sumie jak dla takiego lamera jak ja.. zadanie calkiem przyjemne..;] pozrdo