Ćwiczenia 16: Programowanie imperatywne

Ćwiczenia na konstrukcje imperatywne:

  1. Napisz moduł Counter o następującej sygnaturze:

     
          module type COUNTER = sig
            type counter
            val make : unit -> counter
            val inc : counter -> int
            val reset : unit -> unit
          end;;
     

    Procedura make tworzy nowy licznik o początkowej wartości 0.
    Procedura inc zwiększa licznik o 1 i zwraca jego nową wartość.
    Procedura reset ustawia wartość wszystkich liczników na 0.

    Podaj złożoność czasową i pamięciową ciągu \(m\) operacji, spośród których \(n\) to operacje make.

  2. Dana jest tablica liczb całkowitych zawierająca permutację liczb całkowitych od 0 do \(n\) (dla \(n \ge 0\)).
    Napisz procedurę \(\mathtt{cykl} :\mathtt{int~array} \to \mathtt{int}\), która wyznacza długość najdłuższego cyklu danej permutacji.
    Twoja procedura nie może zmieniać danej tablicy.
    Na przykład:

     
          cykl [|2; 1; 0; 5; 6; 4; 3; 8; 7|] = 4
     

    Rozwiązania

  3. Dana jest tablica rozmiaru \(n+1\) zawierająca liczby od 1 do \(n\).
    Napisz procedurę, która zwraca (dowolną) wartość powtarzającą się w tablicy.

    Twoja procedura powinna działać w stałej pamięci dodatkowej.
    Natomiast może modyfikować daną tablicę.

  4. Dana jest tablica znaków, która wypełniona jest nawiasami.
    Napisz procedurę \(\mathtt{nawiasy}: \mathtt{char~array} \to \mathtt{int}\), która zwróci maksymalną długość spójnego fragmentu tablicy, który jest poprawnym wyrażeniem nawiasowym.

    Rozwiązania
  5. Dana jest deklaracja drzew binarnych, w których węzłach znajdują się dodatkowo referencje do węzłów drzewa:

     
          type α tree =
            Node of α * α tree * α tree * α tree ref |
            Null;;
     
    1. Drzewo binarne z fastrygą, to drzewo, w którym każdy węzeł posiada dodatkową referencję na następny węzeł w porządku infiksowym. (Ostatni węzeł powinien zawierać referencję na Null.)
      Napisz procedurę fastryguj : α tree → unit, która sfastryguje dane drzewo.
    2. Napisz procedurę w_lewo : α tree → unit, która w każdym węźle drzewa ustawia referencję tak, aby wskazywały na węzeł (Node) znajdujący się na tej samej głębokości w drzewie i najbliżej w lewo od danego węzła. W przypadku skrajnie lewych węzłów, referencja powinna wskazywać na Null.
    3. Napisz procedurę potomek : α tree → unit, która w każdym węźle ustawi referencję na najgłębiej położony węzeł (Node) będący jego potomkiem.
    4. Powiemy, że drzewo jest porządkowe (BST), jeśli w każdym jego wierzchołku postaci Node(x, left, right, _) wartości w poddrzewie left są mniejsze lub równe x, a wartości w poddrzewie right są większe równe x.
      Napisz procedurę fastryga: α tree → unit, która mając dane drzewo porządkowe tak ustawi w nim referencje, że węzły zawierające takie same wartości będą połączone w listy cykliczne.
      W szczególności, jeśli jakaś wartość występuje tylko raz, to referencja w jej węźle powinna być pętelką.
  6. Dana jest tablica par dodatnich liczb rzeczywistych.
    Liczby te, to długości boków pewnych prostokątów o takich samych polach.
    Tablica ta jest posortowana rosnąco po pierwszych elementach par, oraz malejąco po drugich elementach par.
    Napisz procedurę diagonal: (float * float) array → float, która wyznaczy najkrótszą z przekątnych prostokątów.
  7. Rozważmy zrównoważone drzewo BST, np. drzewo AVL, złożone z \(n\) węzłów. (Zrównoważone, czyli o wysokości rzędu \(O(\log n)\).) W węzłach drzewa znajdują się różne liczby całkowite.
    Samo drzewo nie jest dane, natomiast mamy daną tablicę z liczbami znajdującymi się w węzłach, w kolejności zgodnej z obejściem prefiksowym drzewa. (Obejście prefiksowe, to obejście zgodnie z rekurencyjną zasadą: najpierw korzeń, potem lewe poddrzewo a potem prawe poddrzewo.) Szukamy pewnej wartości w obejściu drzewa.
    Napisz procedurę \(\mathtt{mediana}: \mathtt{int~array} \to \mathtt{int}\), która mając daną tablicę z obejściem drzewa zwróci medianę z wartości znajdujących się w drzewie. (Jeśli w drzewie jest parzysta liczba wartości, to obie ,,środkowe'' są poprawną medianą.)
  8. [M. Startek]
    Rozważmy zrównoważone drzewo BST, np. drzewo AVL, złożone z \(n\) węzłów. W węzłach drzewa znajdują się różne liczby całkowite.
    Samo drzewo nie jest dane, natomiast mamy daną tablicę z liczbami znajdującymi się w węzłach, w kolejności zgodnej z obejściem prefiksowym drzewa. Szukamy pewnej wartości w obejściu drzewa.
    Napisz procedurę \(\mathtt{znajdz}: \mathtt{int~array} \to \mathtt{int} \to \mathtt{int}\), która mając daną tablicę z obejściem drzewa i szukaną wartość, zwróci jej pozycję w danej tablicy. Jeśli szukana wartość nie występuje w obejściu drzewa, wynikiem powinno być \(-1\).
  9. Rozważmy stóg złożony z \(n\) węzłów, zawierających różne liczby całkowite. Stóg jest uporządkowany tak, że wartość w dowolnym węźle jest ostro większa od wartości w jego poddrzewach. Uwaga, stóg nie musi być drzewem pełnym, ani nawet zrównoważonym.

          type 'a heap = 
             Node of 'a heap * 'a * 'a heap | 
             Null
     

    Sam stóg nie jest dany, natomiast mamy daną tablicę z liczbami znajdującymi się w węzłach, w kolejności zgodnej z obejściem infiksowym stogu.
    (Obejście infiksowe, to obejście zgodnie z rekurencyjną zasadą: najpierw lewe poddrzewo, potem korzeń a potem prawe poddrzewo.)
    Napisz procedurę \(\mathtt{rekonstrukcja}: \mathtt{int~array} \to \mathtt{int~heap}\), która mając daną tablicę z obejściem stogu odtworzy go.

  10. [Bentley]
    Dana jest \(n\)-elementowa tablica znaków. Napisz procedurę rotacja\,:\,char array -> int -> unit, która rotuje daną tablicę o zadaną liczbę miejsc cyklicznie w prawo, tzn.:
    \[
    \mathtt{rotacja} [|x_1; x_2; \dots; x_n|]\ k
    \]
    zmienia zawartość tablicy na:
    \[
    [|x_{n-k+1}; \dots; x_n; x_1; \dots ; x_{n-k}|]
    \]
    Na przykład, wywołanie:
    rotacja [|'a'; 'l'; 'a'; 'm'; 'a'; 'k'; 'o'; 't';  'a'|] 4}
    zmienia zawartość tablicy na
    [|'k'; 'o'; 't'; 'a'; 'a'; 'l'; 'a'; 'm'; 'a'|].
  11. Słowa Fibonacciego to ciąg napisów zdefiniowany następująco:
    \[ F_0 = [||], ~~~~ F_1 = [|'b'|], ~~~~ F_2 = [|'a'|], ~~~~ F_{n} = F_{n-1} @ F_{n-2} \]
    Kilka kolejnych słów Fibonacciego to:
    \(F_3 = [|'a'; {}'b'|]\)
    \(F_4 = [|'a'; {}'b'; {}'a'|]\),
    \(F_5 = [|'a'; {}'b'; {}'a'; {}'a'; {}'b'|]\),
    \(F_6 = [|'a'; {}'b'; {}'a'; {}'a'; {}'b'; {}'a'; {}'b'; {}'a'|]\).
    Napisz procedurę \(\mathtt{slowa}: \mathtt{char~array} \to \mathtt{int}\), która dla danego ciągu znaków wyznaczy największy indeks słowa Fibonacciego, które jest jego podciągiem (niekoniecznie spójnym).
    Na przykład: slowa [|'a'; 'b'; 'b'; 'a' ;'b'; 'a'; 'c'; 'a'; 'b'; 'a'; 'b'; 'a'; 'b'|] = 6.
  12. Dana jest tablica liczb całkowitych, której pewna rotacja jest posortowana ściśle rosnąco.
    Napisz procedurę minmax : int array -> int * int, która znajduje minimum i maksimum w takiej tablicy.
  13. Dana jest niepusta tablica liczb całkowitych \(a = [|x_1; \dots; x_n|]\) zawierająca ciąg ściśle monotoniczny, to jest rosnący lub malejący.
    Napisz procedurę \(\mathtt{blisko\_zera}: \mathtt{int~array} \to \mathtt{int}\), która zwraca \(\min(|x_1|, \dots, |x_n|)\).
  14. Tomek chciałby popłynąć z kolegami jachtem w rejs trwający \(k\) dni. Potrzebuje zebrać grupę kolegów, którzy chcą i mogą z nim popłynąć. Od każdego ze swoich kolegów dowiedział się od kiedy do kiedy (włącznie) dysponuje wolnym czasem. Teraz zastanawia się, kiedy wyruszyć w rejs, tak żeby mogli żeglować jak największą grupą. W trakcie rejsu koledzy Tomka mogą się zmieniać (o ile obie osoby mają tego samego dnia wolne).
    Napisz procedurę \(\mathtt{rejs}: \mathtt{int} \to (\mathtt{int} * \mathtt{int})\ \mathtt{list} \to \mathtt{int}\), która mając daną liczbę \(k\) oraz informacje o dostępności kolegów Tomka zwróci maksymalną wielkość załogi (nie licząc Tomka).
    Jeżeli rejsu nie da się zorganizować, to poprawnym wynikiem jest 0.
    Na przykład: \(\mathtt{rejs}\ 20\ [(12, 36); (48, 100); (28, 70); (55, 80); (0, 65); (25, 30)] = 3\).
  15. Tomek chciałby popłynąć z kolegami jachtem w rejs. Potrzebuje zebrać grupę \(k\) kolegów, którzy chcą i mogą z nim popłynąć. Od każdego ze swoich kolegów dowiedział się od kiedy do kiedy (włącznie) dysponuje wolnym czasem. Teraz zastanawia się, kiedy wyruszyć w rejs, tak żeby mógł on trwać jak najdłużej. W trakcie rejsu załoga nie może się zmieniać.

    Napisz procedurę \(\mathtt{rejs}: \mathtt{int} \to (\mathtt{int} * \mathtt{int})\ \mathtt{list} \to \mathtt{int}\), która mając daną liczbę \(k\) oraz informacje o dostępności kolegów Tomka zwróci maksymalną długość rejsu. Jeżeli rejsu nie da się zorganizować, to poprawnym wynikiem jest 0.
    Na przykład: \(\mathtt{rejs}\ 2\ [(12, 36); (48, 100); (28, 70); (50, 80); (0, 69); (25, 30)] = 42\).

  16. Dana jest tablica liczb całkowitych \(a=[|x_1; x_2; \dots; x_n|]\).
    Tablica ta ma taką własność, że jej ciąg różnicowy ( \((x_{i+1} - x_i)_{i=1, 2, \dots, n-1}\)) jest ściśle rosnący.

    • [PCh] Napisz procedurę \(\mathtt{rozne} : \mathtt{int~array} \to \mathtt{bool}\), która dla danej tablicy sprawdza, czy jej elementy są parami różne.
    • Napisz procedurę \(\mathtt{minimum} : \mathtt{int~array} \to \mathtt{int}\), która dla danej tablicy wyznacz minimum z jej elementów.

    Rozwiązując to zadanie nie wolno Ci tworzyć żadnych własnych procedur rekurencyjnych.
    Wolno natomiast korzystać z pętli i innych konstrukcji imperatywnych.

    Podaj złożoność czasową i pamięciową swojego rozwiązania.

  17. Dana jest tablica liczb całkowitych \(a = [|x_1; x_2; \dots; x_n|]\).
    Napisz procedurę \(\mathtt{segment} : \mathtt{int~array} \to \mathtt{int}\),
    która wyznaczy długość (\(j-i+1\)) najdłuższego takiego spójnego fragmentu tablicy \(a\),
    \([|x_i; x_{i+1}; \dots; x_j|]\), dla którego \(\min(x_i, x_{i+1}, \dots, x_j) \ge j-i+1\).
  18. Dana jest tablica liczb całkowitych \(a = [|x_1; x_2; \dots; x_n|]\).
    Napisz procedurę \(\mathtt{daleko} : \mathtt{int~array} \to (\mathtt{int} * \mathtt{int})\),
    która wyznaczy taką parę indeksów \((i, j)\), że:

    • \(i < j\),
    • \(a.(i) < a.(j)\),
    • \(j - i\) jest maksymalne.

    Rozwiązując to zadanie nie wolno Ci tworzyć żadnych własnych procedur rekurencyjnych.
    Zamiast tego powinieneś użyć konstrukcji imperatywnych.

  19. [PCh]
    Dane są dwie listy (bez zapętleń), które łączą się i od pewnego miejsca są tą samą listą.
    Znajdź ten wspólny fragment.
  20. Napisz procedurę sprawdzającą, czy dana lista zawiera cykl.
    Czy potrafisz wyznaczyć jego długość?