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

Aktualna wersja na dzień 22:17, 11 wrz 2023

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.

@@ Linia 21: / Linia 21: @@
 == Laboratorium ==
-* Napisz procedurę <tt>sześciany : int -> int list</tt> taką, że wynikiem <tt>sześciany n</tt> jest lista postaci <math> [1^3; 2^3; \dots; n^3]</math>. Rozwiązując to zadanie:
+{{cwiczenie|[Sześciany]||
-** możesz korzystać wyłącznie z rekurencji ogonowej,
+Napisz procedurę <tt>sześciany : int -> int list</tt> taką, że wynikiem <tt>sześciany n</tt> jest lista postaci <math>[1^3; 2^3; \dots; n^3]</math>.
-** jedyne operacje na liczbach, z jakich możesz korzystać to: <tt>+</tt>, <tt>-</tt> oraz porównywanie.
+Rozwiązując to zadanie:
-* Napisz procedurę <tt>podziel : int list -> 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> znajdzie jej podział na jak najliczniejszą listę list postaci:
+* możesz korzystać wyłącznie z rekurencji ogonowej,
-<center><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>,</center><br/>
+* jedyne operacje na liczbach, z jakich możesz korzystać to: <tt>+</tt>, <tt>-</tt> oraz porównywanie
-:taką, że:<br/>
+* skorzystaj z tożsamości:
+** <math>(n+1)^3 = n^3 + 3n^2 + 3n +1</math>,
+** <math>(n+1)^2 = n^2 + 2n + 1</math>.
+Twoje rozwiązanie powinno działać w czasie <math>\Theta(n)</math>.
+}}
+{{cwiczenie|[Podział permutacji]||
+Napisz procedurę <tt>podziel : int list -> 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> znajdzie jej podział na jak najliczniejszą listę list postaci:
+<center><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>,</center><br/>
+taką, że:<br/>
 <center><math>\begin{matrix}
 \{a_1, a_2, \dots, a_{k_1}\} & = &\{1, 2, \dots, k_1\}  & \mbox{(równość zbiorów)}, \\
@@ Linia 34: / Linia 45: @@
 \end{matrix}</math></center>
 <br/>
-:Przyjmujemy, że wynikiem dla listy pustej jest lista pusta.
+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>.
-:Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.
+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.
+}}

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

Aktualna wersja na dzień 22:17, 11 wrz 2023

Praca domowa

Ćwiczenia

Laboratorium

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia