Probleme Rezolvate

Pe un bilet există 12 poziții care pot fi perforate, aranjate pe 4 linii şi 3 coloane. Să se genereze toate posibilităţile de perforare a celor 12 poziții, astfel încât să nu existe două poziții alăturate neperforate. Indicație. Considerăm mulțimea A, formată din 12 elemente, fiecare element reprezentând o poziție care poate fi perforată, şi mulțimea B={0,1). Se defineşte funcţia f:A→B astfel: dacă poziţia i este perforată, atunci f(i)=1; altfel, f(i)=0. Problema se reduce la generarea produsului cartezian B12 soluția conține o condiție internă suplimentară: poziția k care se adaugă, nu trebuie să fie neperforată (nu trebuie să aibă valoarea 0) dacă poziția k-1 sau poziţia k-3 este neperforată (are valoarea 0).

# include < iostream >
using namespace std ;
int f[ 12 ]; // vectorul în care construim soluția
void init ( int k) {
f[k] = -1 ;
}
int succesor ( int k) {
f[k]++;
if (f[k] <= 1 ) {
return 1 ;
}
return 0 ;
}
int valid ( int k) {
if (k < 2 || f[k -1 ] == 1 || f[k -2 ] == 1 ) {
return 1 ;
}
if (k >= 3 && f[k -3 ] == 0 && f[k -1 ] == 0 && f[k] == 0 ) {
return 0 ;
}
return 1 ;
}
int solutie ( int k) {
return k == 11 ;
}
void tipar () {
for ( int i = 0 ; i < 12 ; i++) {
cout << f[i];
if ((i+ 1 ) % 3 == 0 ) {
cout << endl ;
}
}
cout << endl ;
}
void bt ( int k) {
init (k);
while ( succesor (k)) {
if ( valid (k)) {
if ( solutie (k)) {
tipar ();
} else {
bt (k+ 1 );
}
}
}
}
int main () {
bt ( 0 ); // apelul funcției de backtracking cu k=0
return 0 ;
}

Funcția init () inițializează elementul k din vectorul f cu -1, pentru a indica faptul că încă nu am decis dacă poziția trebuie să fie perforată sau nu.
Funcția succesor() incrementează valoarea elementului k din vectorul f cu 1 și returnează 1 dacă această valoare este validă ( adica 0 sau 1). Dacă am ajuns la valoarea 2, înseamnă că am epuizat toate posibilitățile și trebuie să renunțăm la această ramură.
Funcția valid() verifică dacă valoarea elementului k din vectorul f este validă, adică nu trebuie să fie 0 dacă poziția k-1 sau poziția k-2 sunt neperforate (au valoarea 0). De asemenea, funcția verifică și condiția suplimentară că poziția k nu trebuie să fie neperforată (are valoarea 0) dacă poziția k-1 și poziția k-3 sunt neperforate.
Funcția solutie () verifică dacă am generat o soluție completă, adică am atribuit valori tuturor elementelor din vectorul f . Aceasta este condiția de oprire a algoritmului de backtracking . În acest caz, se apelează funcția tipar() , care afișează soluția.
Funcția tipar() afișează soluția sub forma unei matrici cu 4 linii și 3 coloane. Aceasta afișează valorile elementelor din vectorul f și adaugă un rând nou după fiecare grup de 3 elemente afișate.
În funcția main () , se apelează funcția bt () cu parametrul 0 , pentru a începe algoritmul de backtracking .
Cu acest cod, ar trebui să puteți genera toate posibilitățile de perforare a celor 12 poziții, respectând condiția că nu trebuie să existe două poziții alăturate neperforate.