Informatyka UJ forum

domis86 · Wysłany: Pon 11:09, 20 Mar 2006 Temat postu: E

Ma ktoś jakikolwiek test (in i out) do tego zadania? :)
Kurde mam ansa i za cholere nie wiem gdzie:(

domis86 · Wysłany: Pon 16:35, 20 Mar 2006 Temat postu:

Sam zrobilem generator:)
jest tu:

[link widoczny dla zalogowanych]

Robi jeden zestaw testow
-drzewa n=(1..100)
-drzewa n=(200, 2 000, 20 000, 200 000)

Wszystko losowe:)

Prosze tylko o udostepnienie tutaj jakiegos exe programu ktory przeszedl :) zeby bylo jak porownac outy

hansu · Wysłany: Pon 17:51, 20 Mar 2006 Temat postu:

Prosze bardzo:

[link widoczny dla zalogowanych]

domis86 · Wysłany: Pon 18:08, 20 Mar 2006 Temat postu:

Dzieki Hans :wink:

domis86 · Wysłany: Pon 18:28, 20 Mar 2006 Temat postu:

Wpizdu!!!
Te same odpowiedzi co twoje a i tak mam ansa................... :(

Skrobocik · Wysłany: Pon 18:38, 20 Mar 2006 Temat postu:

trywialna · Wysłany: Sob 21:00, 25 Mar 2006 Temat postu:

Przeszło komuś to zadanko na zwyklej tablicy z rekurencja? bo ja ciągle ma RCA i nie widze błędu i zastanawiam sie czy nie zmienic tego na iteracje...

smh · Wysłany: Sob 21:23, 25 Mar 2006 Temat postu:

z rekurencją to raczej nie przejdze... (przynajmniej tego nie widze)

Rogal · Wysłany: Sob 21:25, 25 Mar 2006 Temat postu:

To zadanie ma limit pamięci 28MB, co jest kluczowe jeśli chodzi o jego rozwiązywanie. Po prostu jest to za mało, żeby starczyło na klasyczne algorytmy przeszukiwania drzewa.

Co do rozwiązania to chyba wystarczy zaimplementować Robsona z wykładu 8)

trywialna · Wysłany: Sob 22:06, 25 Mar 2006 Temat postu:

A mi się własnie wydaje że można z rekurencja.. ja używam tylko jednej tablicy i w deklaracji porcedury mam tylko jedna zmienna longint, która deklaruje z varem wiec raczej dodatkowej pamieci nie używam... przynajmniej tak mi sie wydaje:) zapewne mam jakiś głupi błąd jak zwykle :(

hansu · Wysłany: Sob 22:29, 25 Mar 2006 Temat postu:

Niestety nie masz racji... Wywolywanie rekurencyjne jakiejs procedury (nawet o niewielkiej liczbie zmiennych) zajmuje calkiem sporo miejsca na stosie... Zreszta to zadanie celowo jest tak pomyslane (i ma tak ustawione limity) zeby nie dalo sie go zrobic rekurencja, a trzeba bylo wlasnie owym slynnym algorytmem Robsona (nie tego naszego, innego Robsona ;)). Wiec jesli mialbym Ci cos doradzic, to porzuc idee rekurencji i poszukaj w notatkach z wykladow ASD tego wlasnie algorytmu...

trywialna · Wysłany: Sob 23:08, 25 Mar 2006 Temat postu:

No dobra wierze na słowo:) i zaczynam pisać od nowa mam nadzieje że zdąże do poniedziałku:]

Madras · Wysłany: Pon 1:05, 27 Mar 2006 Temat postu:

Ja zrobiłem to nie używając Robsona. Jak? Skorzystałem z tych 4 wolnych megabajtów pamięci i zrobiłem iteracyjnie symulację rekurencji.

Lupus

Witam.

W końcu zrobiłem to zadanie, algorytmem Robsona, bez rekurencji, stosu, ani w ogóle dodatkowej pamięci poza kilkoma zmiennymi.

