Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-12-18 16:00:46.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:submultimi.in, submultimi.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deGheorgheMihaiMihai Gheorghe GheorgheMihai
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

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.insubmultimi.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. O solutie de 100 de puncte poate fi gasita aici.

Problema se mai poate rezolva si folosind reprezentarea binara a numerelor, daca al i-1-lea bit din numar este 1 atunci i va face parte din acea submultime. Exemplu: 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. 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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?