Test 1 backtracking

În utilizarea metodei backtracking pentru a genera toate cuvintele alcatuite din doua litere ale mulțimii {a, c, e, q}, astfel incat sa nu existe doua consoane alaturate, cuvintele se genereaza in urmatoarea ordine: aa, ac, ae, aq, ca, ce, ea, ec, ee, eq, qa, qe. Daca se utilizeaza exact aceeasi metoda pentru a genera cuvinte formate din 4 litere ale multimii {a, b, c, d, e, f}, astfel incat sa nu existe doua consoane alaturate in cuvant, care este penultimul cuvant generat?

• fefa
• fafe
• feef
• fefe

Folosind numai cifrele {0,5,3,8}, se construiesc, prin metoda backtracking,toate numerele cu 3 cifre în care oricare două cifre alăturate nu au aceeaşi paritate. Se obţin, în ordine numerele: 505, 503, 585, 583, 305, 303,385, 383, 850, 858, 830, 838. Utilizând acelaşi algoritm pentru a obţine numere cu patru cifre din mulţimea {0,3,6,2,9}, în care oricare două cifre alăturate nu au aceeaşi paritate, al şaselea număr care se obţine este:

• 3092
• 3690
• 6309
• 3096

Folosind modelul combinărilor se generează cuvinte cu câte două litere distincte din mulţimea {i,t,e,m} obţinându-se, în ordine: it, ie, im,te, tm, em. Dacă se utilizează exact aceeaşi tehnică pentru a genera cuvinte cu patru litere distincte din mulţimea {i,t,e,m,a,x}, atunci numărul de cuvinte generate care se termină cu litera a este:

• 4
• 12
• 24
• 5

Utilizand metoda backtracking se genereaza toate numerele formate doar din trei cifre astfel incat fiecare numar sa aiba cifrele distincte. Cifrele fiecarui numar sunt din multimea {1, 2, 3, 4}. acest algoritm genereaza numerele, in aceasta ordine: 123, 124, 132, 134, 213, 214, 231, 234, 312, 314, 321, 324, 412, 413, 421, 423, 431, 432. Daca utilizam acelasi algoritm pentru a genera toate numerele de 4cifre, fiecare numar fiind format din cifre distincte din multimea {1, 2, 3, 4, 5}, precizati care este numarul generat imedia dupa 4325.

• 4351
• 5123
• 4521
• 4321

Daca se utilizeaza metoda backtracking pentru a genera toate numerele naturale, in ordine strict crescatoare, formate din 4 cifre pare distincte, care dintre numerele de mai jos trebuie, eliminate astfel incat cele ramase sa reprezinte o succesiune de numere corect generate? 1) 2068; 2) 2084; 3) 2088; 4) 2468; 5) 2086; 6) 2406

• numai 3)
• atat 3) cat si 5)
• Atat 3) cat si 4)
• numai 4)

Având la dispoziţie cinci tipuri de prăjituri, cu pere, cu mure, cu afine, cu fragi, cu zmeură, se utilizează metoda backtracking pentru a obţine toate posibilităţile de a forma platouri cu câte trei tipuri de prăjituri diferite, ştiind că în cadrul unui platou nu contează ordinea de aşezare a prăjiturilor şi că prăjiturile cu mure nu vor fi plasate pe acelaşi platou cu prăjiturile cu fragi. Primele patru soluţii obţinute sunt, în această ordine: (pere, mure, afine), (pere, mure, zmeură), (pere, afine, fragi), (pere, afine, zmeură). Scrieţi cea de a cincea şi cea de a şasea soluţie, în ordinea obţinerii lor.

În ce condiții se revine de la componenta k la componenta k-1?

• dupa ce am gasit o valoare convenabila pentru componenta k
• daca valoarea testata pentru componenta k nu convine
• daca am testat toate valorile posibile pentru componenta k

Se generează, utilizând metoda backtracking, toate modalităţile de aşezare a numerelor naturale de la 1 la 5, astfel încât oricare două numere de aceeaşi paritate să nu se afle pe poziţii alăturate. Dacă primele 3 soluţii generate sunt, în ordine: 12345, 12543 şi 14352 care este a doua soluţie generată ce începe cu 5?

Folosind metoda bactracking un elev a scris un program care generează toate numerele decâte n cifre (0

Pentru generarea numerelor cu n cifre formate cu elementele mulţimii {0,4,8} se utilizează un algoritm backtracking care, pentru n=2, generează, în ordine, numerele 40,44,48,80,84,88. Dacă n=4 şi se utilizează acelaşi algoritm, care este numărul generat imediat după numărul 4008 ?

• 4040
• 4004
• 4080
• 8004