SISergiu Ilincameditații informatică
Meniu

clasa a XI-a · Metoda backtracking · lecția 7

Backtracking (2): aranjamente, combinări, submulțimi, produs cartezian

60 minmate-info

Înainte de lecția asta: XI.6 Backtracking (1): principiul metodei și generarea permutărilor

Ce vei ști după lecție

  • Adaptezi schema de backtracking pentru aranjamente, combinări, submulțimi și produs cartezian.
  • Știi formulele de numărare (Aₙᵏ, Cₙᵏ, 2ⁿ, nᵏ) și le folosești la grile.
  • Generezi de mână soluțiile în ordine lexicografică și găsești a k-a soluție.
  • Reformulezi o problemă „cu povești” ca una dintre generările standard.

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a XI-aLecția 7 din 21 · mai sunt 14Urmează: XI.8 · Backtracking (3): partiții, plata unei sume, paranteze și backtracking în planVezi toate lecțiile
Cuprins

1. Patru generări, o singură schemă

Sunt patru probleme-tip care apar iar și iar, la clasă și la Bac. Toate se rezolvă cu aceeași schemă din lecția anterioară; se schimbă doar ce valori încercăm și când avem soluție.

Generare Ce înseamnă Exemplu (n = 3, K = 2) Număr de soluții
produs cartezian K poziții, fiecare din {1..n}, cu repetiții 11 12 13 21 22 … 33 nᴷ
aranjamente K valori distincte, ordinea contează 12 13 21 23 31 32 A(n, K) = n!/(n−K)!
combinări K valori distincte, ordinea NU contează 12 13 23 C(n, K) = n!/(K!(n−K)!)
submulțimi orice număr de elemente {1} {1,2} {1,2,3} {1,3} … 2ⁿ (cu mulțimea vidă)

Comparație

Sfat

Cum le deosebești într-un enunț: „contează ordinea?” (12 ≠ 21 → aranjamente) și „se pot repeta?” (11 permis → produs cartezian). Combinările se generează strict crescător, ca să nu apară aceeași grupă de două ori (12 și 21).

2. Produs cartezian

Nicio condiție: orice valoare este bună pe orice poziție. K este numărul de poziții.

#include <iostream>
using namespace std;

int x[20], n, K;

void afisare()
{
    for (int i = 1; i <= K; i++) cout << x[i] << ' ';
    cout << '\n';
}

void back(int k)
{
    for (int v = 1; v <= n; v++)
    {
        x[k] = v;                      // orice valoare e validă
        if (k == K) afisare();
        else back(k + 1);
    }
}

int main()
{
    cin >> n >> K;
    back(1);
    return 0;
}

De ce așa?

De ce nu există valid? Produsul cartezian nu impune nicio relație între elemente: fiecare poziție poate fi aleasă independent. Numărul de soluții este nᴷ (n variante pentru fiecare dintre cele K poziții). Parolele de 4 cifre sunt 10⁴.

3. Aranjamente

Ca la permutări (valori distincte), dar soluția are K elemente: if (k == K).

#include <iostream>
using namespace std;

int x[20], n, K;

bool valid(int k)
{
    for (int i = 1; i < k; i++)
        if (x[i] == x[k]) return false;
    return true;
}

void back(int k)
{
    for (int v = 1; v <= n; v++)
    {
        x[k] = v;
        if (valid(k))
        {
            if (k == K)
            {
                for (int i = 1; i <= K; i++) cout << x[i] << ' ';
                cout << '\n';
            }
            else back(k + 1);
        }
    }
}

int main()
{
    cin >> n >> K;
    back(1);
    return 0;
}

De ce așa?

De ce aranjamentele cu K = n sunt chiar permutări? Dacă luăm toate cele n elemente și le așezăm pe n poziții, fără repetiții, obținem permutările (lecția XI.6). Permutările sunt cazul particular A(n, n) = n!.

4. Combinări

Dacă ordinea nu contează, {1, 2} și {2, 1} sunt aceeași grupă. Ca să o generăm o singură dată, cerem ca valorile să fie strict crescătoare: bucla pornește de la x[k − 1] + 1 (cu x[0] = 0).

Arborele combinărilor

#include <iostream>
using namespace std;

int x[20], n, K;

