Admitere Informatică 2023 — 17 iulie — Varianta S

Fie $f(n)$ și $g(n)$ două funcții oarecare, unde $n$ este număr natural. Considerăm $x$ și $y$ două numere naturale nenule și definim următoarele recurențe:

$$a_0 = 0,\ a_1 = 1,\ a_{n+2} = a_{n+1} + a_n + f(n)$$
$$b_0 = 0,\ b_1 = 1,\ b_{n+2} = b_{n+1} + b_n + g(n)$$
$$c_0 = 0,\ c_1 = 1,\ c_{n+2} = c_{n+1} + c_n + x\cdot f(n) + y\cdot g(n)$$

Cum se poate exprima $c_n$ în funcție de $x$, $y$, $a_n$, $b_n$ și $F_n$, unde $F_n$ este elementul $n$ al șirului lui Fibonacci, care este definit astfel: $F_0=0$, $F_1=1$, $F_{n+2}=F_{n+1}+F_n$?

a) $c_n = x\cdot a_n + y\cdot b_n + (1-x-y)\cdot F_n$; b) $c_n = x\cdot a_n + y\cdot b_n + (1+x+y)\cdot F_n$; c) $c_n = x\cdot a_n + y\cdot b_n + (x+y)\cdot F_n$; d) $c_n = x\cdot a_n + y\cdot b_n + F_n$; e) $c_n = a_n + b_n + (1-x-y)\cdot F_n$; f) $c_n = a_n + b_n + (x+y)\cdot F_n$.

Fie o matrice $M$ cu elemente numere întregi. Valorile $M(i,j)$, $i\ge 0$, $j\ge 0$ se calculează folosind relația recursivă:

$$M(i,j) = \begin{cases} C, & \text{pentru } i=0 \text{ și } j=0 \\ M(i-1,0)+1, & \text{pentru } i>0 \text{ și } j=0 \\ M(0,j-1)+1, & \text{pentru } i=0 \text{ și } j>0 \\ \min(M(i-1,j), M(i,j-1))+1, & \text{pentru } i>0 \text{ și } j>0 \end{cases}$$

unde $C$ este un număr întreg. Dacă $M(2022,2023) = 5045$, care este valoarea lui $C$?

a) $1000$; b) $1024$; c) $2022$; d) $2023$; e) $3022$; f) $3023$.

Fie $a$ și $b$ două variabile de tip întreg inițializate cu valorile $0$, respectiv $111$. Indicați valorile variabilelor $a$ și $b$ în urma apelului $f(a,b)$. Subprogramul $f$ este definit mai jos:

(varianta C/C++)

int f(int& a, int b)
{
    int r = 0;
    if (b > 0)
        r = b + f(a, b - 2);
    a += r;
    return 0;
}

a) $3136, 111$; b) $0, 111$; c) $3136, 0$; d) $6105, 111$; e) $2969, 111$; f) $3080, 111$.

Fie un graf neorientat cu $n$ noduri, numerotate de la $1$ la $n$. Există muchie între $i$ și $j$ dacă și numai dacă $j$ divide pe $i$ ($1\le i\le n$, $1<j<i$). Câte componente conexe are graful pentru $n=50$?

a) $8$; b) $6$; c) $5$; d) $7$; e) $2$; f) $1$.