Am stat 3 ore la problema asta si tot nu imi dau seama.

[•VasiliuIorgu]

Se poate rezolva subpunctul b prin apeluri utile ale subprogramului Ecuatie??


a) Scrieţi definiţia completă a subprogramului Ecuatie care primeşte prin parametrii a, b şi
c trei numere întregi, a ≠ 0, de cel mult patru cifre fiecare, reprezentând coeficienţii ecuaţiei
de gradul al II-lea: ax 2 +bx+c=0. În funcţie de soluţiile ecuaţiei subprogramul va returna:
• cea mai mare dintre soluţii dacă ecuaţia are două soluţii reale distincte, dintre care cel
puţin una pozitivă.
• una dintre soluţii dacă ecuaţia are două soluţii egale şi pozitive.
• -32000 în celelalte cazuri. (10p.)
b) Se consideră şirul s: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 1, 2,... .
Pentru un număr natural k, 0<k≤10000, se cere să se determine valoarea elementului ce
se află pe poziţia k în şirul s.
Exemplu: pentru k=5 numărul cerut este 2.
Scrieţi un program C/C++ care citeşte de la tastatură valoarea numărului natural k şi, prin
apeluri utile ale funcţiei Ecuatie, determină valoarea elementului ce se află pe poziţia k în
şirul s, folosind un algoritm eficient din punctul de vedere al spaţiului de memorie alocat şi
al timpului de executare. Valoarea astfel determinată se va scrie în fişierul text sir.out.
(6p.)
c) Descrieţi succint, în limbaj natural, metoda de rezolvare folosită la punctul b, explicând în
ce constă eficienţa ei (3 – 4 rânduri)

[•Dastas]

Consideram matricea:

1
1 2
1 2 3
1 2 3 4

Sa vedem cum se traduce gasirea valorii k din sir cu gasirea unui element (kx, ky) in matrice.

In primul rand, matricea de mai sus are 1 + 2 + 3 + 4 = 4*5/2 = 10 elemente.

Primele i linii au, in total i*(i + 1)/2 elemente.
Linia i are i elemente 1 2 ... i.

Al k-lea element este pe cea mai mica linie kx astfel incat kx*(kx + 1)/2 >= k

=> kx^2 + kx - 2k >= 0

kx^2 + kx - 2k = 0
delta = 1 - 4*(1 * (-2k)) = 1+8k > 0
kx = [-1 +/- sqrt(1 + 8k)] / 2

Varianta cu - evident nu convine, deoarece kx nu poate fi negativ

=> kx = [-1 + sqrt(1 + 8k)] / 2
=> kx = Ecuatie(1, 1, -2k)

De exemplu, pentru al cincilea element:

kx^2 + kx - 10 = 0
delta = 1 + 40 = 41

kx = [-1 + sqrt(41)] / 2 = 3 (rotunjit in sus)

Pana la linia 3 sunt 3 elemente, deci ky = 5 - 3 = 2

Al doilea element de pe linia 3 este 2.