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
Această problemă este o aplicaţie a metodei backtracking. Aici se găseşte o soluţie ce garantează generarea submulţimilor în ordine lexicografică.
Aplicaţia se mai poate rezolva şi folosind reprezentarea binară a numerelor. Recomand următorul articol ce tratează în detaliu aceste operaţii: „Optimizarea programelor folosind operaţii pe biţi”. Dacă suntem la submulţimea cu indicele idx, dacă al (j-1)-lea bit din număr este 1, atunci j va face parte din submulţimea cu indexul idx. Iată un exemplu: dacă idx = 5 avem următoarea reprezentare în baza 2 a acestui index: 5(2) = 101. În concluzie, elementele 1 şi 3 fac parte din submulţimea a 5-a. O sursă ce foloseşte această idee poate fi găsită aici.
O altă idee de rezolvare poate fi cea de la problema Combinări, generându-se toate combinările de n luate câte k, unde k ia pe rând valori de la 1 la n. Toate combinările de n luate câte k sunt de fapt toate submulţimile cu k elemente. O sursă ce foloseşte această idee poate fi găsită aici.
Se observă că dacă sortăm submulţimile în ordine lexicografică, primele 2n-1 submulţimi încep cu cifra 1, următoarele 2n-2 submulţimi încep cu cifra 2, ... , ultima submulţime începe cu cifra n. Dacă se ştie numărul unei submulţimi, după ce acestea au fost sortate în ordine lexicografică, se pot afla elementele submulţimii. O sursă ce foloseşte această idee poate fi gasită aici.
Menţionăm în final că, indiferent de ideea de rezolvare folosită, soluţiile au complexitate exponenţială.
