Probleme

Folosim metoda backtracking pentru a genera numere naturale în ordine crescătoare utilizând cifrele 0, 1, 2, 3, 4, 5 și 6. Primele 10 numere generate sunt 0, 1, 2, 3, 4, 5, 6, 10, 11, 12. Care este al 256-lea număr generat?

a) 513; b) 501; c) 555; d) 466; e) 444; f) 503.

Pentru mulțimea $\{1, 2, 3, \ldots, n\}$ se generează printr-un program toate permutările în care nu există numere vecine alăturate. Două numere $a$ și $b$ sunt vecine dacă $|a-b|=1$ (de exemplu 3 și 4 sunt vecine, 2 și 1 sunt vecine). Știind că pentru $n=5$ au fost generate 14 permutări distincte în care nu există numere vecine, câte permutări se vor genera pentru $n=6$?

a) 72; b) 56; c) 144; d) 90; e) 89; f) 120.

Se dau n obiecte (n e întreg pozitiv sau 0) ale căror mase și valori sunt stocate în tablourile unidimensionale de întregi m și, respectiv, v (primul element al tablourilor se găsește pe poziția 0). Într-un rucsac se pot transporta obiecte întregi cu masa însumată maxim C (întreg pozitiv sau 0). Trebuie identificată valoarea maximă ce poate să fie obținută prin adăugarea de obiecte în rucsac, astfel încât masa lor să nu depășească C. Procedura descrisă în pseudocod mai jos conține implementarea algoritmului backtracking care returnează soluția. Este considerată dată funcția max care primește 2 parametri întregi și returnează valoarea maximă dintre aceștia. Funcția se apelează cu parametrii: valoare pentru întreg C, tablourile m și v, valoare pentru n și un număr de obiecte. Completați cu secvența lipsă:

întreg bk(întreg C, întreg m[], întreg v[], întreg n)
    dacă (n = 0 sau C = 0)  returnează 0;
    dacă (m[n-1] > C)
        returnează bk(C, m, v, n-1);
    altfel
        returnează ______

a) max(v[n-1]+bk(C-m[n-1], m, v, n), bk(C, m, v, n)); b) max(v[n]+bk(C-m[n], m, v, n-1), bk(C, m, v, n-1)); c) max(v[n-1]+bk(C-m[n-1], m, v, n-1), bk(C, m, v, n-1)); d) max(bk(C-m[n-1], m, v, n-1), bk(C, m, v, n-1)); e) max(v[n]+bk(C-m[n], m, v, n), bk(C, m, v, n)); f) max(bk(C, m, v, n-1), bk(C, m, v, n-2)).

Următoarea secvență de cod generează, folosind cifre de la 0 la 5, numere de 5 cifre. Primul șir afișat este 00000. La un moment dat se afișează 11521. La al câtelea apel al funcției genereaza se întâmplă acest lucru?

void genereaza(char* nr, int p) {
  if (p == 5) {
    nr[p] = '\0';
    printf("%s\n", nr); // cout<<nr<<endl;
    return;
  }
  for (int cifra = 0; cifra <= 5; cifra++) {
    nr[p] = '0' + cifra;
    genereaza(nr, p + 1);
  }
}
int main() {
  char nr[6];
  genereaza(nr, 0);
  return 0;
}

a) 2024; b) 1701; c) 1704; d) 2050; e) 1706; f) 2048.

Se dau $m_1$ greutăți de $k_1$ kg fiecare și $m_2$ greutăți de $k_2$ kg fiecare. Cel mai bun candidat la un concurs a scris un program corect care stabilește modurile în care poate fi echilibrată o balanță având pe talerul din stânga o greutate $X$ dată și afișează numărul de soluții posibile. Greutățile pot fi puse pe ambele talere. Programul citește la rulare numerele naturale $m_1$ $k_1$ $m_2$ $k_2$ $X$ în această ordine. Ce afișează programul pentru trei rulări succesive: rulare 1: 5 2 5 1 4, rulare 2: 5 2 5 1 11, rulare 3: 5 2 5 1 20?

a) 10 5 0; b) 20 7 0; c) 20 7 1; d) 10 10 0; e) 10 7 0; f) 20 5 0.

Fie o mulțime de $k$ simboluri cu care se pot forma șiruri distincte de lungime $n$ ($n\ge k$). Fiecare dintre cele $k$ simboluri apare în fiecare șir de $f_1, f_2, \ldots, f_k$ ori, $f_i\ge 1$, $1\le i\le k$. Pentru simbolurile $\{A, B, C\}$ care apar de $1$, $3$ și, respectiv, $2$ ori, primele $4$ șiruri generate cu metoda backtracking sunt: ABBBCC, ABBCBC, ABBCCB, ABCBBC. Care este următorul șir care va fi generat?

a) ACCBBB; b) ABCBCB; c) ABCCBB; d) ABCBBC; e) ACBBBC; f) BABCCB.

Utilizând metoda backtracking, se generează, în ordine strict descrescătoare, toate numerele naturale de câte patru cifre distincte din mulțimea $\{0,1,2,3,4,5\}$. Primele șase numere generate sunt, în această ordine: $5432$, $5431$, $5430$, $5423$, $5421$, $5420$. Al șaptelea număr generat este:

a) $5415$; b) $5321$; c) $5340$; d) $5421$; e) $5413$; f) $5342$.

Pentru a genera submulțimile unei mulțimi $M=\{x_1,x_2,\ldots,x_n\}$ cu $n=10$ elemente se folosește metoda backtracking. Câte submulțimi cu cardinal impar se generează, submulțimi care conțin numai unul dintre elementele $x_1$ și $x_3$ și nu conțin elementul $x_2$?

a) $510$; b) $128$; c) $511$; d) $255$; e) $256$; f) $127$.