Programowanie funkcyjne/Zadania egzaminacyjne

Propozycje zadań egzaminacyjnych:

• 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$.)

• 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\le j\le n$. Jaką złożoność ma Twoja procedura?

• Napisz procedurę przedziały:int list -> int*int, która dla danej listy $[a_1,\dots ,a_n]$ oblicza taką parę liczb $(k,l)$, $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.

• Napisz procedurę podział: int list -> int list list, która dla danej listy liczb całkowitych $l=[x_1;x_2;\dots ;x_n]$ podzieli ją na listę list $[l_1;\dots ;l_k]$, przy czym:
  • Parser nie mógł rozpoznać (błąd składni): {\displaystyle l = l_1 @ \dots @ l_k} ,
  • każda z list $l_i$ jest ściśle rosnąca,
  • $k$ jest najmniejsze możliwe.

Przykład:

podział [1;3;0;-2;-2;4;9] = [[1; 3]; [0]; [-2]; [-2;4;9]]

• Napisz procedurę podziel: int list -> int list list, która dla danej listy $[a_1;a_2;\dots ;a_n]$ zawierającej permutację zbioru $\{1,2,\dots ,n\}$ znajdzie jej podział na jak najliczniejszą listę list postaci:

$[[a_1;a_2;\dots ;a_{k_1}];[a_{k_1+1};a_{k_1+2};\dots ;a_{k_2}];\dots ;[a_{k_{m-1}+1};a_{k_{m-1}+2};\dots ;a_{k_m}]]$

taką że:

$\begin{array}{cccc}\{a_1,a_2,\dots ,a_{k_1}\}& =& \{1,2,\dots ,k_1\}& \text{(równość zbiorów)},\\ \{a_{k_1+1},a_{k_1+2},\dots ,a_{k_2}\}& =& \{k_1+1,k_1+2,\dots ,k_2\},\\ & ⋮& \\ \{a_{k_{m-1}+1},a_{k_{m-1}+2},\dots ,a_{k_m}\}& =& \{k_{m-1}+1,k_{m-1}+2,\dots ,k_m\}\end{array}$

Przyjmujemy, że wynikiem dla listy pustej jest lista pusta.

Przykład:

podziel [2; 3; 1; 6; 5; 4; 7; 9; 10; 11; 8] = [[2; 3; 1]; [6; 5; 4]; [7]; [9; 10; 11; 8]]

Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.

• Napisz procedurę buduj_permutacje: 'a list list -> 'a -> 'a, która przyjmuje permutację w postaci rozkładu na cykle i zwraca ją w postaci procedury. Lista składowa postaci $[a_1;\dots ;a_n]$, gdzie $a_i\ne a_j$ dla $1\le i<j\le n$, reprezentuje cykl, czyli permutację przeprowadzającą $a_i$ na $a_{(imodn)+1}$ dla $1\le i\le n$. Możesz założyć, że listy składowe są niepuste.

Lista list $[c_1;\dots ;c_k]$, gdzie listy $c_i$ dla $1\le i\le k$ reprezentują cykle, reprezentuje permutację złożoną z tych cykli. Możesz założyć, że wszystkie cykle są rozłączne.

Przyjmujemy, że dla wartości $x$ nie występujących na żadnej z list $c_i$ wynikiem buduj_permutacje $[c_0;\dots ;c_k]x$ jest $x$. W szczególności, przyjmujemy, że pusta lista reprezentuje permutację identycznościową.

Przykład:

 let p = buduj_permutacje [[2; 1]; [8; 3; 4]; [5; 7; 6; 10]; [11]];;
 map p [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12];;
 -: int list = [2; 1; 4; 8; 7; 10; 6; 3; 9; 5; 11; 12]

• Dana jest lista liczb zmiennopozycyjnych $[x_1;x_2;\dots ;x_n]$. Jej uśrednienie, to lista postaci: $[\frac{x_1+.x_2}{2.0};\dots ;\frac{x_{n-1}+.x_n}{2.0}]$. Uśrednieniem listy jednoelementowej oraz pustej jest lista pusta.

Napisz procedurę usrednienie, która dla danej listy obliczy jej uśrednienie. Rozwiązując to zadanie nie możesz tworzyć procedur rekurencyjnych. Zamiast tego powinieneś skorzystać ze standardowych procedur wyższych rzędów przetwarzających listy.

• Rozważmy następującą metodę kompresji ciągów liczb całkowitych: Jeżeli w oryginalnym ciągu ta sama liczba powtarza się kilka razy z rzędu, to jej kolejne wystąpienia reprezentujemy za pomocą jednej tylko liczby. Konkretnie, $i$ powtórzeń liczby $k$ reprezentujemy w ciągu skompresowanym jako $2^{i-1}\cdot (2\cdot k-1)$.

Napisz procedurę kompresuj: int list -> int list kompresującą zadaną listę. Lista wynikowa powinna być oczywiście jak najkrótsza.

Rozwiązując to zadanie nie wolno Ci tworzyć żadnych własnych procedur rekurencyjnych. Powinieneś natomiast użyć procedur wyższych rzędów przetwarzających listy, znanych z wykładów.

Przykład:

kompresuj [1; 2; 2; 5; 11; 11; 2] = [1; 6; 9; 42; 3]

• Napisz procedurę codrugi: 'a stream -> 'a stream, która przekształca strumień postaci $(s_1;s_2;s_3;s_4;\dots )$ w strumień postaci $(s_1;s_3;s_5;\dots )$. Powinna ona działać zarówno dla strumieni skończonych, jak i nieskończonych.

• Zdefiniuj w sposób uwikłany strumień złożony z tych dodatnich liczb całkowitych, które w rozkładzie na czynniki pierwsze mają tylko liczby 2 i 3, oraz rozkładają się na nieparzystą liczbę czynników pierwszych.