Programowanie funkcyjne/Model obliczeń/Ćwiczenia: Różnice pomiędzy wersjami

Wersja z 21:59, 20 lis 2008

Praca domowa

Porównaj foldr i foldl. Która z nich jest ogonowa?
Zaimplementuj potęgowanie liczb -- ogonowo, raz o złożoności liniowej, a raz o złożoności logarytmicznej.

Ćwiczenia

Ćwiczenie [Złożoność rekurencji ogonowej]

Rozważ standardowe procedury przetwarzania list: length, map, append,rev. Czy w ich przypadku definicja ogonowa zmniejsza złożoność pamięciową?

Ćwiczenie [Potęgowanie funkcji]

Potęgowanie funkcji -- najpierw liniowe, potem logarytmiczne, ale obie wersje z rekurencją ogonową.

Rozrysuj 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

Ćwiczenie [Sześciany]

Napisz procedurę sześciany : int -> int list taką, że wynikiem sześciany n jest lista postaci $[1^{3}; 2^{3}; \dots; n^{3}]$ . Rozwiązując to zadanie:

możesz korzystać wyłącznie z rekurencji ogonowej,
jedyne operacje na liczbach, z jakich możesz korzystać to: +, - oraz porównywanie
skorzystaj z tożsamości:
- $(n + 1)^{3} = n^{3} + 3 n^{2} + 3 n + 1$ ,
- $(n + 1)^{2} = n^{2} + 2 n + 1$ .

Twoje rozwiązanie powinno działać w czasie $Θ (n)$ .

Ćwiczenie [Podział permutacji]

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{matrix} {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{matrix}

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]]$ , $podziel [3; 4; 1; 2] = [[3; 4; 1; 2]]$ .

Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.

Programowanie funkcyjne/Model obliczeń/Ćwiczenia: Różnice pomiędzy wersjami

Wersja z 21:59, 20 lis 2008

Praca domowa

Ćwiczenia

Laboratorium

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 47: / Linia 47: @@
 Przyjmujemy, że wynikiem dla listy pustej jest lista pusta.
-Przykład:  <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>.
+Przykład:
+<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>,
+<math>\texttt{\mbox{podziel}} [3;4;1;2] = [[3;4;1;2]] </math>.
 Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.
 }}