Mulțimi

Mulțimi implementate cu liste

Deși listele și mulțimile sunt noțiuni distincte, putem folosi liste pentru a reprezenta mulțimi. Pentru exerciții simple, vom putea astfel specifica mulțimile direct.

1. Scrieți o funcție care ia ca parametri două liste (presupuse fără duplicate) reprezentând mulțimi și returnează produsul lor cartezian, deasemenea în formă de listă.

2. Scrieți o funcție care ia ca parametru o listă reprezentănd o mulțime, și produce mulțimea submulțimilor ei, reprezentată ca listă de liste.

Lucrul cu modulul Set în OCaml

OCaml permite definirea de mulțimi dacă tipul elementelor e ordonat -- e necesar în reprezentarea internă.
Pe scurt, putem defini un modul S pentru mulțimi de șiruri scriind

module S = Set.Make(String)

Mai în detaliu, modulul Set oferă un functor, Set.Make care ia ca parametru un modul (aici String) având la bază un tip ordonat (aici string), și returnează un modul pentru lucru cu mulțimi particularizat pentru acest tip.

Putem acum să folosim valoarea S.empty și funcții cum ar fi S.add, S.union, și altele.

Dacă dorim să lucrăm cu mulțimi de întregi, va trebui să creăm întâi un modul:

module Int = struct
  type t = int          (* tipul de baza *)
  let compare = compare (* functia standard de comparare *)
end

apoi se poate defini module IS = Set.Make(Int) și folosi IS.empty, etc.

3. Se poate scrie o funcție care construiește mulțimea elementelor unei liste (ignorând deci duplicatele), astfel:

let rec set_of_list = function
  | [] -> S.empty
  | h :: t -> S.add h (set_of_list t)

Rescrieți funcția set_of_list folosind iteratorul List.fold_left pentru a parcurge elementele listei. Porniți cu argumentul inițial S.empty în care se vor acumula apoi elementele.

4. Scrieți o funcție care ia ca parametru o mulțime de șiruri ș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. Dintre funcțiile predefinite în modulul Pervasives, deschis implicit, puteți folosi print_string, print_char și print_newline .

5. Un calculator memorează două valori a și b și poate executa 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 valorilor care se pot obține cu aceste instrucțiuni pornind de la a și b, nedepășind lim .
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)

6. Un număr natural descompus în factori primi poate fi reprezentat ca listă 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.

Marius Minea

Last modified: Sat Oct 19 20:05:00 EEST 2013