Programowanie funkcyjne/Procedury wyższych rzędów/Ćwiczenia: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
|||
| Linia 1: | Linia 1: | ||
==Ćwiczenia== | ==Ćwiczenia== | ||
* Dane są: definicja typu <tt>tree</tt> i procedura <tt>fold_tree</tt>: | * Dane są: definicja typu <tt>tree</tt> i procedura <tt>fold_tree</tt>: | ||
| Linia 25: | Linia 15: | ||
==Laboratorium== | ==Laboratorium== | ||
* Niech <math>f : \mathcal{R} \to \mathcal{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 = (\texttt{odwrotnosc} f)</math>, to <math>\forall x\ |g(x) - f^{-1}(x)| \le epsilon</math>). | * Niech <math>f : \mathcal{R} \to \mathcal{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 = (\texttt{odwrotnosc} f)</math>, to <math>\forall x\ |g(x) - f^{-1}(x)| \le epsilon</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. | * 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>? | * 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>? | ||
* Napisz odpowiedniki <tt>map</tt> i <tt>filter</tt> dla drzew. Rozważ drzewa binarne i drzewa o wierzchołkach dowolnego skończonego stopnia (por. ćw. do poprzedniego wykładu). | * Napisz odpowiedniki <tt>map</tt> 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 13:28, 22 sie 2006
Ćwiczenia
- 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
- Niech będzie funkcją 1-1 i "na" oraz taką, że , jest rosnąca i . Zaimplementuj procedurę odwrotność, której wynikiem dla parametru będzie przybliżenie z dokładnością zadaną przez stałą epsilon (czyli jeśli , to ).
- Wygładzenie funkcji z odstępem polega na uśrednieniu , i . Napisz procedurę wygładzającą daną funkcję z zadanym odstępem.
- Punktem stałym funkcji jest . Zaimplementuj obliczanie -tego pierwiastka z 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 ?
- Napisz odpowiedniki map i filter dla drzew. Rozważ drzewa binarne i drzewa o wierzchołkach dowolnego skończonego stopnia (por. ćw. do poprzedniego wykładu).