Rozwiązanie zostało nam podane gotowe na wykładzie ,'] Tylko że z błędami.
Pozwalam sobie zamieścić tutaj pseudokod tego algorytmu wolny od błędów.
Żeby zrozumieć ten algorytm, raczej trzeba przeczytać oryginalny wykład.

Każdy wierzchołek drzewa musi mieć trzy pola i nie powinien mieć więcej:
key
left, right.

Normalnie narzuca się, żeby wierzchołki to był jakiś record z tymi trzeba elementami, a drzewo żeby było tablicą [1..2000000] takich recordów.
No i wtedy narzuca się też, żeby left i right były typu longint i wtedy w left pamiętamy indeks tablicy pod którym znajduje się ten element. Ale ja zrobiłem inaczej i tak polecam: żeby left i right były WSKAŹNIKAMI na odpowiednie elementy tablicy. Wskaźnikami na te recordy. Wtedy normalnie tak jak w tym pseudokodzie można im przypisywać wartość "nil" i łatwo zrobić taki "head" jaki jest potrzebny.

Wyrażenie PREORDER-VISIT(p) oznacza, że jeśli mamy zamiar przeglądać drzewo w porządku preorder, to w tym miejscu algorytmu należy zbadać dany wierzchołek. W naszym wypadku, chodzi o wypisanie jego klucza.
Z INORDER-VISIT(p) i POSTORDER-VISIT(p) analogicznie.

Poprawione błędy opatrzyłem !!!wykrzyknikami!!!.

smas · Wysłany: Wto 0:10, 28 Mar 2006 Temat postu:

Dzisiaj kolega się mnie zapytał gdzie są błędy. NIE POWIEDZIAŁEM! Te błędy przewijają się już od co najmniej roku. Moim zdaniem celowo! Zepsułeś całą zabawę Lupus. Teraz każdy będzie mógł bezmyślnie, nie zagłebiając się w działanie wkleić gotowe rozwiązanie.

Rozumiem jakbyś wstawił same wykrzykniki - ale bez poprawiania.

exeman · Wysłany: Wto 0:17, 28 Mar 2006 Temat postu:

Lukaszt: ja naprawde nie sypiam po nocach, zeby wyrobic sie z zadaniami, do tego mam warunek niedlugo z wdmu. Z checia bym porobil sam te zadania, jakbym tylko mial czas.

Mozna nie spac jedna noc, nawet dwie pod rzad, ale trzy - ciezko, uwierz mi, jesli nie doswiadczyles.

smas · Wysłany: Wto 0:32, 28 Mar 2006 Temat postu:

exeman · Wysłany: Wto 0:35, 28 Mar 2006 Temat postu:

lukaszt: W pewnym sensie masz racje. To zadanie jest z gwiazdka i moze rzeczywiscie nie powinno byc podane publicznie rozwiazanie. Natomiast - kurcze - jesli wszystko robic samemu po kolei, to by nocy zabraklo :/

oinopion · Wysłany: Wto 1:41, 28 Mar 2006 Temat postu:

Zadanie jest z gwiazdką, ale dużo ludzi będzie potrzebowało mieć trochę więcej punktów, niż tylko z zadań obowiązkowych (przypominam, że zadania z asteriksem są wliczane do maksimum punktów). Część ma problemy jeszcze z A. Czas upływa, a zadań nie jest mniej, tak jak pan dr Ślusarek ładnie obiecywał...

Lupus · Wysłany: Wto 14:15, 28 Mar 2006 Temat postu:

z asteriskiem ,']

Pandunia · Gość

[deleted]

exeman

A mi E mimo wszystko sie rypie :/ Wypisuje na koncu przewaznie 0, a dla wiekszych testow w ogole 216 wyskakuje. Jak sprawdzam z heaptrc to dla malych testow (to 10 wierzcholkow), wszystk oladnie sie usuwa, ale ten ostatni bonusowy 0, wrr :/