|
|
| (Nie pokazano 10 wersji utworzonych przez jednego użytkownika) |
| Linia 1: |
Linia 1: |
| ==Ćwiczenia==
| | [[Programowanie funkcyjne/Model obliczeń/Ćwiczenia]] |
| *Porównaj <tt>foldr</tt> i <tt>foldl</tt>. Która z nich jest ogonowa?
| |
| *Potęgowanie liczb - liniowe i logarytmiczne, ogonowe.
| |
| *Rozważ standardowe procedury przetwarzania list: <tt>length</tt>, <tt>map</tt>, <tt>append</tt>,<tt>rev</tt>. Czy w ich przypadku definicja ogonowa zmniejsza złożoność pamięciową?
| |
| *Potęgowanie funkcji - najpierw liniowe, potem logarytmiczne, ale obie wersje z rekurencją ogonową. Rozrysować w jaki sposób oblicza się:
| |
|
| |
| iterate 2 ('''function''' x -> x * (x+1)) 2
| |
| iterate 3 ('''function''' x -> x * (x+1)) 1
| |
|
| |
| (w zależności od wersji, cierpliwości i powierzchni tablic :-). W przypadku wersji logarytmicznej, procedura wynikowa jest
| |
| obliczana w czasie logarytmicznym, ale ona sama działa w czasie liniowym.
| |
| | |
| ==Laboratorium==
| |
| * Napisz procedurę <tt>sześciany: int <math> \to</math> int list</tt> taką, że wynikiem <tt>sześciany <math> n</math></tt> jest lista postaci<math> [1^3; 2^3; \dots; n^3]</math>. Rozwiązując to zadanie:
| |
| **możesz korzystać wyłącznie z rekurencji ogonowej,
| |
| **jedyne operacje na liczbach, z jakich możesz korzystać to: <tt>+</tt>, <tt>-</tt> oraz porównywanie.
| |
| *Napisz procedurę <tt>podziel: int list</tt> <math> \to</math> <tt>int list list</tt>,która dla danej listy <math> [a_1; a_2; \dots; a_n]</math> zawierającej permutację zbioru <math> {1, 2, \dots, n}</math> znajdziejej podział na jak najliczniejszą listę list postaci:
| |
| <math> [[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}]] </math>, taką że:
| |
| | |
| <center><math>
| |
| \begin{matrix}
| |
| {a_1, a_2, \dots, a_{k_1}} & = &{1, 2, \dots, k_1} \quad\mbox{(rownosc zbiorow)}, \\{a_{{k_1}+1}, a_{{k_1}+2}, \dots, a_{k_2}} & = &{k_1+1, k_1+2, \dots, k_2},\\ & \vdots & \\
| |
| {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{matrix}</math></center>
| |
| | |
| Przyjmujemy, że wynikiem dla listy pustej jest lista pusta. Przykład:
| |
| <center><math>\texttt{\mbox{podziel}} [2; 3; 1; 6; 5; 4; 7; 9; 10; 11; 8] =
| |
| [[2; 3; 1]; [6; 5; 4]; [7]; [9; 10; 11; 8]]</math></center>.
| |
| | |
| Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.
| |