void back(int k)
{
    for (int v = x[k - 1] + 1; v <= n; v++)       // mai mare decât precedentul
    {
        x[k] = v;
        if (k == K)
        {
            for (int i = 1; i <= K; i++) cout << x[i] << ' ';
            cout << '\n';
        }
        else back(k + 1);
    }
}

int main()
{
    cin >> n >> K;
    back(1);                                       // x[0] = 0 (global)
    return 0;
}

De ce așa?

De ce x[k − 1] + 1? Dacă fiecare valoare este mai mare decât precedenta, fiecare grupă apare într-o singură ordine (cea crescătoare). Pentru {1, 2}: doar 1 2, niciodată 2 1. Nu mai avem nevoie nici de valid: valorile strict crescătoare sunt automat distincte. De ce x[0] = 0? La prima poziție nu avem „precedent”: cu x[0] = 0, prima valoare încercată este 1.

De știut

Optimizare. Pe poziția k nu are rost să încercăm valori mai mari decât n − K + k: nu ar mai rămâne destule valori pentru pozițiile următoare. Pentru n = 5, K = 3: x[1] ≤ 3, x[2] ≤ 4, x[3] ≤ 5.

#include <iostream>
using namespace std;

int x[20], n, K, optim, solutii, apeluri;

void back(int k)
{
    apeluri++;
    int sus = optim ? n - K + k : n;             // limita superioară pentru x[k]
    for (int v = x[k - 1] + 1; v <= sus; v++)
    {
        x[k] = v;
        if (k == K) solutii++;
        else back(k + 1);
    }
}

int main()
{
    cin >> n >> K >> optim;
    back(1);
    cout << solutii << ' ' << apeluri;
    return 0;
}

Același număr de soluții (C(5, 3) = 10), dar 16 apeluri fără optimizare și 10 cu ea: prin tăierea ramurilor fără ieșire, căutarea se face mai repede.

Intrare / ieșire

Intrare Ieșire
2 2 (produs cartezian) 1 1
1 2
2 1
2 2
3 2 (aranjamente) 1 2
1 3
2 1
2 3
3 1
3 2
4 2 (combinări) 1 2
1 3
1 4
2 3
2 4
3 4

5. Submulțimi

Fiecare prefix strict crescător x[1..k] este o submulțime. Așa că afișăm la fiecare pas, nu doar la final.

Submulțimi

#include <iostream>
using namespace std;

int x[20], n;

void back(int k)
{
    for (int v = x[k - 1] + 1; v <= n; v++)
    {
        x[k] = v;
        for (int i = 1; i <= k; i++) cout << x[i] << ' ';     // x[1..k] este o submulțime
        cout << '\n';
        back(k + 1);                                          // și încercăm să o prelungim
    }
}

int main()
{
    cin >> n;
    back(1);
    return 0;
}

De ce așa?

De ce afișăm la fiecare pas? O submulțime poate avea oricâte elemente (1, 2, …, n), iar fiecare prefix crescător este una. Programul nu are „caz de bază” explicit: când v depășește n, bucla nu mai rulează și funcția se termină. Mulțimea vidă (ignorată aici) se poate afișa o dată, în main. Varianta „cu 0 și 1”: x[i] = 1 dacă i e în submulțime și 0 altfel: produs cartezian cu valorile {0, 1} și K = n; pentru {1, 3} din {1, 2, 3} se obține 1 0 1.

6. Grile de Bac: cum le rezolvi

„Utilizând metoda backtracking se generează toate numerele de 3 cifre distincte, formate cu cifre din mulțimea {1, 3, 5, 7}. Primele numere generate sunt 135, 137, 153. Care este al 8-lea număr generat?”

  1. Recunoaște tipul: cifre distincte, ordinea contează → aranjamente de 4 luate câte 3 (24 de soluții).
  2. Scrie soluțiile în ordine până la a 8-a: 135, 137, 153, 157, 173, 175, 315, 317 → al 8-lea este 317.

Blocuri

La BAC

Scurtătură: pe prima poziție, fiecare cifră „acoperă” un bloc de A(3, 2) = 6 soluții. Soluțiile 1–6 încep cu 1, 7–12 cu 3. Deci a 8-a este a doua din blocul lui 3 → 317. Folosește blocurile ca să ajungi repede la soluția cerută, fără să le scrii pe toate.

#include <iostream>
using namespace std;

