Esponenziamento veloce
Problem
Elevare a potenza è più veloce delle n moltiplicazioni! Per fare ciò, utilizzare le seguenti relazioni di ricorrenza:
\(a^n=(a^2)^{n/2},\ per \ pari \ n, \\ a^n=a \cdot a^{n-1 },\ per \ dispari \ n.\)
Implementa l'algoritmo di esponenziazione rapida. Se fai tutto bene, la complessità del tuo algoritmo sarà O(logn) .
Input
Il programma riceve un numero reale a e un intero n come input. Ogni numero su una riga separata.
Impronta
Output
\(a^n\).
Esempi
| # |
Input |
Uscita |
| 1 |
2
7 |
128 |
| 2 |
1.00001
100000 |
2.71827 |
Запрещенные операторы: for; while; until; math; **; pow