Rezolvare A.5

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

Enunț

Se consideră șirul (1, 2, 3, 2, 5, 2, 3, 7, 2, 4, 3, 2, 5, 11, ...) format astfel: plecând de la șirul numerelor naturale, se înlocuiesc numerele care nu sunt prime cu divizorii lor proprii, fiecare divizor d fiind considerat o singură dată pentru fiecare număr. Care dintre subalgoritmi determină al n-lea element al acestui șir (n – număr natural, 1 ≤ n ≤ 1000)?

A.

Subalgoritm identificare(n):
  a ← 1, b ← 1, c ← 1
  CâtTimp c < n execută
    a ← a + 1, b ← a, c ← c + 1, d ← 2
    f ← false
    CâtTimp c ≤ n și d ≤ a DIV 2 execută
      Dacă a MOD d = 0 atunci
        c ← c + 1, b ← d, f ← true
      SfDacă
      d ← d + 1
    SfCâtTimp
    Dacă f atunci
      c ← c - 1
    SfDacă
  SfCâtTimp
  returnează b
SfSubalgoritm

B.

Subalgoritm identificare(n):
  a ← 1, b ← 1, c ← 1
  CâtTimp c < n execută
    c ← c + 1, d ← 2
    CâtTimp c ≤ n și d ≤ a DIV 2 execută
      Dacă a MOD d = 0 atunci
        c ← c + 1, b ← d
      SfDacă
      d ← d + 1
    SfCâtTimp
    a ← a + 1, b ← a
  SfCâtTimp
  returnează b
SfSubalgoritm

C.

Subalgoritm identificare(n):
  a ← 1, b ← 1, c ← 1
  CâtTimp c < n execută
    a ← a + 1, d ← 2
    CâtTimp c < n și d ≤ a execută
      Dacă a MOD d = 0 atunci
        c ← c + 1, b ← d
      SfDacă
      d ← d + 1
    SfCâtTimp
  SfCâtTimp
  returnează b
SfSubalgoritm

D.

Subalgoritm identificare(n):
  a ← 1, b ← 1, c ← 1
  CâtTimp c < n execută
    b ← a, a ← a + 1, c ← c + 1, d ← 2
    CâtTimp c ≤ n și d ≤ a DIV 2 execută
      Dacă a MOD d = 0 atunci
        c ← c + 1, b ← d
      SfDacă
      d ← d + 1
    SfCâtTimp
  SfCâtTimp
  returnează b
SfSubalgoritm 

Soluție

Răspuns corect: A.