int c[] = {0, 1, 3, 5, 7};             // cifrele disponibile (indice de la 1)
int x[10], n = 4, K = 3, nr, tinta;

bool valid(int k)
{
    for (int i = 1; i < k; i++)
        if (x[i] == x[k]) return false;
    return true;
}

void back(int k)
{
    for (int v = 1; v <= n; v++)
    {
        x[k] = v;
        if (valid(k))
        {
            if (k == K)
            {
                nr++;
                if (nr == tinta)
                {
                    for (int i = 1; i <= K; i++) cout << c[x[i]] << ' ';
                }
            }
            else back(k + 1);
        }
    }
}

int main()
{
    cin >> tinta;
    back(1);
    return 0;
}

De ce așa?

De ce generăm indici (x[k] între 1 și n) și nu cifrele direct? Algoritmul lucrează cu pozițiile 1..n din mulțimea dată; abia la afișare traducem poziția într-o cifră cu c[x[k]]. Așa același program merge pentru orice mulțime (litere, nume, valori).

Alte întrebări frecvente: „Câte soluții au proprietatea …?” (numeri pe blocuri sau cu formule), „Care este soluția generată imediat înaintea / după …?”, „Câte soluții se generează în total?”.

7. Probleme „cu povești”, generări standard

Enunț Este de fapt…
toate echipele de 3 elevi dintr-o clasă de 10 combinări C(10, 3)
toate podiumurile (aur, argint, bronz) din 8 sportivi aranjamente A(8, 3)
toate parolele de 4 cifre produs cartezian 10⁴
toate parolele de 4 cifre distincte aranjamente A(10, 4) = 5 040
toate meniurile alese dintr-o listă de preparate submulțimi 2ⁿ

8. Greșeli frecvente

Greșeala Efect Corect
combinări cu for (v = 1; …) apar și 12 și 21 for (v = x[k−1] + 1; …)
aranjamente cu if (k == n) soluții de lungime greșită if (k == K)
uiți că x[0] trebuie să fie 0 prima valoare nu e 1 global, inițializat cu 0
submulțimi: afișezi doar la k == K lipsesc submulțimile mai scurte afișezi la fiecare pas
confunzi „ordinea contează” număr greșit de soluții întreabă: 12 ≠ 21?
nu optimizezi limita superioară timp mai mare v <= n − K + k

9. La BAC

La BAC

Acestea sunt cele mai frecvente grile din Subiectul I de informatică la clasa a XI-a: se dă o generare (cifre distincte, cuvinte din litere, combinări de numere) și se cere „a câta soluție este …”, „care este soluția următoare”, „câte soluții respectă condiția X”. Rezolvarea standard: recunoști tipul, folosești blocurile ca să sari direct, scrii doar soluțiile necesare.

10. Exersează pe hârtie

Răspunsurile sunt la final: încearcă întâi singur.

1. Generează de mână combinările de 5 luate câte 3. Câte sunt? Care este a 7-a?

2. Se generează submulțimile lui {1, 2, 3, 4} (nevide, în ordinea din lecție). Care submulțime urmează după {1, 3, 4}?

3. Câte dintre șirurile de 4 litere din {a, b} conțin exact două litere a?

4. Câte soluții au: aranjamentele de 5 luate câte 3? combinările de 5 luate câte 3? produsul cartezian cu 5 valori și 3 poziții? submulțimile lui {1, ..., 5}?

5. (BAC) Pentru generarea din secțiunea 6 (cifrele 1, 3, 5, 7), care este al 20-lea număr generat?

6. Se generează numerele de 3 cifre formate cu cifrele 1, 2, 3 (nu neapărat distincte), în ordine crescătoare. Care este al 10-lea?

7. La combinări de 6 luate câte 4, care este valoarea maximă pe care o poate lua x[2], conform optimizării n − K + k?

8. Câte echipe de 5 elevi se pot forma dintr-o clasă de 28? Dar câte echipe de 5 elevi cu un căpitan ales (5 variante)?

9. Scrie submulțimile lui {1, 2, 3} ca șiruri de 0 și 1 (de lungime 3). Ce șir corespunde submulțimii {1, 3}?

10. Pentru ce valori ale lui K aranjamentele A(n, K) și combinările C(n, K) au același număr de soluții?

11. Mai departe (pentru cine vrea mai mult)

