Exponentiation Rapide
Calcul de aⁿ en O(log n)
Enonce
Implémenter l'exponentiation rapide en version itérative et récursive. Tester avec $2^{10}=1024$ et $3^{20}$.
Signature attendue
def expo_rapide(a: float, n: int) -> float:Exemples
expo_rapide(2, 10)→1024expo_rapide(3, 20)→3486784401expo_rapide_rec(2, 10)→1024
📖 Rappel de cours
L'exponentiation rapide exploite la décomposition binaire de $n$ pour calculer $a^n$ en $O(\log n)$ multiplications au lieu de $O(n)$.
Principe :
$a^n = \begin{cases} 1 & \text{si } n=0 \\ (a^{n/2})^2 & \text{si } n \text{ pair} \\ a \cdot a^{n-1} & \text{si } n \text{ impair} \end{cases}$
Nombre de multiplications : $\lfloor\log_2 n\rfloor + \nu(n) - 1$ où $\nu(n)$ est le nombre de bits à 1.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Tri par Sélection
- Tri Fusion (Merge Sort)
- Tri Rapide (Quicksort)
- Recherche dans une Liste Chaînée
- Pile et File
- Évaluation d'Expressions Postfixées
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.