Puissance

On considère la fonction python suivante:

def puissance(a, n):
    """
    a -- entier strictement positif
    n -- entier naturel

    renvoie le nombre a exposant n (a**n)
    """

    A = a
    N = n
    p = 1

    while N > 0:
        if N%2 == 0:
            A = A*A
            N = N//2
        else:
            p = p * A
            N = N - 1
    return p

Démontrer que cette fonction termine en explicitant un variant.

Indication

Montrez que N est un variant.

Une résolution

On montre que N est un variant.

• N prend des valeurs entières (c'est un entier au départ et toutes les opérations effectuées sur N le laissent entier).
• N prend des valeurs positives dans la boucle (puisque la condition d'entrée est N > 0).
• Il faut ensuite établir que N décroit strictement à chaque passage dans la boucle.
  Notons $N_e$ la valeur de N en entrée d'un passage dans la boucle et $N_f$ sa valeur en sortie de ce passage dans la boucle.
  • Cas 1: $N_e$ est pair (donc $N_e$ ≥ 2).
    Après exécution du corps de boucle, N prend la valeur $N_f$ = $N_e$//2: on a bien $N_f$ < $N_e$.
  • Cas 2: $N_e$ est impair. Dans ce cas, $N_f = N_e -1$. et $N_f < N_e$.

N est bien un variant de boucle: la boucle while termine.