Ćwiczenia 14: Koszt zamortyzowany

Rozwiązując poniższe zadania zwróć uwagę na efektywność algorytmów.
W większości zadań należy użyć techniki kosztu zamortyzowanego.

  1. 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?
  2. Rozszerzyć implementację kolejek FIFO o wkładanie i wyjmowanie elementów z obydwu stron (w koszcie zamortyzowanym stałym).
  3. 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.

  4. 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.
  5. 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]\).

  6. 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\).
  7. 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.

  8. 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)\).
  9. 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.
  10. 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].
  11. 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ę.

  12. [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).

  13. [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.
  14. [*][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.