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

  6. 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)\).
  7. 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.
  8. 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].
  9. 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 $\to$ 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ę.

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

  11. [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.
  12. [*][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.