Combinările cu repetiții. Alegi K elemente dintre n, cu repetiții, fără să conteze ordinea (de exemplu 3 bile din 4 culori: 112, 123, 333…). Se obțin cu aceeași schemă, dar bucla pornește de la x[k − 1] (nu x[k − 1] + 1).

Generarea cu biți. Orice submulțime a unei mulțimi de n ≤ 20 elemente se poate reprezenta printr-un număr mask de la 0 la 2ⁿ − 1: bitul i este 1 dacă elementul i este în submulțime. Parcurgi for (mask = 0; mask < (1 << n); mask++) și testezi biții cu mask & (1 << i). Nu e recursiv și e foarte folosit la concursuri.

Triunghiul lui Pascal și C(n, K). Formula C(n, K) = C(n − 1, K − 1) + C(n − 1, K) permite să calculezi numărul de combinări fără factoriale (cu o matrice), evitând depășirea lui int (vezi lecția X.9).

Numere mari de soluții. Pentru n = 20, K = 10 sunt 184 756 de combinări: încă rezonabil. Pentru n = 30, 2ⁿ ≈ 10⁹: backtracking-ul nu mai este fezabil dacă trebuie să afișezi toate soluțiile.

Rezumat

  • Produs cartezian: orice valoare (nᴷ). Aranjamente: valori distincte, K poziții (A(n, K)). Combinări: strict crescătoare, bucla de la x[k−1] + 1 (C(n, K)). Submulțimi: crescătoare + afișare la fiecare pas (2ⁿ).
  • Întrebări-cheie: ordinea contează? Se pot repeta valorile?
  • Grile: folosește blocurile (A(n−1, K−1) soluții per prima valoare) ca să sari direct la soluția cerută.
  • Optimizare: v ≤ n − K + k taie ramuri fără ieșire.

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 110 min

Backtracking: permutări, aranjamente, combinări, submulțimi, partiții

  • Recunoști generarea din enunț și numeri soluțiile cu formulă sau pe blocuri.
  • Răspunzi la grilele BAC: a câta soluție, ce urmează după, ce este înainte, câte au o proprietate.
  • Adaptezi schema `back(k)` la condiții noi: sumă dată, vecini, poziții interzise.

Fișa acoperă și: XI.6, XI.8

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • aranjamente#196

    ușoară
  • combinari#197

    ușoară
  • submultimi#198

    ușoară
  • produscartezian1#1277

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • produscartezian2#1278

    ușoară
  • submultimi1#1286

    ușoară
  • combinari2#3152

    ușoară
  • cifregen#1287

    ușoară
  • cifregen2#1289

    ușoară
  • cifre-bin-back#3162

    ușoară
  • subimp1#3247

    ușoară

Pentru cei care vor mai mult

  • sirab#1355

    ușoară
  • numere123#3158

    ușoară

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. 10 combinări: 123, 124, 125, 134, 135, 145, 234, 235, 245, 345. A 7-a este 234.

2. Ordinea: {1}, {1,2}, {1,2,3}, {1,2,3,4}, {1,2,4}, {1,3}, {1,3,4}, {1,4}, {2}, …. După {1,3,4} urmează {1,4}.

3. 6 (alegi pozițiile celor două litere a: C(4, 2) = 6): aabb, abab, abba, baab, baba, bbaa.

4. Aranjamente: 5·4·3 = 60. Combinări: 60/3! = 10. Produs cartezian: 5³ = 125. Submulțimi: 2⁵ = 32 (cu mulțimea vidă; 31 fără ea).

5. 715: blocul lui 7 are soluțiile 19–24 (713, 715, 731, 735, 751, 753); a 20-a este a doua din bloc.

6. 211: șirurile încep 111, 112, 113, 121, 122, 123, 131, 132, 133, 211: a 10-a este 211.

7. x[2] ≤ n − K + k = 6 − 4 + 2 = 4 (pe pozițiile 3 și 4 mai trebuie două valori mai mari).

8. C(28, 5) = 28·27·26·25·24 / 120 = 98 280 echipe. Cu un căpitan ales: 98 280 · 5 = 491 400.

9. 000, 001, 010, 011, 100, 101, 110, 111 (8 șiruri). Submulțimii {1, 3} îi corespunde 101.

10. A(n, K) = C(n, K) · K!, deci sunt egale doar când K! = 1, adică K = 0 sau K = 1.