Rozwiązując poniższe zadania zwróć uwagę na efektywność algorytmów.
W większości zadań należy użyć techniki kosztu zamortyzowanego.
-
Napisz funkcję, która przekształci zadane drzewo w stóg, zachowując jego kształt (w rozwiązaniu można wykorzystać
zmodyfikowaną procedurę rotate z wykładu).
Jaka jest złożoność tej procedury? W jaki sposób zależy ona od kształtu drzewa?
-
Rozszerzyć implementację kolejek FIFO o wkładanie i wyjmowanie elementów z obydwu stron (w koszcie zamortyzowanym stałym).
-
Mamy \(n\) kubeczków z wodą, ponumerowanych od 1 do \(n\) (\(n > 0\)).
W kubeczku nr \(i\) znajduje się \(x_i\) wody, przy czym \(0 < x_1 \le x_2 \le \dots \le x_n\).
Powtarzamy \(k\) razy (dla \(k < n\)) nastepującą czynność:
wybieramy dwa (niepuste) kubeczki zawierające jak najmniej wody i wodę z jednego kubeczka dolewamy do drugiego.
Napisz procedurę \(\mathtt{zlewki}:\mathtt{float~list} \to \mathtt{int} \to \mathtt{float}\),
która dla danej listy zawierającej liczby \([|x_1; \dots; x_n|]\) oraz liczby \(k\) określa
określa ile jest wody w najmniej wypełnionym niepustym kubeczku po wykonaniu \(k\) operacji przelewania.
-
Dana jest definicja typu reprezentującego pory roku:
type pora = Wiosna | Lato | Jesień | Zima.
Napisz procedurę \(\mathtt{pory} : \mathtt{pora~array} \to \mathtt{int}\), która dla danego ciągu pór roku wyznaczy długość najkrótszego jej spójnego fragmentu, który zawiera podciąg złożony ze wszystkich czterech pór roku i to we właściwej kolejności.
Jeżeli taki fragment nie istnieje, poprawnym wynikiem jest -1.
Na przykład: pory [|Lato; Wiosna; Zima; Jesień; Lato; Zima; Wiosna; Jesień; Lato|] = 6.
Fragment złożony z 6 ostatnich elementów danej tablicy zawiera podciąg: Jesień, Zima, Wiosna, Lato.
-
Zosia codziennie idąc do szkoły mija sadzawkę w parku i lubi ją obserwować. Zbliża się zima. W tej chwili na sadzawce nie ma lodu, ale wkrótce może się to zmienić. Jeżeli danego dnia temperatura jest ujemna i wynosi \(-X^\circ\)C, to górne \(X\) mm wody na sadzawce zamarza. Jeżeli danego dnia temperatura jest dodatnia i wynosi \(+X^\circ\)C, to górne \(X\) mm lodu topi się, o ile na sadzawce jest tyle lodu. Jeśli temperatura wynosi \(0^\circ\)C, to sadzawka się nie zmienia. Możesz założyć, że sadzawka nigdy nie zamarza do dna.
Przykład: Poniżej podane są temperatury i czym będzie pokryta sadzawka (od góry) w kolejne dni:
- \(+2^\circ\)C: nic,
- \(-12^\circ\)C: 12 mm lodu,
- \(+8^\circ\)C: 8 mm wody, 4 mm lodu,
- \(-4^\circ\)C: 4 mm lodu, 4 mm wody, 4 mm lodu,
- \(+2^\circ\)C: 2 mm wody, 2 mm lodu, 4 mm wody, 4 mm lodu,
- \(+4^\circ\)C: 10 mm wody, 2 mm lodu – roztopiła się górna warstwa lodu i 2 mm dolnej warstwy,
- \(-4^\circ\)C: 4 mm lodu, 6 mm wody, 2 mm lodu,
- \(+1^\circ\)C: 1 mm wody, 3 mm lodu, 6 mm wody, 2 mm lodu,
- \(-3^\circ\)C: 6 mm lodu, 4 mm wody, 2 mm lodu – zamarza górna warstwa lodu i 2 mm kolejnej warstwy wody.
Napisz procedurę \(\mathtt{sadzawka}: \mathtt{int~list} \to \mathtt{int~list}\), która dla danej listy temperatur zwróci listę reprezentującą kolejne warstwy pokrywające sadzawkę po tym okresie – liczby ujemne reprezentują lód, dodatnie wodę, a ich wartość bezwzględna grubość warstwy.
Dla powyższego przykładu, poprawnym wynikiem jest \([-6, 4, -2]\).
-
Zadanie o katastrofach lotniczych:
Dana jest lista liczb całkowitych\([x_1; \dots; x_n]\).
Dla każdego \(i\) trzeba policzyć największe takie \(k_i\), że \(x_i = \max (x_{i-k_i+1}, \dots x_i)\).
Przyjmujemy, że \(x_0 = \infty\).
-
Zaimplementuj \(k\)-max-kolejkę, czyli kolejkę, do której można wkładać elementy i dowiadywać się jakie jest maksimum
z \(k\) ostatnio włożonych elementów.
Dokładniej, powinny być dostępne następujące operacje na \(k\)-max-kolejkach:
init : int → α max_queue -- tworzy nową pustą kolejkę z określonym parametrem \(k\), put : α max_queue → α → α max_queue -- wkłada element do kolejki, get_max : α max_queue → α -- zwraca maksimum z \(k\) ostatnich elementów włożonych do kolejki.
Wszystkie operacje na kolejce powinny działać w stałym czasie zamortyzowanym.
-
Dana jest lista \([x_1; \dots; x_n]\) i stała \(0 \le k < n\).
Oblicz listę \([y_1; \dots; y_n]\), gdzie \(y_i = \max(x_{\max(i-k,1)}, \dots, x_i)\).
-
Mamy daną listę liczb całkowitych \(l = [a_1, \dots, a_n]\).
Liczbę \(a_i\) nazywamy \(k\)-maksimum, jeżeli jest ona większa od \(a_{\max(i-k,1)}, \dots, a_{i-1}, a_{i+1}, a_{\min(i+k,n)}\).
Napisz funkcję kmax : int → int list → int list, dla której wynikiem kmax \(k\) \(l\) jest podlista
listy \(l\) złożona z samych \(k\)-maksimów.
-
Dana jest lista \([x_1; \dots; x_n]\).
Dla \(1 \le i < j \le n\) powiemy, że elementy \(x_i\) i \(x_j\) widzą się nawzajem, jeżeli \(\min(x_i, x_j) \ge \max(x_{i+1}, \dots, x_{j-1})\).
Napisz procedurę widoczne, która obliczy ile elementów ciągu jest widocznych z kolejnych jego elementów.
Np. widoczne [1; 8; 5; 6; 4] = [1; 3; 2; 3; 1].
-
Dana jest tablica \(n\) dodatnich liczb całkowitych.
Tablica ta opisuje figurę złożoną z \(n\) stykających się bokami prostokątów-słupków, których dolne boki leżą na jednej prostej (tzw.~Manhattan skyline).
Kolejne liczby w tej tablicy reprezentują wysokości kolejnych słupków jednostkowej szerokości(od lewej do prawej).
Napisz procedurę \texttt{prostokat: int list → int}, która dla danej tablicy wyznaczy maksymalną powierzchnię prostokąta (o bokach równoległych do boków figury), który można wpisać w figurę opisaną przez tablicę.
- [PCh]
Dana jest lista liczb całkowitych \([x_1;\dots;x_n]\).
Napisz procedurę różnica : int list → (int * int), która dla danej listy wyznaczy taką parę liczb \((i,j)\), że:
- \(0 < i < j \le n\),
- \(x_i \le x_j\), oraz
- \(j-i\) jest jak największe.
Jeżeli takie \(i\) i \(j\) nie istnieją, to poprawnym wynikiem jest (0,0).
- [SICP, Ćw 2.29]
Mobil, to ruchoma konstrukcja o budowie rekurencyjnej.
Mobil ma ruchome ramiona, jak w wadze szalkowej, określonej długości.
Na końcu każdego z ramion zawieszony jest ciężarek o określonej masie, lub mniejszy mobil.
- Zaimplementuj strukturę danych reprezentującą mobile.
- Napisz procedurę obliczającą wagę mobila.
- Napisz procedurę sprawdzającą, czy mobil jest wyważony.
- [*] [BOI 1999 --- uproszczone]
Napisz procedurę, która zrównoważy dany mobil tak, aby jego odważniki miały dodatnie wagi całkowite, a jego całkowita masa była minimalna.
- [*][XII OI, zadanie Sumy Fibonacciego]
System Zeckendorfa, to taki system, w którym liczba jest reprezentowana jako ciąg zer i jedynek, a kolejne cyfry mają
takie znaczenie, jak kolejne liczby Fibonacciego (\(1, 2, 3, 5, \dots\)).
Ponadto, w reprezentacji liczby nie mogą pojawiać się dwie jedynki obok siebie.
Liczby reprezentujemy jako listy zer i jedynek.
Zaimplementuj dodawanie w systemie Zeckendorfa.