(FGV-RJ) Você tem uma calculadora que só faz multiplicações. Dado um número a, o número mínimo de multiplicações que você deve fazer para calcular a^37 é:
a) 6
b) 7
c) 8
d) 9
e) 10

Passo 1

O enunciado pede o número mínimo de multiplicações para obter a^37 usando apenas multiplicações sucessivas, ou seja, construir um addition chain que comece em 1 e termine em 37. O conteúdo é exponenciação rápida por cadeias de adição.

Passo 2

Um limite inferior genérico para o comprimento l(n) de um addition chain para n é
l(n)>= lfloorlog2 nrfloor+nu(n)-1,
onde nu(n) é o número de bits iguais a 1 na representação binária de n. Aqui lfloorlog2 37rfloor=5 e nu(37)=3, logo
l(37)>= 5+3-1=7
Isso significa que não podemos usar menos que 7 multiplicações.

Passo 3

Agora exibimos um addition chain que atinge exatamente 7 multiplicações:
1,2,4,5,9,18,36,37
Cada termo é obtido por uma soma de dois termos já calculados:
2=1+1,
4=2+2,
5=4+1,
9=5+4,
18=9+9,
36=18+18,
37=36+1.
São 7 multiplicações totais.

Passo 4

Como o limite inferior é 7 e há uma cadeia que usa exatamente 7 multiplicações, concluímos que 7 é o mínimo.

Resposta

b) 7

Exercícios de Livros Relacionados