Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

E

 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
domis86
[świeżak]



Dołączył: 17 Mar 2006
Posty: 23
Przeczytał: 0 tematów

Skąd: Brzesko

PostWysł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:(
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
domis86
[świeżak]



Dołączył: 17 Mar 2006
Posty: 23
Przeczytał: 0 tematów

Skąd: Brzesko

PostWysł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
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Pon 17:51, 20 Mar 2006    Temat postu:

Prosze bardzo:

[link widoczny dla zalogowanych]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
domis86
[świeżak]



Dołączył: 17 Mar 2006
Posty: 23
Przeczytał: 0 tematów

Skąd: Brzesko

PostWysłany: Pon 18:08, 20 Mar 2006    Temat postu:

Dzieki Hans :wink:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
domis86
[świeżak]



Dołączył: 17 Mar 2006
Posty: 23
Przeczytał: 0 tematów

Skąd: Brzesko

PostWysłany: Pon 18:28, 20 Mar 2006    Temat postu:

Wpizdu!!!
Te same odpowiedzi co twoje a i tak mam ansa................... :(
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Pon 18:38, 20 Mar 2006    Temat postu:

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

Po porstu sprawdzarka widzi, że to hANS i nie wie co robić. Normalnie daje ANS, ale Jemu się wysypuje i zawsze daje OK :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
trywialna
pijak



Dołączył: 12 Mar 2006
Posty: 257
Przeczytał: 0 tematów

Skąd: z kontowni:)

PostWysł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...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
smh
[świeżak]



Dołączył: 05 Mar 2006
Posty: 21
Przeczytał: 0 tematów


PostWysłany: Sob 21:23, 25 Mar 2006    Temat postu:

z rekurencją to raczej nie przejdze... (przynajmniej tego nie widze)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysł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)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
trywialna
pijak



Dołączył: 12 Mar 2006
Posty: 257
Przeczytał: 0 tematów

Skąd: z kontowni:)

PostWysł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 :(
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysł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...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
trywialna
pijak



Dołączył: 12 Mar 2006
Posty: 257
Przeczytał: 0 tematów

Skąd: z kontowni:)

PostWysł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:]
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów

Skąd: Z Pokoju :]

PostWysł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.
Cytat:
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:)

Więc algorytm masz/miałaś ;P prawie dobry, z tym, że Pascal jeśli wywołujesz standardową rekurencję, to kładzie na stos adres (4 bajty) instrukcji programu, którą ostatnio wykonywał przed wejściem do funkcji/procedury, co w pesymistycznym przypadku powoduje rekurencyjne wywołanie 2000000 procedur, a więc zajęcie 8MB pamięci na same adresy miejsc, w których program zaczął wykonywać procedurę, a zapewne masz także 24 megabajtową tablicę z danymi, co powoduje zajęcie 32MB pamięci i wywala błąd przekroczenia limitu. Natomiast ja stwierdziłem, że jeśli zrobię to ręcznie, to wracając do obsługi danego węzła wystarczy, że będę pamiętał ile razy już go odwiedziłem - do tego wystarcza zmienna typu byte, co w najgorszym przypadku zmusza mnie do zajęcia dodatkowych 2MB pamięci - w sumie 26MB, i się spokojnie mieszczę w limicie.
Program ma <100 linii, jeśli ktoś chce szczegółowy algorytm, to niech pisze ;].
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Lupus
pijak



Dołączył: 02 Lut 2006
Posty: 105
Przeczytał: 0 tematów

Skąd: Lea/Piastowska

PostWysłany: Pon 22:01, 27 Mar 2006    Temat postu: Algorytm Robsona. Robson_traversal.

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!!!.

Kod:

Robson_traversal:

head    // jak na rysunku z wykładu
        // head.left <- pierwszy element drzewa
        // head.right <- head
        // wartosc head.key jest nieistotna

// ponizsze zmienne są typu wskaźnikowego na wierzchołki drzewa
prev <- head  // drzewo z nagłówkiem
avail <- nil
top <- nil
p <- left(head)
// q, stack, - zmienne pomocnicze

