Algoritm echivalent

[MoroJr]

Cod:

citeste a, b ( numere naturale )
s <- a
r <- 0
iteratii <- 0
cat timp b > 1 executa
  iteratii <- iteratii + 1
  daca b % 2 = 0 atunci
    s <- s * 2
    b <- b / 2
  altfel
    r <- r + s
    b <- b - 1
  sfarsit_daca
sfarsit_cat_timp

rezultat <- s + r

Urmatorul algoritm, calculeaza in variabila rezultat produsul numerelor a * b. Pentru setul de valori a = 4, b = 56, valorile variabilelor urmatoare vor fi:
rezultat = 224
iteratii = 7

Cum as putea sa fac un alt algoritm echivalent cu acesta, care sa imi calculeze ambele variabile corect?

Pentru variabila rezultat, fac in felul urmator:

Cod:

cat timp a <> 0 executa
  rezultat <- rezultat + b
  a <- a - 1
sfarsit_cat_timp
scrie rezultat

Dar la iteratii? Vreun indiciu ceva? Sau poate nu acesta ar fi algoritmul partial echivalent?

Va multumesc!

[•laurion]

Asigura-te ca intelegi mai intai ce face algoritmul. Primul are complexitate logaritmica, al tau are complexitate liniara.

Gandeste-te la un algoritm echivalent recursiv