Mulțimi

Modulul Set (documentația OCaml)

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

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

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

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ă 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)

Marius Minea
Last modified: Mon Oct 13 23:10:00 EEST 2014