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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Kubica (dyskusja | edycje)
630 edycji
m Zastępowanie tekstu – „<math> ” na „<math>”
 
(Nie pokazano 2 wersji utworzonych przez 2 użytkowników)
Linia 22: Linia 22:
== Laboratorium ==
== Laboratorium ==
{{cwiczenie|[Sześciany]||
{{cwiczenie|[Sześciany]||
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>.  
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:
Rozwiązując to zadanie:
* możesz korzystać wyłącznie z rekurencji ogonowej,
* 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
* jedyne operacje na liczbach, z jakich możesz korzystać to: <tt>+</tt>, <tt>-</tt> oraz porównywanie
* skorzystaj z tożsamości:  
* skorzystaj z tożsamości:  
** <math>(n+1)^3 = n^3 + 3n^2 + 3n +1 </math>,
** <math>(n+1)^3 = n^3 + 3n^2 + 3n +1</math>,
** <math>(n+1)^2 = n^2 + 2n + 1</math>.  
** <math>(n+1)^2 = n^2 + 2n + 1</math>.  
Twoje rozwiązanie powinno działać w czasie <math>\Theta(n)</math>.
Twoje rozwiązanie powinno działać w czasie <math>\Theta(n)</math>.
Linia 36: Linia 36:
która dla danej listy <math>[a_1; a_2; \dots; a_n]</math> zawierającej permutację zbioru  
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:  
<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/>  
<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/>
taką, że:<br/>
<center><math>\begin{matrix}
<center><math>\begin{matrix}
Linia 47: Linia 47:
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>.
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.
Rozwiązując to zadanie powinieneś skorzystać z rekurencji, ale wolno Ci korzystać wyłącznie z rekurencji ogonowej.
}}
}}

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 [13;23;…;n3]. 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=n3+3n2+3n+1,
    • (n+1)2=n2+2n+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 [a1;a2;…;an] zawierającej permutację zbioru {1,2,…,n} znajdzie jej podział na jak najliczniejszą listę list postaci:

[[a1;a2;…;ak1];[ak1+1;ak1+2;…;ak2];…;[akm−1+1;akm−1+2;…;akm]],

taką, że:

{a1,a2,…,ak1}={1,2,…,k1}(równość zbiorów),{ak1+1,ak1+2,…,ak2}={k1+1,k1+2,…,k2},⋮{akm−1+1,akm−1+2,…,akm}={km−1+1,km−1+2,…,km}


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.

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Programowanie_funkcyjne/Model_obliczeń/Ćwiczenia&oldid=82614”