(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) 6
b) 7
c) 8
d) 9
e) 10
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
usando apenas multiplicações sucessivas, ou seja, construir um addition chain que comece em
e termine em
. O conteúdo é exponenciação rápida por cadeias de adição.
Passo 2
Um limite inferior genérico para o comprimento
de um addition chain para
é
onde
é o número de bits iguais a
na representação binária de
. Aqui
e
, logo
Isso significa que não podemos usar menos que
multiplicações.
Passo 3
Agora exibimos um addition chain que atinge exatamente
multiplicações:
Cada termo é obtido por uma soma de dois termos já calculados:
,
,
,
,
,
,
.
São multiplicações totais.
São
Passo 4
Como o limite inferior é
e há uma cadeia que usa exatamente
multiplicações, concluímos que
é o mínimo.
Resposta
b)