QCM☘

QCM 1☘

On considère la fonction python suivante:

def f(a,b):
    """
    a -- entier naturel
    b -- entier naturel
    """

    while a >= 0 and b >= 0:
        if a < b:
            a, b = b, a
        else:
            a = a - 1
    return a

a est un variant de la boucle
b est un variant de la boucle
a + b est un variant de la boucle
a + 2b est un variant de la boucle
a + 2b + 1 est un variant de la boucle

Réponse

a est un variant de la boucle
b est un variant de la boucle
a+b est un variant de la boucle
a + 2b est un variant de la boucle
a + 2b + 1 est un variant de la boucle
a n'est pas un variant car il peut augmenter (dans la partie if a<b: a,b = b,a)
b n'est pas un variant car il ne diminue pas dans le cas a ≥ b.
a + b n'est pas un variant car il reste constant dans le cas a < b.
Vérifions maintenant que a + 2b est un variant. Les valeurs prises par a + 2b sont clairement des entiers positifs dans la boucle. On note $a_e$ , $b_e$ les valeurs de a et b en entrée de boucle et $a_f$ , $b_f$ les valeurs en fin de boucle.
- Si $a_e$ ≥ $b_e$ alors $a_f = a_e -1$ et $b_f = b_e$ , on a donc $a_f + 2b_f = a_e -1 + 2b_e < a_e + 2b_e$ .
- Si $a_e < b_e$ alors $a_f = b_e$ et $b_f = a_e$ . On a donc $a_f + 2b_f = b_e + 2a_e$ D'où \begin{align} a_f + 2b_f < a_e + 2b_e &\Longleftrightarrow b_e + 2a_e < a_e + 2b_e \ &\Longleftrightarrow 2a_e - a_e < 2b_e - b_e \ &\Longleftrightarrow a_e < b_e \end{align} On a donc bien $a_f + 2b_f < a_e + 2b_e$ .
On établit de même que a + 2b + 1 est un variant de la boucle.

QCM 2☘

On considère la fonction python suivante:

def puissanceDeDeux(n):
    """
    n -- entier naturel

    renvoie 2 à la puissance n
    """

    p = 1
    c = 0

    while c < n:
        p = 2*p
        c = c+1
    return p

n est un variant de la boucle
p est un variant de la boucle
c est un variant de la boucle
n-c est un variant de la boucle
2n-c est un variant de la boucle

Réponse

n est un variant de la boucle
p est un variant de la boucle
c est un variant de la boucle
n-c est un variant de la boucle
2n-c est un variant de la boucle

QCM 3☘

Pour une boucle python du type suivant dans laquelle n est un entier fixé:

for i in range(n):
    ...

alors n - i:

est un variant de boucle
n'est pas nécessairement un variant de boucle.

Réponse

est un variant de boucle
n'est pas nécessairement un variant de boucle.

Attention, toutefois:

Avec le code suivant en JavaScript:

let s = 0;

for(let i=0; i<10; i += 1)
{
  s = s + i; 
  i = i + 2;
}

en sortie de boucle, on obtient: s = 18.
En effet, on commence avec s = 0 et i = 0.
Au premier passage, s ← s+i donc s = 0.
Puis i est augmenté de 2: i = 2.
Puis i est augmenté de 1 (par le code i += 1 qui s'exécute en fin de boucle): i = 3.
Au passage suivant: s ← s+i donc s = 3.
Puis i est augmenté de 2 puis de 1, donc i = 6.
Au passage suivant: s ← s+i donc s = 9.
Puis i est augmenté de 2 puis de 1, donc i = 9.
Au passage suivant: s ← s+i donc s = 18.
Puis i est augmenté de 2 puis de 1, donc i = 12. Donc la boucle n'est plus exécutée.

Ce comportement semble contredire notre affirmation "n - i est un variant".
Imaginons en effet que l'on remplace la ligne i = i +2par i = i - 3 alors à chaque passage de boucle, i sera décrémenté de 3 puis incrémenté de 1, donc i sera décrémenté de 2.
Donc n - i sera lui augmenté de 2 à chaque passage: ce n'est pas un variant.

Avec Python toutefois, l'affirmation est correcte. Testons le code analogue au code javascript avec Python:

s = 0

for i in range(10):
    s = s + i 
    i = i + 2

Testez! On constate que s vaut 45 en sortie de boucle, c'est à dire la même valeur que pour le code:

s = 0

for i in range(10):
    s = s + i

En python, la valeur i va prendre successivement les valeurs 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 et ceci même si on cherche à agir sur la variable i à l'intérieur de la boucle. Et n - i est bien un variant de boucle.

On retiendra:

Important

Lorsqu'on utilise une boucle for( i ..., que ce soit en algorithmique, ou en programmation (quelque soit le langage utilisé), on ne cherchera jamais à modifier i dans le corps de la boucle. Cela sera toujours considéré comme une très mauvais pratique (cela ne peut que rendre très peu lisible votre code). Si vous avez besoin d'agir sur i, programmez une boucle while et non une boucle for.

Important

Un raisonnement de correction ou de terminaison d'algorithme doit être indépendant du langage utilisé. Il faut toujours éviter d'inclure dans son raisonnement des particularités d'un langage donné.