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!