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)