Metoda backtracking: cum merge și în ce ordine generează (doar matematică-informatică)

Pe scurt

2 minesențialul, de recitit oricând

Culorile din lecție:termencifră, datăidee-cheie

• Doar la matematică-informatică. Capitolele 9 și 10 din programă nu apar la științele naturii.
• Backtracking înseamnă: construiești soluția poziție cu poziție și, când nu mai poți continua, te întorci un pas.
• În cele 23 de lucrări MI din 2023-2027, apare câte un item în fiecare lucrare: de 17 ori la Subiectul I (4 p) și de 6 ori la II.2 (6 p).
• La aceste lucrări nu ți se cere programul. Ți se dau primele soluții și ți se cere o soluție anume. Tot ce ai nevoie e regula ordinii.

Urmează · 2 min

Ideea, apoi numele oficial

2 min

Ai uitat cifrul unui lacăt cu 3 rotițe și știi că are cifre diferite. Pui 1 pe prima rotiță. Pui 1 pe a doua: nu merge, cifrele trebuie să fie diferite, deci treci la 2. Pe a treia încerci 1, 2 și ajungi la 3. Ai o soluție. Când s-au terminat cifrele de pe o rotiță, te întorci la rotița de dinainte și o schimbi.

Oficial: valorile rotițelor sunt elementele tabloului x, numit și stivă. Testul „nu se repetă” este condiția de continuare. Întoarcerea la rotița de dinainte e pasul care dă numele metodei, backtracking.

Urmează · 2 min

Schema, recursivă și iterativă

3 min 2 întrebări la final

Programa cere metoda „iterativă sau recursivă”. Exemplul de mai jos generează permutările mulțimii 1, 2, ..., n.

int x[20],n;

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

void afis()
{ for(int i=1;i<=n;i++)
    cout<<x[i]<<" ";
  cout<<endl;
}

void bt(int k)
{ for(int v=1;v<=n;v++)
  { x[k]=v;
    if(valid(k))
      if(k==n) afis();
      else bt(k+1);
  }
}

Apelul este bt(1). Pentru n=3, ordinea soluțiilor este 123, 132, 213, 231, 312, 321.

Aceeași logică, fără recursivitate:

void bt()
{ int k=1;
  x[1]=0;
  while(k>0)
  { x[k]++;
    if(x[k]>n) k--;
    else if(valid(k))
      if(k==n) afis();
      else
      { k++;
        x[k]=0;
      }
  }
}

În Pascal, schema e aceeași: procedure bt(k:integer);, cu for v:=1 to n do.

Oportunitate. Metoda e potrivită când trebuie să enumeri toate soluțiile sau să găsești una printre foarte multe posibilități. Numărul de soluții crește foarte repede, iar pentru n=20 nici măcar nu poți afișa toate permutările. Dacă ți se cere doar câte sunt, de obicei e mai bună o formulă.

Urmează · 3 min

Regula ordinii

2 min

Soluțiile vin ca pe un contor de kilometri: poziția din dreapta se schimbă cel mai des.

1. Stabilești ordinea elementelor
   Din mulțimea ordonată din enunț. Dacă nu e spusă, o deduci din primele soluții.
2. Înțelegi condițiile
   Ce se poate repeta, cât de lungă e o soluție, ce perechi nu pot sta împreună.
3. Cauți poziția cea mai din dreapta care poate crește
   Încerci să o mărești la următoarea valoare care respectă condițiile.
4. Umpli ce rămâne
   Pozițiile de după iau cele mai mici valori permise, de la stânga la dreapta.

Urmează · 2 min

Oficial: rezervă 2026, varianta 5, II.2

3 min

Un cifru are 5 cifre distincte, iar oricare două cifre alăturate au parități diferite. Soluțiile sunt în ordine lexicografică: 01234, 01236, 01238, 01254, 01256, 01258. Se cere soluția generată imediat înainte și imediat după 16789.

Cifrele alternează aici: impară, pară, impară, pară, impară.

Înainte. Ultima cifră, 9, poate scădea. Trebuie să rămână impară și nefolosită. 7 e folosit, deci urmează 5: 16785.

După.

• 9 nu poate crește: e cea mai mare cifră.
• 8 nu poate crește: e cea mai mare cifră pară.
• 7 poate deveni 9, pentru că 9 a rămas liberă după ce ai eliberat ultima poziție. Începutul e acum 169.
• A patra poziție ia cea mai mică cifră pară liberă, 0. A cincea ia cea mai mică cifră impară liberă, 3, pentru că 1 e folosit. Rezultă 16903.

Barem: câte 3 p pentru fiecare soluție, 16785 și 16903.

