Probleme

Care este valoarea maximă a sumei $a+b$ care se calculează în ultima instrucțiune din funcția h la cel mai adânc nivel al recursivității, pentru apelul h(0, 2026)?

(varianta C/C++)

void h(int a, int b) {
    int m;
    if(a > b) return;
    m = (a + b)/2;
    printf("%d", m % 10); // cout<<m % 10;
    h(a, m - 1);
    h(m + 1, b);
    printf("%d", (a + b) % 10); // cout<<(a + b) % 10;
}

a) $2025$; b) $6$; c) $1013$; d) $2026$; e) $506$; f) $4052$.

Fie următoarea funcție definită în pseudocod, unde x % y reprezintă restul împărțirii lui x la y. Care este rezultatul apelului f(1234567, 0)?

intreg f(intreg n, intreg k) {
    daca (n == 0) returneaza 1;
    rez <- f(n / 10, k);
    daca ((k % 10 - n % 10) != 1)
        rez <- rez + f(n / 10, k * 10 + n % 10);
    returneaza rez;
}

a) $7$; b) $128$; c) $14$; d) $64$; e) $10$; f) $34$.

Fie șirul lui Fibonacci $(F_n)_{n\ge 0}$: $F_0=0$, $F_1=1$, iar pentru $n\ge 2$: $F_n=F_{n-1}+F_{n-2}$. Fie funcția recursivă $f:\mathbb{N}\to\mathbb{Z}$ definită prin $f(0)=0$, $f(1)=1$, iar pentru $n\ge 2$: $f(n)=f(n-1)+(-1)^n\cdot F_{(n \bmod 5)+1}$ (unde mod este restul împărțirii întregi). Ce valoare are $f(2026)$?

a) $5$; b) $4$; c) $0$; d) $8$; e) $-5$; f) $1$.

Fie următoarea funcție recursivă definită prin pseudocod. Câte apeluri ale funcției se realizează pentru a calcula func(20, 2025)?

intreg func(intreg x, intreg n) {
    daca x < 2 atunci
        intoarce n;
    intoarce func(x-2, n+2) + 2*func(x-4, n-1);
}

a) 2024; b) 1706; c) 144; d) 89; e) 2025; f) 287.

Considerăm șirul lui Fibonacci unde $fib(0)=0$, $fib(1)=1$ și $fib(k)=fib(k-1)+fib(k-2)$, pentru orice $k>1$, natural. Se construiește un arbore definit în funcție de numărul de nivele, rădăcina se află pe nivelul 1, și fiecare nod de pe nivelul $h$ are $fib(h+2)$ copii. Calculăm $N$ ca fiind numărul de noduri pentru un astfel de arbore cu 10 nivele. Pentru că numărul $N$ este destul de mare, se cere $N \bmod 13$ (restul împărțirii lui $N$ la 13).

a) 7; b) 3; c) 8; d) 4; e) 11; f) 6.

Care este rezultatul apelului power(2,2025) pentru funcția recursivă definită mai jos?

(varianta C/C++)

int power(int x, int n) {
    if(n==0)
        return 1;
    if(n%2==0)
        return x * power(x, n/2);
    else
        return power(x, (n-1)/2);
}

a) 8; b) 1024; c) 128; d) 4096; e) 16; f) 2048.

Fie funcția dată prin următorul pseudocod (% reprezintă restul împărțirii întregi). Care dintre următoarele apeluri au ca rezultat numai valori pare?

intreg f(intreg n, intreg y) {
  dacă (n > 0)
    dacă (n % 2 == 0) returnează f(n - 1, y + 1) + y;
    altfel returnează f(n - 1, y + 1);
  altfel returnează 0;
}

a) f(117, 200), f(222, 300), f(322, 485), f(422, 653); b) f(116, 100), f(220, 181), f(321, 281), f(420, 551); c) f(117, 130), f(222, 461), f(323, 771), f(422, 891); d) f(117, 240), f(222, 480), f(322, 795), f(422, 833); e) f(116, 150), f(222, 81), f(321, 331), f(420, 671); f) f(118, 241), f(222, 291), f(322, 481), f(422, 451).

În urma apelului f(5) se afișează un șir de cifre. Care sunt cifrele de pe pozițiile 14-17, prima poziție fiind numerotată cu 1?

void f(int n)
{
  int i;
  for (i=n; i>=1; i-=2) {
    f(n-1);
    printf("%d", n); // cout << n;
  }
}

a) 2341; b) 4123; c) 4512; d) 1234; e) 1231; f) 2345.

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.

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

Se consideră funcția recursivă următoare, unde literele $x$ și $y$ sunt două numere naturale:

(varianta C/C++)

int f(int a, int b)
{
    if (a == b)
        return 0;
    if (b % a == 0)
        return a + b;
    return f(a + x, b - y);
}

Pentru care perechi de numere naturale $x$ și $y$ de mai jos, din intervalul $[1,25]$, rezultatul apelului $f(1000,2004)$ este $0$, iar numărul de apeluri recursive este maxim $300$?

a) $(x=16,y=20)$; $(x=17,y=21)$; $(x=18,y=22)$; b) $(x=1,y=1)$; $(x=2,y=2)$; $(x=3,y=1)$; c) $(x=1,y=3)$; $(x=20,y=24)$; $(x=21,y=25)$; d) $(x=13,y=17)$; $(x=14,y=18)$; $(x=15,y=19)$; e) $(x=1,y=3)$; $(x=2,y=2)$; $(x=3,y=1)$; f) $(x=6,y=10)$; $(x=7,y=11)$; $(x=9,y=13)$.

Se consideră funcția recursivă (varianta C/C++):

int S(int n, int a, int b)
{
  if(n==0) return 0;
  else return a*n + b + S(n-1,a,b);
}

Dacă apelul $S(10,a,b)$ are ca rezultat $2045$, iar apelul $S(5,a,b)$ are ca rezultat $560$, atunci:

a) $a=1,\ b=2$; b) $a=10,\ b=5$; c) $a=1,\ b=37$; d) $a=37,\ b=1$; e) $a=37,\ b=38$; f) $a=5,\ b=10$.

Fie funcția recursivă definită prin următorul pseudocod. Care este rezultatul apelului $f(1, 3, 2022)$?

int f(int a, int b, int k)
{
    dacă (k==1) returnează a+b
    dacă (a+2>b) returnează f(a+2, b, k-1)
    returnează f(1, b+2, k-1)
}

a) $4$; b) $169$; c) $170$; d) $139$; e) $4044$; f) $140$.