Forum Coders' city Strona Główna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady

Kopiec

Idź do strony 1, 2  Następny

 
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
piotrkakol
Gość





PostWysłany: Pon Lis 30, 2009 10:51 am  OP    Temat postu: Kopiec Odpowiedz z cytatem Pisownia

Chcę nauczyć się kopców.
W zadaniu: https://pl.spoj.pl/problems/HEAP/ w przykładzie są podane kolejno liczby:
3 -14 -3 15 13 -5 6 -8 -11 1
oto jak zbudowano z nich kopiec:
-14 -11 -5 -8 1 -3 6 3 15 13
No i nie wiem, jak to się stało.
Czy mógłby mi ktoś napisać, czym kierować się przy wrzucaniu kolejnych elementów na kopiec? Wiem, że ma byś to chyba "kopiec rosnący", czyli na samej górze jest najmniejsza liczba, ale nie wiem, jak ustawiać resztę elementów.
Tak więc czy mógłby mi ktoś, krok po kroku, napisać, jak wrzucać owe elementy i czemu?
Rysunek (chociażby w Paincie) mile widziany.

PS Czytałem artykuł na Wikipedii o kopcu, więc bez linków się obejdzie. ;-)


Ostatnio zmieniony przez piotrkakol dnia Pon Lis 30, 2009 3:19 pm, w całości zmieniany 1 raz
Powrót do góry
izaw



Dołączył: 12 Wrz 2008
Posty: 2181
Skąd: Łódź

PostWysłany: Pon Lis 30, 2009 2:09 pm      Temat postu: Odpowiedz z cytatem Pisownia

Skoro czytałeś, to znasz zależności relacji wartości ojciec - synowie. Znasz także jak są określane indeksy synów dla danego ojca i odwrotnie. Zatem dla każdego indeksu w tablicy oblicz indeksy ojca i synów i sprawdź ich wartości względem danego.
_________________
Program nie robi tego co chce programista, ale to co programista zaprogramował
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
piotrkakol
Gość





PostWysłany: Pon Lis 30, 2009 2:42 pm  OP(?)    Temat postu: Odpowiedz z cytatem Pisownia

Cytat:
wartości potomków węzła są w stałej relacji z wartością rodzica (na przykład wartość rodzica jest zawsze większa lub równa wartości potomka).

To fragment z Wikipedii. "W stałej relacji" - nie rozumiem tego. Wiem, że "praojciec" - ten na szczycie - ma najmniejszą wartość.
Cytat:
Znasz także jak są określane indeksy synów dla danego ojca i odwrotnie.
- nie znam, a raczej nie wiem
Cytat:
Zatem dla każdego indeksu w tablicy oblicz indeksy ojca i synów i sprawdź ich wartości względem danego.
- jak?

Napisałem, że czytałem artykuł z Wikipedii, a nie, że rozumiałem.
Powrót do góry
izaw



Dołączył: 12 Wrz 2008
Posty: 2181
Skąd: Łódź

PostWysłany: Pon Lis 30, 2009 3:06 pm      Temat postu: Odpowiedz z cytatem Pisownia

Szukanie to podstawowa umiejętność programisty.

Wpisz w google "kopiec algorytm". Masz tam sporo linków. Na początek przeczytaj z lo z Tarnowa odnośnie konstrukcji, algorytmu. Do kodów nie zaglądaj, ą niestety na bakier ze standardem ;(

_________________
Program nie robi tego co chce programista, ale to co programista zaprogramował
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
piotrkakol
Gość





PostWysłany: Pon Lis 30, 2009 3:40 pm  OP(?)    Temat postu: Odpowiedz z cytatem Pisownia

Dzięki. O to mi chodziło.
Jednak mam dwa elementy źle. To moje kroki i jak powinien wyglądać kopiec:
http://img215.imageshack.us/img215/3461/prawiekopiec.gif
Powrót do góry
izaw



Dołączył: 12 Wrz 2008
Posty: 2181
Skąd: Łódź

PostWysłany: Pon Lis 30, 2009 3:47 pm      Temat postu: Odpowiedz z cytatem Pisownia

Oba kopce są poprawne. Definicja kopca nic nie mówi o relacji między synami danego węzła.
_________________
Program nie robi tego co chce programista, ale to co programista zaprogramował
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
piotrkakol
Gość





PostWysłany: Pon Lis 30, 2009 4:15 pm  OP(?)    Temat postu: Odpowiedz z cytatem Pisownia

No to jak zrobić, żeby dojść to tego "bardziej poprawnego" kopca? Bo na SPOJu musi być tak, jak chce autor zadania - tylko jedna opcja jest poprawna. Jak wypiszę poprawną odpowiedź, ale będzie ona inna niż odpowiedź autora to mi SPOJ nie zaliczy programu.
Powrót do góry
izaw



Dołączył: 12 Wrz 2008
Posty: 2181
Skąd: Łódź

PostWysłany: Pon Lis 30, 2009 6:01 pm      Temat postu: Odpowiedz z cytatem Pisownia

W tym przypadku w funkcji heapify musisz porównywać wartości synów i w razie potrzeby zamienić miejscami. Zauważ, że zamiana musi dotyczyć całych poddrzew.

Nie piszesz nic o języku, ale jeżeli to c/c++ to dobrym pomysłem byłyby wskaźniki.

_________________
Program nie robi tego co chce programista, ale to co programista zaprogramował
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
piotrkakol
Gość





PostWysłany: Pon Lis 30, 2009 6:48 pm  OP(?)    Temat postu: Odpowiedz z cytatem Pisownia

"W funkcji heapify, w przypadku gdy obaj synowie mają równą wartość należy wybrać lewego syna."

A w tym przykładzie, który opisałem nikt nie ma tej samej wartości.
Powrót do góry
izaw



Dołączył: 12 Wrz 2008
Posty: 2181
Skąd: Łódź

PostWysłany: Pon Lis 30, 2009 7:39 pm      Temat postu: Odpowiedz z cytatem Pisownia

Napisałeś program i wysłałeś? Dostałeś błędna odpowiedź, czy spekulujesz.

W przykładach podawana jest jedna z możliwych odpowiedzi i sprawdź czy w tym przypadku nie zostanie zaakceptowana.

_________________
Program nie robi tego co chce programista, ale to co programista zaprogramował
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
Wyświetl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania Wszystkie czasy w strefie CET (Europa)
Idź do strony 1, 2  Następny
Strona 1 z 2

 
Skocz do:  
Możesz pisać nowe tematy
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
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum




Debug: strone wygenerowano w 0.10995 sekund, zapytan = 11
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |