Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Metoda backtraking |
# include < iostream >
# include < fstream >
using namespace std ;
int n, m;
string nume[ 100 ]; // vectorul cu numele persoanelor
int aranjament[ 100 ]; // vectorul în care construim aranjamentul
int viz [ 100 ]; // vectorul auxiliar pentru a evita duplicatele
void init ( int k) {
aranjament[k] = -1 ;
}
int succesor ( int k) {
aranjament[k]++;
if (aranjament[k] < n) {
return 1 ;
}
return 0 ;
}
int valid ( int k) {
if ( viz [aranjament[k]] == 0 ) {
return 1 ;
}
return 0 ;
}
int solutie ( int k) {
return k == m -1 ;
}
void tipar () {
for ( int i = 0 ; i < m; i++) {
cout << nume[aranjament[i]] << " " ;
}
cout << endl ;
}
void bt ( int k) {
init (k);
while ( succesor (k)) {
if ( valid (k)) {
viz [aranjament[k]] = 1 ;
if ( solutie (k)) {
tipar ();
} else {
bt (k+ 1 );
}
viz [aranjament[k]] = 0 ;
}
}
}
int main () {
ifstream fin ( "input.txt" ) ;
fin >> n >> m;
for ( int i = 0 ; i < n; i++) {
fin >> nume[i];
}
fin. close ();
bt ( 0 ); // apelul funcției de backtracking cu k=0
return 0 ;
}
# include < fstream >
using namespace std ;
int n, m;
string nume[ 100 ]; // vectorul cu numele persoanelor
int aranjament[ 100 ]; // vectorul în care construim aranjamentul
int viz [ 100 ]; // vectorul auxiliar pentru a evita duplicatele
void init ( int k) {
aranjament[k] = -1 ;
}
int succesor ( int k) {
aranjament[k]++;
if (aranjament[k] < n) {
return 1 ;
}
return 0 ;
}
int valid ( int k) {
if ( viz [aranjament[k]] == 0 ) {
return 1 ;
}
return 0 ;
}
int solutie ( int k) {
return k == m -1 ;
}
void tipar () {
for ( int i = 0 ; i < m; i++) {
cout << nume[aranjament[i]] << " " ;
}
cout << endl ;
}
void bt ( int k) {
init (k);
while ( succesor (k)) {
if ( valid (k)) {
viz [aranjament[k]] = 1 ;
if ( solutie (k)) {
tipar ();
} else {
bt (k+ 1 );
}
viz [aranjament[k]] = 0 ;
}
}
}
int main () {
ifstream fin ( "input.txt" ) ;
fin >> n >> m;
for ( int i = 0 ; i < n; i++) {
fin >> nume[i];
}
fin. close ();
bt ( 0 ); // apelul funcției de backtracking cu k=0
return 0 ;
}
În acest cod, citim dintr-un fișier text numărul de persoane n , numărul de scaune m și numele persoanelor dintr-un vector nume .
Funcția init () inițializează elementul k din vectorul aranjament cu -1, pentru a indica faptul că încă nu am decis cine va ocupa scaunul.
Funcția succesor() incrementează valoarea elementului k din vectorul aranjament cu 1 și returnează 1 dacă această valoare este validă ( adica este mai mică decât n ). Dacă am ajuns la valoarea n , înseamnă că am epuizat toate posibilitățile și trebuie să renunțăm la această ramură.
În funcția valid() , se verifică dacă valoarea elementului k din vectorul aranjament (adică indexul persoanei) a fost deja marcată ca vizitată în vectorul viz . Dacă elementul nu a fost vizitat, atunci returnăm 1, ceea ce indică că putem continua să explorăm această ramură.
Dacă elementul a fost deja vizitat, atunci returnăm 0, ceea ce indică că nu putem continua pe această ramură și trebuie să ne întoarcem la nivelul anterior.
După ce am verificat valabilitatea elementului curent, îl marcam ca vizitat în vectorul viz , pentru a evita să mai folosim aceeași persoană în aranjament în continuare.
După ce am generat toate soluțiile care conțin elementul curent, resetăm marcajul din vectorul viz pentru a ne pregăti pentru explorarea altor ramuri.
Fișierul text de intrare trebuie să conțină două numere întregi separate prin spațiu: n și m , reprezentând numărul de persoane și numărul de scaune, respectiv.
Pe următoarele n linii se află numele persoanelor, fiecare nume fiind scris pe o linie separată.
De exemplu, conținutul fișierului text de intrare ar putea arăta astfel:
5 3
Ana
Bianca
Cristina
David
Elena