Rezolvare A.6

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

Enunț

Fie subalgoritmul factoriPrimi(n, d, k, x) care determină cei k factori primi ai unui număr natural n, începând căutarea factorilor primi de la valoarea d. Parametrii de intrare sunt numerele naturale n, d și k, iar parametrii de ieșire sunt șirul x cu cei k factori primi (1 ≤ n ≤ 10000, 2 ≤ d ≤ 10000, 0 ≤ k ≤ 10000).

Subalgoritm factoriPrimi(n, d, k, x):
  Dacă n MOD d = 0 atunci
    k ← k + 1
    x[k] ← d
  SfDacă
  CâtTimp n MOD d = 0 execută
    n ← n DIV d
  SfCâtTimp
  Dacă n > 1 atunci
    factoriPrimi(n, d + 1, k, x)
  SfDacă
SfSubalgoritm

Stabiliți de câte ori se autoapelează subalgoritmul factoriPrimi(n, d, k, x) prin execuția următoarei secvențe de instrucțiuni:

n ← 120
d ← 2
k ← 0
factoriPrimi(n, d, k, x)

A. de 3 ori
B. de 5 ori
C. de 9 ori
D. de același număr de ori ca și în cadrul secvenței de instrucțiuni:

n ← 750
d ← 2
k ← 0
factoriPrimi(n, d, k, x)

Soluție

Răspuns corect: A, D.

Justificare

Fie:

n ← 120
d ← 2
k ← 0
factoriPrimi(n, d, k, x)

Atunci:

factoriPrimi(120, 2, 0, x) → factoriPrimi(15, 3, 1, x) → factoriPrimi(5, 4, 1, x) → factoriPrimi(5, 5, 2, x)

S-au făcut trei autoapeluri, deci răspunsul A este corect.

De asemenea, răspunsul D este corect, deoarece:

factoriPrimi(750, 2, 0, x) → factoriPrimi(375, 3, 1, x) → factoriPrimi(125, 4, 1, x) → factoriPrimi(125, 5, 2, x)

Și în acest caz sunt trei autoapeluri!