Question

Recursivitate.

Ce calculeaza algoritmul ALGO1?

Am nevoie de ajutor la subpunctul c).

Answer 1

In primul rand, algo2 calculeaza suma tuturor elementelor $x[i] + x[i+1] + x[i+2] + \cdots + x[j-1] + x[j]$, cu $j \geq i$, prin metoda DIVIDE ET IMPERA.

Dupa se observa in algo1 ca parametrul j de la algo2 va fi intotdeauna mai mare sau egal cu i, deoarece for-ul are valoarea initiala i.

Mai departe, daca se atribuie o valoare elementului b[i][j], atunci matricea va fi completata doar deasupra diagonalei principale.

Deoarece pe diagonala principala avem i = j, elementul returnat de algo2 este x[i], deci toate elementele de pe diagonala principala vor avea valoarea elementului $x[i]$.

Dupa pentru restul elementelor, un element $b_{ij}$ va avea valoarea $x_i + x_{i+1} + x_{i+2} + \cdots + x_{j-1} + x_{j}$.

Astfel elementul $b_{ij}$ va avea valoarea sumei elementelor din vectorul x de la indicele randului pana la indicele coloanei.

(astfel daca acum avem, dintr-un anume motiv, de suma $x_i + x_{i+1} + x_{i+2} + \cdots + x_{j-1} + x_j$, o putem gasi la b[i][j])