| Calculando N^K em O(log(K)) |
Uma maneira simples de calcular N^K é tomar F(K) na seqüência F(n) = N *
F(n-1), sendo F(0) = 1.
Embora F resolva nosso problema, F não funcionará para K grande (K = 100000,
por exemplo), pois haverá estouro de pilha (Stack Overflow).
Se pensarmos mais um pouco esse problema pode ser resolvido usando essa nova
recursão:
E(0) = 1.
Se n é par => E(n) = E(n/2) * E(n/2) e
Se n é ímpar => E(n) = (E((n-1)/2) * E((n-1)/2)) * N
É possível provar que E = F, e para se computar E precisaremos de O(log(K))
operações, quanto
para computar F precisaremos de O(K) operações (assim como chamadas
recursivas).
Mas a nossa tarefa aqui é dado N real e K natural computar N^K.
(Obviamente usem recursão para resolver esse problema)
A entrada consiste de um N (double) e um K(K >= 0) para cada linha, até o
fim do arquivo.
A saída consiste em N^K (com 6 casas decimais) para cada linha de entrada.
1 10000 10 3 1.1 2 0.5 5 0.1 6
1.000000 1000.000000 1.210000 0.031250 0.000001