Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | submultimi.in, submultimi.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Mihai Gheorghe •GheorgheMihai |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Submultimi
Fie mulţimea An = {1, 2, 3, ..., n}. Se cere să se determine toate submulţimile mulţimii An.
Date de intrare
Fişierul de intrare submultimi.in conţine pe prima linie numărul natural n, reprezentând numărul elementelor din mulţime.
Date de ieşire
Fişierul de ieşire submultimi.out conţine toate submulţimile mulţimii An.
Restricţii
- 1 ≤ n ≤ 16.
- Submulţimile se pot afişa în orice ordine.
Exemplu
| submultimi.in | submultimi.out |
|---|---|
| 3 | 1 1 2 1 2 3 1 3 2 2 3 3 |
Indicaţii de rezolvare
Problema este o aplicatie a metodei backtracking. Aceasta solutie garanteaza generarea submultimilor in ordine lexicografica.
Problema se mai poate rezolva si folosind reprezentarea binara a numerelor. Daca suntem la submultimea i si daca al j-1-lea bit din numar este 1 atunci j va face parte din submultimea i. Exemplu: daca i=5, 5(2)=101 deci elementele 1 si 3 fac parte din submultimea a 5-a. O sursa ce foloseste aceasta idee poate fi gasita aici.
O alta idee de rezolvare poate fi cea de la problema combinari, generandu-se toate combinarile de n luate cate k, unde k ia pe rand valori de la 1 la n. Toate combinarile de n luate cate k sunt de fapt toate submultimile cu k elemente. O sursa ce foloseste aceasta idee poate fi gasita aici.
Se observa ca daca sortam submultimile in ordine lexicografica, primele 2n-1 submultimi incep cu cifra 1, urmatoarele 2n-2 submultimi incep cu cifra 2, ... , ultima submultime incepe cu cifra n. Daca se stie numarul unei submultimi, dupa ce acestea au fost sortate in ordine lexicografica, se pot afla elementele submultimii. O sursa ce foloseste aceasta idee poate fi gasita aici.
