online: 14; azi: 634; total: 51089 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
Pentru realizarea unui chestionar există n întrebări, fiecare întrebare având un punctaj. Numărul de întrebări şi punctajul fiecărei întrebări se citesc dintr-un fişier text. Să se genereze toate chestionarele care au între a şi b întrebări distincte şi un punctaj total între p şi q puncte. Valorile pentru a, b, p şi q se citesc de la tastatură.
Pentru a realiza acest program, vom utiliza o abordare de backtracking și vom citi datele dintr-un fișier text. În primul rând, să creeăm un fișier de intrare de exemplu:
Fișier de intrare (intrebari.txt):
5
2
3
5
7
10
Acest fișier indică următoarele informații:
# include < iostream >
# include < fstream >
using namespace std ;
int n, a, b, p, q;
int intrebari [ 100 ];
int sol[ 100 ];
void citire () {
ifstream fin ( "intrebari.txt" ) ;
fin >> n;
for ( int i = 0 ; i < n; ++i) {
fin >> intrebari [i];
}
fin. close ();
}
bool valid ( int k, int sum , int count ) {
return sum >= p && sum <= q && count >= a && count <= b;
}
void afisare ( int k) {
for ( int i = 0 ; i < k; ++i) {
cout << sol[i] << ' ' ;
}
cout << endl ;
}
void back ( int k, int start, int sum , int count ) {
if ( valid (k, sum , count )) {
afisare (k);
}
for ( int i = start; i < n; ++i) {
sol[k] = intrebari [i];
back (k + 1 , i + 1 , sum + intrebari [i], count + 1 );
}
}
int main () {
citire ();
cout << " Introduceti a, b, p si q: " ;
cin >> a >> b >> p >> q;
back ( 0 , 0 , 0 , 0 );
return 0 ;
}

Acest program va citi datele din fișierul text, va citi valorile pentru a, b, p și q de la tastatură și va afișa toate chestionarele posibile care respectă condițiile impuse.