online: 5; azi: 305; total: 50760 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
Să se genereze toate drapelele cu trei culori care se pot forma cu şase culori: alb, gal ben, roşu , verde, albastru şi negru, care au în mijloc culoarea alb, verde sau roşu . Indicație. Soluţia are 3 elemente, un element al soluţiei fiind indicele din vector al unei culori. Se generează aranjamente cu condiţie de 6 obiecte luate câte 3 — soluția conţine o condiție internă suplimentară față de cea impusă de aranjamente: elementul 2 al soluției trebuie să fie indicele culorii alb, verde sau roşu .
# include < iostream >
using namespace std ;
string culori[ 6 ] = { "alb" , "galben" , " rosu " , "verde" , "albastru" , "negru" };
int aranjament[ 3 ];
bool utilizat[ 6 ];
bool valid ( int k) {
if (k == 1 ) {
return aranjament[k] == 0 || aranjament[k] == 3 || aranjament[k] == 2 ;
}
return true ;
}
void tipar () {
for ( int i = 0 ; i < 3 ; i++) {
cout << culori[aranjament[i]] << ' ' ;
}
cout << endl ;
}
void bt ( int k) {
if (k == 3 ) {
tipar ();
return ;
}
for ( int i = 0 ; i < 6 ; i++) {
if (!utilizat[i]) {
aranjament[k] = i;
utilizat[i] = true ;
if ( valid (k)) {
bt (k + 1 );
}
utilizat[i] = false ;
}
}
}
int main () {
bt ( 0 );
return 0 ;
}

Acest program folosește o funcție de backtracking ( bt () ) pentru a construi toate drapelele cu trei culori care se pot forma cu șase culori: alb, galben, roșu, verde, albastru și negru, care au în mijloc culoarea alb, verde sau roșu. Funcția valid() verifică dacă elementul de pe poziția 1 al aranjamentului este una dintre culorile permise (alb, verde sau roșu). Dacă aranjamentul este valid, funcția tipar() afișează drapelele generate.