|
|
| Linia 24: |
Linia 24: |
|
| |
|
| ==Laboratorium== | | ==Laboratorium== |
|
| |
| * Korzystając z <tt>filter</tt> zaimplementuj Quick-sort.
| |
| * Niech <math>f : {\cal R} \to {\cal R}</math> będzie funkcją 1--1 i "`na'' oraz taką, że <math>f(0) = 0</math>, <math>f</math> jest rosnąca i <math>|f(x)| \ge |x|</math>. Zaimplementuj procedurę <tt>odwrotność</tt>, której wynikiem dla parametru <math>f</math> będzie przybliżenie <math>f^{-1}</math> z dokładnością zadaną przez stałą <tt>epsilon</tt> (czyli jeśli <math>g = (<tt>odwrotność </tt> f)</math>, to <math>\forall x\ |g(x) - f^{-1}(x)| \le <tt>epsilon</tt></math>).
| |
| * Wygładzenie funkcji z odstępem <math>dx</math> polega na uśrednieniu <math>f(x - dx)</math>, <math>f(x)</math> i <math>f(x + dx)</math>. Napisz procedurę wygładzającą daną funkcję z zadanym odstępem.
| |
| * Punktem stałym funkcji <math>y \to \frac{x}{y^{n-1}}</math> jest <math>\sqrt[n]{x}</math>. Zaimplementuj obliczanie <math>n</math>-tego pierwiastka z <math>x</math> za pomocą obliczania punktu stałego i tłumienia przez uśrednianie. Uwaga: ile razy należy stosować tłumienie w zależności od <math>n</math>?
| |
| * 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, <math>i</math> powtórzeń liczby <math>k</math> reprezentujemy w ciągu
| |
| *;skompresowanym jako <math>2^{i-1} \cdot (2 \cdot k - 1)</math>.
| |
| *;
| |
| *;Napisz procedury: kompresującą i dekompresującą
| |
| *;zadaną listę.
| |
| *;Lista skompresowana powinna być oczywiście jak najkrótsza.
| |
| *;Przy dekompresji możesz założyć, że lista skompresowana
| |
| *;nie zawiera zer.
| |
| *;
| |
| *;Rozwiązując to zadanie, zamiast rekurencji, należy użyć
| |
| *;standardowych procedur wyższych rzędów przetwarzających
| |
| *;listy.
| |
| *;
| |
| *;\begin{flushleft} \tt
| |
| *;kompresuj [1; 2; 2; 5; 11; 11; 2];;
| |
| *;''- : int list = [1; 6; 9; 42; 3]''*;\end{flushleft}
| |
| **;Napisz odpowiedniki \codeline{map} i <tt>filter</tt> dla drzew.*;Rozważ drzewa binarne i drzewa o wierzchołkach dowolnego
| |
| *;skończonego stopnia (por.\ ćw.\ do poprzedniego wykładu).
| |
Wersja z 12:13, 18 lip 2006
Ćwiczenia
- Zapisz procedurę length za pomocą foldr.
- Zapisz procedurę append za pomocą foldr/foldl.
- Za pomocą foldl zapisz procedurę rev.
- suma listy funkcji,
- złożenie listy funkcji,
- Za pomocą map zapisz procedurę heads, której wynikiem dla danej listy list, jest lista pierwszych elementów list składowych.
- Za pomocą filter zaimplementuj procedurę not_divisivble, która pozostawia na liście wszystkie elementy niepodzielne przez zadaną liczbę.
- Wykorzystaj rozwiązanie poprzedniego zadania do zaimplementowania sita Eratostenesa.
- Za pomocą foldr zapisz flatten. (let flatten l = foldr (@) l [];;)
- Za pomocą foldl zapisz procedurę foldr.
- Dane są: definicja typu tree i procedura fold_tree:
type tree = Node of tree * int * tree | Leaf;;
let rec fold_tree f a t =
match t with
Leaf -> a |
Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;
Powiemy, że liczba w węźle drzewa jest widoczna, jeżeli na ścieżce od tego węzła do korzenia drzewa nie ma większej liczby. W szczególności liczba w korzeniu drzewa jest zawsze widoczna, a liczby mniejsze od niej nie są nigdy widoczne.
- Napisz procedurę widoczne:drzewo int, która dla zadanego drzewa (zawierającego wyłącznie liczby nieujemne) obliczy liczbę widocznych liczb. Rozwiązując to zadanie nie wolno Ci tworzyć żadnych definicji rekurencyjnych. Powinieneś natomiast skorzystać z procedury fold_tree.
Laboratorium
