Rezolvare A.4

Nu parcurgeți acest articol înainte de rezolvarea problemei!

Enunț

Fie subalgoritmul calcul(a, b) cu parametrii de intrare a și b numere naturale, 1 ≤ a ≤ 1000, 1 ≤ b ≤ 1000.

1. Subalgoritm calcul(a, b):
2.     Dacă a ≠ 0 atunci
3.         returnează calcul(a DIV 2, b + b) + b * (a MOD 2)
4.     SfDacă
5.     returnează 0
6. SfSubalgoritm

Care din afirmațiile de mai jos sunt false?

A. dacă a și b sunt egale, subalgoritmul returnează valoarea lui a
B. dacă a = 1000 și b = 2, subalgoritmul se autoapelează de 10 ori
C. valoarea calculată și returnată de subalgoritm este a / 2 + 2 * b
D. instrucțiunea de pe linia 5 nu se execută niciodată

Soluție

Răspuns corect: A, C, D.

Justificare

Pentru a verifica afirmația A, considerăm un apel potrivit, de exemplu calcul(3,3):

• calcul(3,3) = calcul(1,6) + 3 * 1
• calcul(1,6) = calcul(0,12) + 6 * 1
• calcul(0,12)=0

Rezultă:

• calcul(1,6) = 0 + 6 * 1 = 6
• calcul(3,3) = 6 + 3 * 1 = 9

Deci * calcul(3,3) = 9, nicidecum 3. Rezultă că afirmația A este falsă.

Totodată, deoarece pentru a=3 și b=3 avem a / 2 + 2 * b = 3/2+2*3 = 7.5 (sau 7, dacă considerăm că / reprezintă câtul împărțirii), deducem că afirmația C este falsă.

Analizăm afirmația B:

1. calcul(1000,2) = calcul(500,4) + 2 * 0
2. calcul(500,4) = calcul(250,8) + 4 * 0
3. calcul(250,8) = calcul(125,16) + 8 * 0
4. calcul(125,16) = calcul(62,32) + 16 * 1
5. calcul(62,32) = calcul(31,64) + 32 * 0
6. calcul(31,64) = calcul(15,128) + 64 * 1
7. calcul(15,128) = calcul(7,256) + 128 * 1
8. calcul(7,256) = calcul(3,512) + 256 * 1
9. calcul(3,512) = calcul(1,1024) + 512 * 1
10. calcul(1,1024) = calcul(0,2048) + 1024 * 1
11. calcul(0,2048)=0

Numărul de autoapeluri (fără apelul principal) este 10, deci afirmația B este adevărată.

Afirmația D este falsă; instrucțiunea return 0; se execută când condiția a ≠ 0 este falsă, cazul în care se opresc apelurile recursive.