Forum I Roku Informatyki UW

Punkt o największej liczbie przecięć (2 kolokwium / Ciebiera)

Go down

Punkt o największej liczbie przecięć (2 kolokwium / Ciebiera)

Post by juho on Sat Jan 07, 2012 6:12 pm

Hej,
Na dodatkowych zajęciach przed kolokwium pan Ciebiera podał swoje typy zadań na kolokwium.
Wśród nich był problem punktu o największej ilości przecięć. Mianowicie w zadaniu należy zaprojektować strukturę, która pozwala na dodawanie, usuwanie, wyszukiwanie przedziałów oraz sprawdzanie, czy X przecina się z jakimś przedziałem w strukturze. Dodatkowe wzbogacenie miało umożliwić znalezienie punktu, o największej liczbie przecięć w czasie krótszym niż liniowy. Strukturą najpewniej jest drzewo przedziałowe, wariant z Cormena (strona 333). Ten problem został też zamieszczony na dole rozdziału jako zagadnienie do przemyślenia.

Czy ktoś ma pomysł jak efektywnie aktualizować / wyszukiwać taki punkt w tego rodzaju drzewie?

Uwaga: nie jest to drzewo przedziałowe, które było na labach i w materiałach do ogarnięcia. Również ja nie miałem tego na żadnych ćwiczeniach. Jest to zupełnie inny rodzaj drzewa przedziałowego.
avatar
juho

Liczba postów : 177
Join date : 2010-10-13
Age : 27
Skąd : Krępiec / Lublin

View user profile http://juho-the-panda.xt.pl

Back to top Go down

Re: Punkt o największej liczbie przecięć (2 kolokwium / Ciebiera)

Post by Gricha on Sat Jan 07, 2012 7:46 pm

Daj raczej namiary na rozdział i podrozdział w cormenie Razz bo mi się strony różnią Razz
avatar
Gricha

Liczba postów : 425
Join date : 2010-10-12
Age : 27
Skąd : Myszków

View user profile

Back to top Go down

Re: Punkt o największej liczbie przecięć (2 kolokwium / Ciebiera)

Post by juho on Sun Jan 08, 2012 4:33 am

15.3 - Drzewa przedziałowe.
avatar
juho

Liczba postów : 177
Join date : 2010-10-13
Age : 27
Skąd : Krępiec / Lublin

View user profile http://juho-the-panda.xt.pl

Back to top Go down

Re: Punkt o największej liczbie przecięć (2 kolokwium / Ciebiera)

Post by Sponsored content


Sponsored content


Back to top Go down

Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum