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 ca parametru o mulțime (de exemplu de caractere) și returnează mulțimea părților (submulțimilor) acelei mulțimi.
Indicație Lucrați recursiv și construiți la fiecare pas k toate submulțimile cu primele k elemente. Apoi, păstrând toate elementele (submulțimi) construite, adăugați la fiecare și al k+1-lea element. (Sau numărați invers, de la n în jos până ajungeți la 0).

Pentru a crea modulul de mulțimi de mulțimi, scriem următoarele (exemplul e pentru mulțimi de caractere):

module CS = Set.Make(Char)    (* creaza un modul pentru multimi de caractere *)
module CharSet = struct       (* creaza un modul de tip ordonat *)
  type t = CS.t               (* cu tipul de baza multimi de caractere *)
  let compare = compare
end
module PS = Set.Make(CharSet) (* modulul de multimi de multimi de caractere *)

6. 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.

7. 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.

8. 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:Sun Oct 25 18:00:00 EET 2015