RSS Feed
Următoarea

Problema 122

02 Iunie 2006

Exponențializare eficientă


Cea mai naivă metodă de a calcula n15 necesită 14 înmulțiri:

n × n × ... × n = n15

Dar folosind o metodă "binary" poți obține rezultatul după doar 6 înmulțiri:

n × n = n2
n2 × n2 = n4
n4 × n4 = n8
n8 × n4 = n12
n12 × n2 = n14
n14 × n = n15

Totuși, e posibil să obții rezultatul după doar 5 înmulțiri:

n × n = n2
n2 × n = n3
n3 × n3 = n6
n6 × n6 = n12
n12 × n3 = n15

Fie m(k) numărul minim de înmulțiri necesare pentru a calcula nk; de exemplu m(15) = 5.

Pentru 1 ≤ k ≤ 200, găsește m(k).


Tag-uri:

>> Vezi problema originală <<