online: 17; azi: 1140; total: 51595 Manual clasa a xi a - Tehnici de programare - Metoda backtraking

Probleme Rezolvate



Sa se genereze toate aranjamentele
O bara are lungimea l
Sa se rezolve in mulimea numerelor naturale ecuatia 4x
Sa se genereze toate descompunerile unui numar natural n in numere prime
Pentru o multime oarecare a cu n elemente sa se genereze toate submulimile care au suma
Se citesc n cifre distincte si un numar natural x
Sa se afiseze toate secventele de n litere
Sa se genereze toate partiiile mulimii a formate din submultimi care au acelasi numar de elemente
Sa se genereze toate descompunerile unui numar natural n in numere naturale distincte
Se considera n multimi de cuvinte ai fiecare multime avand nj cuvinte
Sa se genereze toate posibilitaile de aranjare pe m scaune a n persoane
Dintr o multime de n persoane aranjate intr-un sir se elimina p persoane
Din n obiecte date
Pe un bilet exista 12 pozitii care pot fi perforate
Sa se genereze toate constructiile corecte de paranteze
Sa se afiseze toate numerele formate din cifre distincte cu proprietatea ca suma cifrelor este s
Sa se genereze toate partiiile multimii a formate din m submultimi
Sa se genereze toate partiiile mulimii a formate din doua submultimi care au suma elementelor egale
Se citesc de la tastatura n caractere distincte
Doua persoane isi impart n obiecte astfel
Sa se gaseasca modalitatea de plata a unei sume cu un numar minim de bancnote cu valori date
Sa se afiseze toate numerele cu n cifre
Se citesc de la tastatura n cifre distincte
Ntr-un restaurant un meniu este format din trei feluri de mancare
Se citeste un numar natural n
Sa se genereze toate grupurile de p persoane care se pot forma din n persoane
Profesorul de informatica a pregatit m teme
Problema bilei
Sa se genereze toate numerele binare de n cifre care au m cifre de 0
Se citeste un numar n care are m cifre
Se citesc de la tastatura un numar natural n
Doua persoane isi impart n obiecte astfel prima persoana ia m obiecte iar cealalta persoana
O bara are lungimea l1
Ntr un restaurant un meniu este format din trei feluri de mancare
Sa se genereze toate descompunerile unui numar natural n in suma de 3 si 5
Problema capcanelor
Sa se genereze toate anagramele unui cuvant
Doua persoane isi impart n obiecte
Se citesc de la tastatura n caractere distincte
Pentru realizarea unui chestionar exista n intrebari
Sa se genereze toate numerele naturale
Se considera n cuburi
Sa se genereze toate drapelele cu trei culori care se pot forma cu sase culori
Sa se genereze toate numerele naturale
Se citesc de la tastatura n cifre distincte

Manual clasa a Xi a

Tehnici de programare

Metoda backtraking
Profesorul de informatică a pregătit m teme, pentru proiecte pe care trebuie să le repartizeze celor n elevi din clasă (m<=n), astfel încât nici o temă de proiect să nu rămână nerepartizată. Să se genereze toate soluțiile de repartizare a temelor pentru proiect.
Pentru a genera toate soluțiile de repartizare a temelor pentru proiect putem folosi o soluție de tip backtracking . Ideea constă în a parcurge toate combinațiile posibile de alegere a temelor pentru fiecare elev.
Pseudocodul algoritmului ar putea fi următorul:
Exemplu de cod C++:
# include < iostream >
using namespace std ;
const int MAX_N = 100 ;
int n, m;
int temas [MAX_N];
bool used [MAX_N];
void generateSolutions ( int k) {
if (k == n) {
// am gasit o solutie
for ( int i = 0 ; i < n; i++) {
cout << "Elevul " << i+ 1 << " are tema " << temas [i] << endl ;
}
cout << endl ;
return ;
}
for ( int i = 1 ; i <= m; i++) {
if (! used [i]) {
temas [k] = i;
used [i] = true ;
generateSolutions (k+ 1 );
used [i] = false ;
}
}
}
int main () {
cin >> n >> m;
generateSolutions ( 0 );
return 0 ;
}

În acest exemplu, repartizarea temelor este reprezentată printr-un vector temas , iar pentru a verifica dacă o temă a fost deja repartizată altui elev folosim un vector used . Algoritmul începe cu primul elev și încă nu i se repartizează nicio temă, așa că parametrul k inițial este 0. Pentru fiecare elev, încercăm să îi repartizăm o temă care nu a fost deja repartizată altora, parcurgând temele posibile cu ajutorul variabilei i .