Forum I Roku Informatyki UW

I kolokwium - zadanie 3 z 2007

Go down

I kolokwium - zadanie 3 z 2007

Post by juho on Sat Nov 12, 2011 4:00 pm

Zadanie 3 [5 punktów]

Zaproponuj implementację następujących operacji na tablicy liczb naturalnych T[0..n+1], początkowo wypełnionej zerami, w taki sposób, żeby ich koszt zamortyzowany był stały.

Inc(i):: T[i]:=T[i]+1 // zawsze 0<i<n+1
BlockDec(i):: Jeśli T[i]=0 nic nie rób. W przeciwnym przypadku znajdź najbliższy indeks j taki, że T[i]≠T[j] (jeśli są dwa takie indeksy wybieramy mniejszy z nich). Dla każdego k pomiędzy i oraz j wykonaj T[k]:=T[k]–1


Hej, czy ktoś robił już to zadanie i ma pomysł jak je rozwiązać?
Próbowaliśmy na razie bezskutecznie walczyć z liniowym szukaniem końców bloków (uznaliśmy, że to wyszukiwanie psuje koszt zamortyzowany).
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: I kolokwium - zadanie 3 z 2007

Post by adek05 on Sat Nov 12, 2011 6:46 pm

Wydaje mi się, że jeżeli zrobimy szukanie końców tak jak w zadaniu z palindromami - od środka rozjeżdżamy się wskaźnikami i zwiążemy z każdą wstawianą jedynką kredyt 3, to nam wystarczy na opłacenie przy zmniejszaniu.
3 = 1 na usunięcie, 1 na przeszukiwanie siebie, 1 na przeszukiwanie punktu powstałego przez odbicie lustrzane siebie względemu punktu i.

Chyba napisałem niejasno bo Filip na SO próbował to obalić Razz
Jak zrobimy szukanie, to fizycznie odbieramy 2 zł od tych elementów z przedziału, które bedziemy zmniejszać - od krótszego przedziału, to wydaje się rozjaśniać to co napisałem wyżej. W ten sposób cały czas jest parzysta liczba złotówek Smile


Last edited by adek05 on Tue Nov 15, 2011 10:42 pm; edited 1 time in total

adek05

Liczba postów : 34
Join date : 2010-10-20

View user profile

Back to top Go down

Re: I kolokwium - zadanie 3 z 2007

Post by Gricha on Tue Nov 15, 2011 10:21 pm

Podepne się pod ten temat:

Podaj strukturę danych umożliwiającą wykonywanie w czasie O(logn) następujących operacji na początkowo pustym zbiorze S:
insert(v,S)
deletemedian(S)
przy założeniu, że elementy zbioru S pochodzą z dowolnego zbioru liniowego uporządkowanego.

Any idea?
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: I kolokwium - zadanie 3 z 2007

Post by adek05 on Tue Nov 15, 2011 10:38 pm

Mój pomysł jest taki:

EDIT: lepszy link:
https://docs.google.com/drawings/d/1UeesX4eQhJ8_7tri6K3abHYPjJbNaDpzW2cY5Ik4MpY/edit


Insert(v, S)
Patrzymy czy v jest większy czy mniejszy od mediany
większy ląduje w prawym kopcu, mniejszy lub równy w lewym
I robimy poprawienie struktury. Jeśli size(L) + 1 < size(P) lub odwrotnie size(L) > size(P) + 1 to robimy jakby rotację w lewo lub prawo odpowiednio.
Rotacja polega na przerzucenia korzenia do odpowiedniego kopca i wyciągnięcia z wierzchołka drugiego nowej mediany.

Delete polega na wyciągnięciu mediany i wzięciu elementu z odpowiedniego kopca tak, żeby zachować warunek |size(P) - size(L)| <= 1 - taki niezmiennik chcemy utrzymać i insert zapisany jak wyżej zdaje się go zachowywać.

Jak ktoś widzi błąd, to dajcie znać! Smile

adek05

Liczba postów : 34
Join date : 2010-10-20

View user profile

Back to top Go down

Re: I kolokwium - zadanie 3 z 2007

Post by Maciek on Tue Nov 15, 2011 11:01 pm

Mediana jest zdefiniowana jako: dla nieparzystego n to (n+1)/2 element, dla parzystego n, to średnia arytmetyczna, obu środkowych elementów. Tak więc trochę trzeba zmodyfikować tę strukturę, ale ogólnie pomysł mi się podoba Smile

Maciek

Liczba postów : 186
Join date : 2010-10-12

View user profile

Back to top Go down

Re: I kolokwium - zadanie 3 z 2007

Post by adek05 on Tue Nov 15, 2011 11:24 pm

Racja! Ale wtedy jak usunąć medianę? Przecież ona fizycznie w zbiorze nie wystepuje... może jest jakieś założenie co do tego czym jest mediana?

adek05

Liczba postów : 34
Join date : 2010-10-20

View user profile

Back to top Go down

Re: I kolokwium - zadanie 3 z 2007

Post by juho on Tue Nov 15, 2011 11:34 pm

Zgadzam się z Adrianem Wink

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: I kolokwium - zadanie 3 z 2007

Post by adek05 on Tue Nov 15, 2011 11:36 pm

Filip, spadłem z krzesła =)

Przez Ciebie będzie mi się dzisiaj KD śnić... Razz

adek05

Liczba postów : 34
Join date : 2010-10-20

View user profile

Back to top Go down

Re: I kolokwium - zadanie 3 z 2007

Post by Gricha on Wed Nov 16, 2011 12:00 am

Raczej zakładałbym, że medianą będzie element najbliższy medianie mniejszy równy od mediany. Wtedy ma sens deletemedian
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: I kolokwium - zadanie 3 z 2007

Post by Gricha on Wed Nov 16, 2011 9:07 pm

Hej, ma ktoś może dobrze zapisany algorytm sortowania mergesortem ze scalaniem w miejscu? Ten z podziałem na bloki itd.

Chciałem się dowiedzieć co się dzieje jak już mamy posortowane blokowo i mamy ten bufor na początku. Co dalej robimy - jak "wsortowujemy" bloki teraz?
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: I kolokwium - zadanie 3 z 2007

Post by adek05 on Wed Nov 16, 2011 9:41 pm


adek05

Liczba postów : 34
Join date : 2010-10-20

View user profile

Back to top Go down

Re: I kolokwium - zadanie 3 z 2007

Post by Sponsored content


Sponsored content


Back to top Go down

Back to top

- Similar topics

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