Urmează · 3 min

Oficial: iunie 2026, varianta 3, II.2

2 min

Din mulțimea ordonată {broșură, ghid, pliant, revistă} se generează seturi de cel mult trei materiale, fără pliant și revistă împreună. Primele cinci: (broșură), (broșură, ghid), (broșură, ghid, pliant), (broșură, ghid, revistă), (broșură, pliant). Se cer a șasea și a șaptea.

• Soluțiile au lungimi diferite. (broșură, pliant) nu poate continua cu revistă, deci urmează (broșură, revistă).
• Revista e ultimul element, deci nu mai are ce adăuga. Toate seturile care încep cu broșură s-au terminat, iar următorul e (ghid).

Barem: câte 3 p pentru fiecare soluție.

Urmează · 2 min

Oficial: august 2024, varianta 8, II.2

3 min

Buchete de câte trei flori distincte din mulțimea ordonată astfel: {trandafir, crin, gerbera, iris, eustoma, orhidee, zambilă}. Crinul nu poate fi cu eustoma sau cu zambila. Se cer soluțiile imediat înainte și imediat după (crin, gerbera, orhidee).

Scrie sub fiecare floare un număr: trandafir 1, crin 2, gerbera 3, iris 4, eustoma 5, orhidee 6, zambilă 7. Într-un buchet, numerele merg crescător.

• (crin, gerbera, orhidee) este 2, 3, 6. Înainte ar veni 2, 3, 5, adică eustoma, dar crinul nu poate sta cu ea. Deci 2, 3, 4: (crin, gerbera, iris).
• După ar veni 2, 3, 7, adică zambila, dar nici ea nu poate sta cu crinul. Crește a doua poziție, la 4. A treia ar lua 5, tot eustoma, deci ia 6: (crin, iris, orhidee).

Barem: câte 3 p pentru fiecare soluție.

Urmează · 3 min

Oficial: grile cu ultima sau penultima soluție

6 min o întrebare la final

August 2025, varianta 4, I.3. Șase perechi de dans A-F, A prima și F ultima, iar se cere ultima soluție. Pozițiile din mijloc iau valorile cele mai mari, în ordine descrescătoare: (A, E, D, C, B, F), varianta c.

Simulare 2026, I.4. Bilete numerotate de la 30 la 1, în această ordine, câte șase, anunțate în ordine descrescătoare. Primele sunt (30,29,28,27,26,25), (30,29,28,27,26,24). Se cere penultima. Ultima este (6,5,4,3,2,1), singura soluție care începe cu 6. Înaintea ei sunt soluțiile care încep cu 7, iar ultima dintre ele se termină cu cele mai mici numere: (7,5,4,3,2,1), varianta d. Atenție, ordinea e 30, 29, ..., deci un număr mai mare vine mai devreme.

Sesiunea specială 2023, varianta 6, I.4. Șiruri de 5 litere distincte din {A, M, U, R, G}, cu R înaintea lui A și a lui M. Primele sunt URAMG, URAGM, URMAG, URMGA, URGAM. Se cere soluția de după GURMA. Ultimele trei litere, R, M, A, sunt deja în ordinea cea mai târzie posibilă, deci nu pot crește. Crește a doua poziție: după U urmează R. Restul se umple în ordinea mulțimii: A, M, U. Rezultă GRAMU, varianta b. Ordinea A, M, U, R, G nu e cea alfabetică, iar primele soluții o confirmă.

Simulare 2024, I.3. Patru sume nenule, mai mici decât 10, strict crescătoare, cu totalul 24. Se cere soluția de după (3,6,7,8). Cu prima sumă 3, a doua nu mai poate crește: (3,7,8,9) are totalul 27. Prima devine 4, următoarele iau cele mai mici valori, 5 și 6, iar ultima e ce rămâne: 24-15 = 9. Rezultă (4,5,6,9), varianta b.

Urmează · 6 min

Ce se cere la BAC

3 mincum apare la examen

Felurile de mulțimi, permutări, aranjamente, combinări și celelalte, sunt în lecția următoare.

Urmează · 3 min

Greșeli care costă puncte

1 mincapcanele de evitat

• Folosești alfabetul în loc de ordinea din enunț.
• Nu verifici pe primele soluții: regula ta trebuie să le obțină exact pe acelea.
• Uiți o condiție după ce ai schimbat o poziție.
• Sari peste soluțiile scurte, când lungimea nu e fixă.
• Numerotezi greșit pozițiile când enunțul spune „imediat înainte”.
• Scrii o singură soluție la II.2, deși se punctează separat.

Urmează · 1 min