Exponenciação rápida
Problem
Elevar a uma potência é mais rápido que n multiplicações! Para fazer isso, use as seguintes relações de recorrência:
\(a^n=(a^2)^{n/2},\ para \ par \ n, \\ a^n=a \cdot a^{n-1 },\ para \ ímpar \ n.\)
Implemente o algoritmo de exponenciação rápida. Se você fizer tudo certo, a complexidade do seu algoritmo será O(logn) .
Entrada
O programa recebe um número real a e um inteiro n como entrada. Cada número em uma linha separada.
Impressão
Saída
\(a^n\).
Exemplos
| # |
Entrada |
Saída |
| 1 |
2
7 |
128 |
| 2 |
1.00001
100000 |
2.71827 |
Запрещенные операторы: for; while; until; math; **; pow