Programowanie funkcyjne/Zadania egzaminacyjne: Różnice pomiędzy wersjami

Wersja z 20:15, 15 wrz 2006

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 \leq i \leq j \leq 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 \leq k \leq l \leq n$ , dla której suma $a_{k} + \dots + 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}} (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.

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.

@@ Linia 24: / Linia 24: @@
 : Przykład: <tt>podziel [2; 3; 1; 6; 5; 4; 7; 9; 10; 11; 8] = [[2; 3; 1]; [6; 5; 4]; [7]; [9; 10; 11; 8]]</tt>.
 : Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.
+* 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.