Ćwiczenia na konstrukcje imperatywne:
-
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.
-
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
-
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ę.
-
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
-
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;;
-
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.
-
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.
-
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.
-
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ą.
-
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.
-
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ą.)
- [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\).
-
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.
- [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'|].
-
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.
-
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.
-
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|)\).
-
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\).
-
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\).
-
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.
-
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\).
-
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.
- [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.
-
Napisz procedurę sprawdzającą, czy dana lista zawiera cykl.
Czy potrafisz wyznaczyć jego długość?