Mulțimi

Modulul Set (documentația OCaml)

1. Scrieți o funcție care ia ca parametru o mulțime de șiruri de caractere și o tipărește, folosind iteratorul S.iter pentru a parcurge elementele. Afișați mulțimea pe o linie, între acolade { } și cu virgulă între elemente. Puteți folosi print_string, print_char, print_newline (vezi modulul implicit deschis Pervasives) sau Printf.printf.

2. Asemănător cu funcția set_of_intlist, scrieți o funcție care ia o listă de perechi (de tip precizat) și returnează mulțimea elementelor de pe prima poziție din fiecare pereche (variante: a doua poziție; ambele poziții, dacă sunt de același tip).

3. Implementați funcția standard filter care ia ca parametri o funcție booleană (condiție, predicat) f și o mulțime s și returnează mulțimea elementelor din s care satisfac funcția f.

4. Implementați funcția standard partition care ia ca parametri o funcție booleană f și o mulțime s și returnează o pereche de mulțimi, cu elementele din s care satisfac, respectiv nu satisfac funcția f.

5. Scrieți o funcție care ia o mulțime de mulțimi (de exemplu, de șiruri), și returnează reuniunea (variantă: intersectia) mulțimilor.

6. Scrieți o funcție care returnează mulțimea cifrelor unui număr. Scrieți apoi altă funcție care ia o mulțime de numere și returnează reuniunea/intersecția dintre mulțimile cifrelor lor.

7. Un număr natural descompus în factori primi poate fi reprezentat ca mulțime de perechi (factor prim, exponent), de exemplu {(2, 3), (5, 1)} pentru 40.
Descrieți, în notație matematică pe hârtie, cum obțineți în cazul general mulțimea tuturor divizorilor unui număr astfel dat, folosind operații pe mulțimi. Calculați mulțimea divizorilor pentru un număr cu cel puțin 3 factori primi, din care cel puțini doi cu exponenți mai mari decât 1.
Scrieți, folosind liste sau mulțimi, o funcție care implementează unul din pașii de calcul găsiți rezolvând punctul anterior.

8. Scrieți o funcție care ia ca parametru o mulțime s și un număr k și returnează lista (sau mulțimea) tuturor submulțimilor lui s cu k elemente.
Indicație: țineți minte mulțimea aleasă deja, și numărul elementelor n din mulțimea rămasă. Dacă k = 0, nu mai trebuie ales nimic. Dacă k = n, trebuie luate toate elementele rămase. Altfel, pentru un element dat din mulțime, putem să îl alegem, sau nu.

9. Scrieți o funcție care ia ca parametru o funcție (de doi întregi cu rezultat întreg) și două mulțimi de întregi A și B și returnează mulțimea valorilor f a b cu a ∈ A și b ∈ B. Adaptați parcurgerile făcute pentru produsul cartezian.

10. Un calculator memorează numere în doi regiștri a și b și poate executa la fiecare pas una din două instrucțiuni: a += b care adună pe b la a (modificând pe a) și b += a (analog). Scrieți o funcție care ia ca parametri două numere naturale a și b și o valoare limită lim și calculează mulțimea tuturor numerelor care se pot obține cu aceste instrucțiuni pornind de la a și b, nedepășind lim .
De exemplu, dacă inițial (a,b)=(3,1) și lim=5, în primul pas se ajunge fie la (4,1) fie la (3,4). Din (3, 4) nu se poate continua (s-ar depăși limita); din (4, 1) se ajunge la (4, 5) și (5, 1). Răspunsul e {1, 3, 4, 5}.
Puteți lucra acumulând o mulțime de numere (direct rezultatul cerut) sau o mulțime de perechi obținute până la un moment dat, din care extrageți apoi mulțimea numerelor. Varianta a doua e mai generală, funcționează și când spațiul stărilor are cicluri (de exemplu, dacă am avea și instrucțiunile a-=b și b-=a cât timp numerele sunt nenegative). Cum mulțimea perechilor obținute crește la fiecare pas, dar e finită (numerele sunt limitate), puteți adapta funcția de punct fix de aici, folosind equal pentru a compara mulțimi.
Puteți lucra cu mulțimi de perechi de întregi definind modulul

module IntPair = struct
  type t = int * int
  let compare = compare
end
module PS = Set.Make(IntPair)


Marius Minea
Last modified: Tue Oct 18 8:15:00 EET 2016