dir <- left_or_right  // dir jest typu wyliczeniowego, przyjmuje wartosci
                      // "left_or_right" albo "back"


while TRUE do

  if dir = left_or_right then
    PREORDER-VISIT(p)
    if left(p) <> nil then
       // w lewo, odwracając lewy odsyłacz do prev
       q <- left(p)
       letf(p) <- prev
       prev <- p
       p <- q

    else if right(p) <> nil then
       INORDER-VISIT(p)
       //w prawo odwracając prawy odsyłacz do prev
       q <- right(p)
       right(p) <- prev
       prev <- p
       p <- q

    else // p jest liściem
       INORDER-VISIT(p)
       POSTORDER-VISIT(p)
       avail <- p
       dir <- back

  else //dir = back

    if prev = head then
       left(head) <- p
       return

    if left(prev) = nil then
       //powrót z prawej, lewego następnika nie było,
       //wystarcza odwrócić odsyłacz
       q <- right(prev)
       right(prev) <- p
       p <- prev
       prev <- q
       POSTORDER-VISIT(p)

    else if !!!right(prev)!!! = nil then                    //!!!!!!!!!!!!!!
       //powrót z lewej, bez przejścia w prawo
       q <- left(prev)
       left(prev) <- p
       p <- prev
       prev <- q
       !!!POSTORDER-VISIT(p)!!!                             //!!!!!!!!!!!!!!
       INORDER-VISIT(p)

    else // oba poddrzewa węzła prev niepuste

       if !!!(top = nil) or ( top <> nil and right(top) <> prev )!!! then   //!!!!!!!!!!
             //powrót z lewej, idź w prawo,
             //zapamiętaj węzeł na stosie
          q <- left(prev)
          left(prev) <- p  //lewy wskaźnik przywrócony
          p <- right(prev)
          right(prev) <- q //prawy wskaźnik odwrócony

             //teraz operacja push
          right(avail) <- prev
          left(avail) <- top
          top <- avail
          dir <- left_or_right
          INORDER-VISIT(prev)

       else //powrót z prawej

          POSTORDER-VISIT(!!!prev!!!)                          //!!!!!!!!!!!
          q <- right(prev)
          right(prev) <- p//prawy wskaźnik przywrócony
          p <- prev
          prev <- q
          stack <- left(top)  // zamiast stack można użyć q, żadna różnica
          left(top) <- right(top) <- nil
                  //odsyłacze w liściu OK
          top <- stack  // = pop
end while.



Ostatnio zmieniony przez Lupus dnia Wto 14:28, 28 Mar 2006, w całości zmieniany 2 razy
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
smas
Okrutny Admin



Dołączył: 20 Paź 2005
Posty: 1634
Przeczytał: 0 tematów


PostWysł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.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysł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.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
smas
Okrutny Admin



Dołączył: 20 Paź 2005
Posty: 1634
Przeczytał: 0 tematów


PostWysłany: Wto 0:32, 28 Mar 2006    Temat postu:

exeman napisał:
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.

Spoko, doświadczyłem niespania, nieuczenia się z innych przedmiotów - jak większość! Zauważ, że przy tym zadaniu jest gwiazdka - co znaczy, że to zadanie jest dla chętnych.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysł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 :/
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
oinopion
żul



Dołączył: 28 Lis 2005
Posty: 858
Przeczytał: 0 tematów

Skąd: Kraków

PostWysł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ł...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Lupus
pijak



Dołączył: 02 Lut 2006
Posty: 105
Przeczytał: 0 tematów

Skąd: Lea/Piastowska

PostWysłany: Wto 14:15, 28 Mar 2006    Temat postu:

z asteriskiem ,']
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Pandunia
Gość






PostWysłany: Wto 17:46, 28 Mar 2006    Temat postu:

[deleted]

Ostatnio zmieniony przez Pandunia dnia Pią 5:35, 10 Lis 2006, w całości zmieniany 1 raz
Powrót do góry
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Sob 0:31, 01 Kwi 2006    Temat postu:

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 :/
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych Wszystkie czasy w strefie EET (Europa)
Strona 1 z 1

 
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
Regulamin