Ć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
     
  3. 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.
  4. 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ą.
  5. 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.
  6. 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.
  7. 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|)\).
  8. 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\).

  9. 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.

  10. 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\).
  11. 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.

  12. [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.
  13. Napisz procedurę sprawdzającą, czy dana lista zawiera cykl.
    Czy potrafisz wyznaczyć jego długość?