online: 9; azi: 1407; total: 51862 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
Se citesc de la tastatură n cifre distincte. Să se genereze toate numerele de m cifre (n< = m) care se pot forma cu aceste cifre şi care conţin toate cele n cifre.
# include < iostream >
using namespace std ;
void generateNumbers ( int digits [], int m, int usedDigits [], int usedCount , int currNumber ) {
if (m == 0 ) {
cout << currNumber << " " ;
return ;
}
for ( int i = 0 ; i < usedCount ; i++) {
int newNumber = currNumber * 10 + usedDigits [i];
generateNumbers ( digits , m - 1 , usedDigits , usedCount , newNumber );
}
return ;
}
int main () {
int n, m;
cout << " Introduceti numarul de cifre distincte: " ;
cin >> n;
int digits [n];
cout << " Introduceti cifrele distincte: " ;
for ( int i = 0 ; i < n; i++) {
cin >> digits [i];
}
cout << " Introduceti numarul de cifre pentru numerele de generat: " ;
cin >> m;
int usedDigits [n];
int usedCount = 0 ;
for ( int i = 0 ; i < n; i++) {
usedDigits [ usedCount ++] = digits [i];
generateNumbers ( digits , m - 1 , usedDigits , usedCount , digits [i]);
usedCount --;
}
cout << endl ;
return 0 ;
}

Explicație:
Pentru a genera toate numerele de m cifre care conțin toate cele n cifre distincte date, putem folosi o soluție recursivă. În cadrul acestei soluții, la fiecare pas adăugăm o cifră la numărul generat până acum, prin combinarea cifrelor disponibile. Pentru a evita dublarea cifrelor, am utilizat un vector " usedDigits " care conține cifrele folosite până în acel moment, și un contor " usedCount " care indică numărul de cifre utilizate. La începutul programului, folosim fiecare cifră aflată în vectorul " digits " ca primă cifră pentru numerele de generat și apoi apelăm funcția recursivă " generateNumbers " pentru a genera restul cifrelor. Pentru a garanta că numărul de cifre generate este egal cu m, decrementăm valoarea lui m la fiecare apel recursiv. Când m ajunge la zero, numărul generat este afișat.