Exercice☘

Note

Page facultative, exercice d'entraînement

On considère la fonction python suivante:

def f(n):
    """
    n -- entier naturel
    """
    N = n + 2

    while n!=0:

        if N == n:
            n = n-1
        else:
            N = N-1

Question 1☘

Justifier que n prend des valeurs entières positives, décroissantes.
n est-il un variant de la boucle?

n ≥ 0 est un invariant

Note

On rappelle que n positif signifie "n ≥ 0".

Les valeurs prises par n décroissent puisque la seule opération faite sur n est n ← n - 1.
n est un entier positif avant la boucle.
Supposons que l'on soit arrivé à une étape telle que n soit un entier positif en entrée de boucle (ligne 8).
Alors $n > 0$ (car pour n nul on n'entre pas dans la boucle).
Notons $n_e$ la valeur en entrée de boucle et $n_f$ la valeur après exécution du corps de boucle.
On a:
- soit $n_f = n_e -1 \geqslant 0$
- soit $n_f = n_e > 0$ .

En fin de passage dans la boucle, n est donc encore un entier positif.

n variant?

n n'est pas un variant de boucle car les valeurs de n ne décroissent pas strictement. En effet, n reste constant dans le cas $N \neq n$ .

Question 2☘

Justifier que N ne prend ques des valeurs entières.
Justifier que N ≥ n est un invariant de la boucle (c'est à dire que cette propriété est vérifiée à la première entrée dans la boucle et qu'elle est encore vérifiée après chaque passage dans la boucle).
Justifier que N prend des valeurs entières positives, décroissantes.
N est-il un variant de la boucle?

N entier

N est initialisé avec une valeur entière avant la boucle (N ← n+2). Ensuite, les seules opérations faites sur N (N ← N-1) conserve sa nature entière.

N ≥ n est un invariant

Initialisation.
Avant la boucle, on a N = n+2 ≥ n.
Conservation.
Supposons que l'on soit à une étape telle qu'en entrée de boucle on a N ≥ n. On note $N_e$ et $n_e$ les valeurs de N et n en entrée de boucle
et $N_f$ et $n_f$ les valeurs en fin du passage dans la boucle.
On envisage deux cas:
- Cas 1: $N_e = n_e$ . Dans ce cas $N_f = N_e = n_e$ et $n_f = n_e -1$ . Donc $N_f \geqslant n_f$ .
- Cas 2: $N_e \neq n_e$ . Comme $N_e \geqslant n_e$ , on en déduit $N_e > n_e$ . Comme ce sont des entiers, on a $N_e \geqslant n_e+1$ , soit $N_e - 1 \geqslant n_e$ .
  Or on a dans ce cas $N_f = N_e-1$ et $n_f = n_e$ , d'où $N_f \geqslant n_f$ .

Dans tous les cas, la propriété "N ≥ n" est conservée.

N entier positif décroissant

n est un entier positif dans la boucle (cf question 1) et N ≥ n (cf question précédente) et N est entier, donc N est toujours un entier positif.

Par ailleurs, la seule opération faite sur N (N ← N-1) ne peut que décroître sa valeur. Donc N prend des valeurs entières positives décroissantes.

N variant?

N n'est pas un variant de la boucle car les valeurs de N ne décroissent pas strictement. En effet, N reste constant dans le cas "N==n".

Question 3☘

N + n est-il un variant de la boucle?

n+N variant?

La réponse est oui.

Comme n et N ne prennent que des valeurs entières positives, c'est le cas également de n + N.
Il s'agit maintenant de vérifier que n + N prend des valeurs strictement décroissantes. Notons $n_e$ et $N_e$ les valeurs de n et N en entrée de boucle et $n_f$ , $N_f$ les valeurs après un passage dans le corps de boucle.
On envisage deux cas:
- Cas 1: $N_e = n_e$ . Dans ce cas, $N_f = N_e$ et $n_f = n_e -1$ donc $N_f + n_f = N_e + n_e - 1 < N_e + n_e$ .
- Cas 2: $N_e \neq n_e$ . Dans cas, $N_f = N_e - 1$ et $n_f = n_e $ donc $N_f + n_f = N_e + n_e - 1 < N_e + n_e$ .

Conclusion: n+N est un variant de boucle.

Question 4☘

La boucle termine-t-elle nécessairement?

terminaison

On a explicité un variant de boucle, elle termine donc.