Danh sách khoá học Đăng nhập

Thông tin

Tác giả Vincent Branders, Pierre Dupont
Hạn chót 25/03/2026 14:00:00
Giới hạn nộp bài Không có giới hạn

Đăng nhập

Đăng nhập

[TP06] Exponentiation rapide

Soient deux nombres \(x \in \mathbb{Z}\) et \(n \in \mathbb{N}\).

Une façon naïve de calculer \(x^n\) serait de multiplier \(n\) fois \(x\) par lui-même.
Mais on peut faire bien plus efficace que cela !
Il suffit d'utiliser les équations de récurrence suivantes :

\begin{align*} p(x,0) &= 1\\ p(x,n) &= p(x \cdot x,\frac{n}{2}) & \mbox{si $n$ est pair}\\ &= x \cdot p(x \cdot x,\frac{n-1}{2}) & \mbox{si $n$ est impair}\\ \end{align*}

On vous demande d'implémenter un algorithme avec récursion. Avant d'élaborer votre algorithme, détaillez :

  1. le cas de base,
  2. comment traiter le cas de base,
  3. comment construire la solution actuelle (taille n) si je connais une solution pour un problème plus petit (par exemple de taille n-1).
Câu hỏi 1: Exponentiation rapide récursive

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier expo.py qui contient la signature de la fonction et quelques exemples de tests.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

def puiss_rec(x, n):
    """
    Exponentiation rapide par récursion
    pre: `n` >= 0
    post: retourne `x`^`n`
    """
Câu hỏi 2: Nombre d'appels récursifs

Combien y a-t-il d'appels récursifs si n = 64 ?

Câu hỏi 3: Complexité temporelle

Intuitivement, quelle est la complexité temporelle de l’algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

On suppose que vous n'effectuez pas d'opérations inutiles.

Note : de façon générale, on exprime toujours une complexité (temporelle ou spatiale) en fonction de la taille du problème traité.

Pour la grande majorité des algorithmes étudiés dans ce cours, la taille du problème est simplement le nombre de valeurs à mémoriser
dans la collection (une liste, un tableau, un arbre, un graphe, ...) qui contient les données et sur laquelle l'algorithme réalise un calcul.

Ici, la taille du problème est la puissance \(n\) à calculer puisque, logiquement, il peut y avoir plus ou moins d'opérations à faire selon la puissance considérée.
Ce n'est donc pas un hasard si nous dénotons par \(n\) la puissance à calculer puisque c'est la notation la plus courante pour exprimer la taille du problème traité.


Câu hỏi 4: Complexité temporelle de la méthode naïve

Comme énoncé au début de l'exercice, une façon naïve de calculer \(x^n\) serait de multiplier \(n\) fois \(x\) par lui-même. Quelle est la complexité temporelle d'un tel algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

Câu hỏi 5: Faites vos jeux

Les deux approches étudiées dans cet exercice ont leurs propres qualités et défauts. Sélectionnez, parmi les propositions suivantes, les qualités de chacune. Sur base de vos réponses, quelle approche devriez-vous utiliser pour la puissance d'un nombre ?