Fişierul intrare/ieşire:submultimi.in, submultimi.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deGheorgheMihaiMihai Gheorghe GheorgheMihai
Timp execuţie pe test0.2 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.
  • Submulţimea vidă nu se va afişa.

Exemplu

submultimi.insubmultimi.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ă.

Aplicaţii

  1. Jocul Flip
  2. Elimin
  3. Numere3
  4. Numere8
  5. Sortari
  6. Frac
  7. Ture
  8. Zebughil
  9. Sobo
  10. Gather
  11. Boom
  12. Afacere
  13. Reteta
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content