La fonction puissance, v1⚓︎
Pour un réel \(a\) et un entier naturel \(n\), on note \(a^n = a × a × ... × a\), avec \(n\) fois le facteur \(a\).
Ainsi
- \(3^4 = 3 × 3 × 3 × 3 = 81\)
- \(3^5 = 3 × 3 × 3 × 3 × 3 = 243\)
On a aussi
- \(3^1 = 3\), il y a un seul facteur égal à \(3\)
- \(3^0 = 1\), comme un produit vide
def puissancepy-undv1(a: float, n: int) -> float:bksl-nl "Renvoie a à la puissance n, pour n >= 0"bksl-nl ...bksl-nlbksl-nlbksl-nlassert puissancepy-undv1(3.0, 0) == 1.0bksl-nlassert puissancepy-undv1(3.0, 1) == 3.0bksl-nlassert puissancepy-undv1(3.0, 4) == 81.0bksl-nlassert puissancepy-undv1(3.0, 5) == 243.0bksl-nlassert puissancepy-undv1(2.0, 10) == 1024.0bksl-nlbksl-nlbksl-nl
A
Z
Question 1
Donnez une version itérative d'une fonction puissance_v1 qui prend deux arguments : a flottant et n entier naturel ; on garantit que n >= 0.
Indice 1
On pourra faire une boucle qui fait n tours.
Réponse
def puissance_v1(a: float, n: int) -> float:
"Renvoie `a` à la puissance `n`, pour n >= 0"
y = 1
for _ in range(n):
y = y * a
return y
Question 2
Donnez une version récursive de puissance_v1.
Indice 2
On pourra constater que \(3^5 = 3^4 × 3\), et que, de manière générale,
pour \(n > 0\), on a \(a^n = a^{n - 1} × a\)
Réponse 2
def puissance_v1(a: float, n: int) -> float:
"Renvoie `a` à la puissance `n`, pour n >= 0"
if n == 0:
return 1.0
else:
return puissance_v1(a, n - 1) * a
Complexité
Le coût du calcul de puissance_v1(a, n) est de n multiplications entre flottants. Chacune étant à coût constant, on peut dire le coût du calcul est proportionnel à n, on dit linéaire en n.
On note ce coût \(\mathcal O(n)\) quand il est proportionnel à n.
Ainsi, si on sait que puissance(1.000003, 1000000) prend \(0,\!1~\text{s}\), alors, on peut déduire que puissance(1.000003, 100000000) prend \(10~\text{s}\).