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ę 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}{rcl}\{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.

• 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].

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