Programowanie funkcyjne/Struktury danych/Ćwiczenia

Praca domowa

• Napisz procedurę dubluj, która dubluje elementy listy. Na przykład, dubluj [1;2;3] = [1;1;2;2;3;3].
• Zaimplementuj arytmetykę liczb wymiernych, reprezentując liczby wymierne jako rekordy złożone z licznika i mianownika. Implementacja może być uproszczona, np.\ bez skracania ułamków i bez normalizacji znaków.
• Zadeklaruj wariantowy typ danych reprezentujący abstrakcyjną składnię wyrażeń arytmetycznych. Napisz procedurę obliczającą wartość wyrażenia.

Ćwiczenia

Ćwiczenie programistyczne na listy:

• Zaimplementuj procedurę zwracającą $n$-ty element listy.
• Napisz procedurę tworzącą listę $n$ pierwszych liczb naturalnych.
• Zaimplementuj procedurę rev odwrócającą listę. (Zwróć uwagę, że rozwiązując to zadanie można korzystać z :: lub @, co daje liniową lub kwadratową złożoność czasową.)
• Zaimplementuj procedurę append sklejającą listy.
• Ciąg różnicowy ciągu $(x_1,\dots ,x_n)$ to ciąg postaci $(x_2-x_1,\dots ,x_n-x_{n-1})$. Napisz procedurę obliczającą ciąg różnicowy zadanej listy liczb całkowitych.
• Napisz procedurę obliczającą listę kolejnych ciągów różnicowych zadanej listy liczb całkowitych.
• Napisz procedurę, której wynikiem jest para: minimum i maksimum elementów z listy. Procedura ta powinna wykonywać co najwyżej $\frac{3}{2}n$ porównań.
• Napisz procedurę flatten rozwijającą listę list do listy elementów. Na przykład, flatten [[1; 2]; []; [3; 4; 5]] = [1; 2; 3; 4; 5].
• Napisz procedurę last, której wynikiem jest ostatni element listy.
• Napisz procedury head i tail, które dla zadanej listy $l$ i liczby całkowitej $n$ zwracają pierwsze/ostatnie $n$ elementów listy $l$. Jeśli lista $l$ ma mniej elementów niż $n$, to wynikiem powinna być cała lista $l$. (Nazwy pochodzą od programów head i tail w Uniksie.) Co jest wynikiem tail (head l n) 1?
• Napisz procedurę posumuj, która dla danej niemalejącej listy dodatnich liczb całkowitych $(a_1\dots a_n)$ oblicza listę $(b_1\dots b_n)$, gdzie $b_i=\sum _{k=a_i}^n{a}_k$. (Pamiętaj o tym, że jeśli $m>n$, $\sum _{k=m}^n{a}_k=0$.)
• Zaimplementuj sortowanie: przez scalanie lub quick-sort.
• Zaimplementuj pakiet arytmetyczny nieograniczonych liczb całkowitych.
• Napisz program wybierający większość z listy większościowej; uzasadnij jego poprawność. Uwaga: to zadanie można rozwiązać probabilistycznie: metodą Las Vegas: wylosuj element i sprawdź czy to większość; policz oczekiwaną złożoność,
• Tomek ma zabawkę, z której wystają drewniane słupki różnej wysokości. Jednym uderzeniem młotka może wbić lub wysunąć wybrany słupek o 1. Napisz procedurę słupki, która dla danej listy początkowych wysokości słupków obliczy minimalną liczbę uderzeń młotka potrzebnych do wyrównania wysokości słupków. Napisz funkcję max_diff : int list $\to$ int, która dla niepustej listy $[x_1;\dots ;x_n]$ znajdzie maksymalną różnicę $x_j-x_i$ dla $1\le i<j\le n$. Jaką złożoność ma Twój program.
• Napisz funkcję trójki:int list $\to$ (int * int * int) list, która dla zadanej listy dodatnich liczb całkowitych, uporządkowanej rosnąco, stworzy listę takich trójek $(a,b,c)$ liczb z danej listy, że:
  • $a<b<c$,
  • liczby $a$, $b$ i $c$ spełniają nierówność trójkąta, czyli $c<a+b$.
• Zdefiniuj taką funkcję przedziały:int list $\to$ int*int, że przedzialy$[a_1,\dots ,a_n]=(k,l)$, gdzie jest to taka para liczb $1\le k\le l\le n$, dla której suma $a_k+\cdots +a_l$ jest największa. Oblicz i podaj złożoność Twojego rozwiązania (jako funkcję $n$).

Ćwiczenia na inne struktury danych:

• Zdefiniuj typ reprezentujący drzewa o wierzchołkach dowolnego (skończonego stopnia).
• Zdefiniuj trochę procedur operujących na takich drzewach.
• Zdefiniuj typ reprezentujący dni tygodnia, miesiące i datę.
• Zdefiniuj procedurę obliczającą na podstawie daty dzień tygodnia. Możesz założyć, że dana jest procedura sylwester, która na podstawie roku określa jakiego dnia tygodnia był Sylwester.

Ćwiczenia na inne struktury danych:

• Napisz całe mnóstwo procedur operujących na drzewach. Mogą to być znane Ci operacje dotyczące drzew, lub odpowiedniki operacji na listach.
• Napisz procedurę, która dla dowolnego drzewa binarnego poprawia je tak, że spełnia ono słabszą wersję warunku BST: dla dowolnego węzła, lewy syn nie jest większy, a prawy nie jest mniejszy, niż węzeł.
• Napisz procedurę, która przekształca dane drzewo binarne w wyważone drzewo binarne, zachowując kolejność elementów w porządku infiksowym.
• Rozszerzyć implementację kolejek o wkładanie i wyjmowanie elementów z obydwu stron.
• Dany jest typ danych reprezentujący (mało efektywnie) liczby naturalne: type nat = ZERO | SUCC of nat;;. Zaimplementuj operacje arytmetyczne na takich liczbach.
• Zaimplementuj takie operacje na zbiorach, jak suma, przecięcie, różnica.