Admitere Informatică 2024 — Simulare 17 martie — Varianta A

În câte moduri se poate colora următorul graf neorientat folosind 4 culori astfel încât 2 noduri adiacente să nu aibă aceeași culoare? [Figura: graf cu 8 noduri — patru noduri în colțurile unui pătrat exterior și patru noduri în colțurile unui pătrat interior. Muchii: cele 4 laturi ale pătratului exterior, cele 4 laturi ale pătratului interior, cele 4 muchii care leagă fiecare colț exterior de colțul interior corespunzător și cele 2 diagonale ale pătratului interior (X-ul din centru). În total 14 muchii.]

a) 288; b) 696; c) 625; d) 24!; e) 120; f) 24.

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)).

Care este rezultatul întors de funcția scrisă mai jos în pseudocod, dacă este apelată cu valoarea 3 pentru parametrul a întreg și 10 pentru parametrul n întreg? S-a notat cu a%b restul împărțirii numărului natural a la numărul natural nenul b și cu [a] partea întreagă a numărului real a.

întreg f(întreg a, întreg n) {
    dacă (n == 0) returnează 1;
    altfel dacă (n%2 == 0) returnează f(a, n/2)*f(a, n/2);
    altfel returnează a*f(a, [n/2])*f(a, [n/2]);
}

a) 39366; b) 243; c) 486; d) 177147; e) 59049; f) 19683.

Se consideră o hartă sub forma unei matrice 4x4. Dacă cineva pleacă de pe poziția (1,1) și vrea să ajungă în celula (4,4), se poate muta doar pe linii sau coloane cu numere mai mari și poate sări oricât de multe în ambele direcții, deci poate ajunge inclusiv direct din (1,1) în (4,4). În câte moduri distincte poate face acest lucru?

a) 76; b) 128; c) 256; d) 63; e) 252; f) 64.