Problemă rezolvată matrice clasa a XI-a mate-info neintensiv

Enunț

Se citește de la tastatură un nr. natural nenul n. Scrieți un program care să genereze n submulțimi disjuncte (fără nici un element comun), având fiecare câte n elemente din mulțimea {1,2,...,n²}, submulțimi pentru care suma elementelor este aceeași.

Exemplu: pentru n=4, pe mulțimea {1,2,...,15,16}, submulțimile cerute sunt: {1,6,11,16}, {4,5,10,15}, {3,8,9,14} și {2,7,12,13}, toate aceste submulțimi având suma elementelor egală cu 34.

Rezolvare

Cod sursă

Cu colorare de sintaxă, aici. Scrie în fișier.

Ieșire pt. n = 4: click aici.

Note

- această rezolvare dă primele rezultate pentru n = 4 după aprox. 2min;
- această rezolvare dă mai multe soluții valide, nu doar prima, folosind metoda backtracking de două ori, dar se poate modifica ușor să afișeze o singură soluție.

Explicație

Funcția back

- este o funcție backtracking;

- generează toate combinările de N luate câte P (se cer submulțimi neordonate disjuncte, în exemplul dat, din mulțimea {1, 2, ..., 15, 16}, submulțimile având 4 elemente fiecare);

- reține combinările în vectorul de vectori (matrice) Sols care este transmis prin referință (folosind operatorul &);

- combinarea curentă (sau stiva din backtracking) este tabloul unidimensional Sol care implicit este transmis ca referință;

- în Sol valorile care contează se rețin de la indicele 1 în sus, dar în Sols se introduc de la indicele 0.

Funcția back2

- este o funcție backtracking;

- generează toate posibilitățile de n (=4) mulțimi de submulțimi de n (=4) elemente disjuncte care au aceeași sumă a elementelor;

- vectorul Sols este primit din funcția main care îl primește de la funcția back explicată mai sus

- vectorul SolFin este stiva din backtracking care conține indici din Sols;

- vectorul Fol este un vector de prezență, fiecărui indice corespunzându-i true sau false, valoare care indică dacă indicele (o valoare de la 1 la 16 în exemplul dat) este prezent în setul curent de submulțimi (din SolFin);

- suma este suma primei submulțimi din SolFin cu care se compară apoi sumele celorlalte submulțimi care se pun pe stivă;

- se folosesc metodele push_back (adaugă la sfâșit) și pop_back (scoate ultima valoare din vector);

- se are grijă ca la punerea unei submulțimi în stiva SolFin să nu existe elemente în ea care deja sunt folosite (dacă există, nu se pune ci se face un salt cu instrucțiunea continue, la fel și când suma locală este diferită de parametrul suma);

- se are grijă ca la ieșirea din recursivitate să se marcheze elementele care înainte erau folosite, ca nefolosite.