Module: sub-rotinas. recursão


Problem

7 /8


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

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!