Échange de variables

vendredi 10 septembre 2010
par  Alain BUSSER

L’énoncé est inspiré du livre de Guillaume Connan : Échanger les contenus de deux variables. L’algorithme de Guillaume Connan implémente cet échange sans faire intervenir une troisième variable. Cette contrainte n’était ici pas imposée.

L’énoncé du TP est téléchargeable ici :

le sujet du TP en pdf

En fait aucun élève n’a réussi la première partie du TP (aussi celle-ci n’était-elle pas notée).

L’effet attendu était la création spontanée de l’algorithme suivant :

Mettre 3 dans x
Mettre 8 dans y
Mettre x dans y
Mettre y dans x

C’est bien ce qui s’est passé. Mais les élèves n’ont pas pensé à créer une autre variable que x et y, pour y stocker temporairement les anciennes valeurs afin que celles-ci ne soient pas écrasées par les nouvelles. En effet, si on examine le script en mode pas-à-pas, on constate que le problème vient de la ligne 7, où y écrase x :

Surprenamment, ce phénomène semble très difficile à imaginer par les élèves : Alors que

x prend 3
x prend 8

leur semble simple à comprendre (ils savent qu’à la fin, x=8), dans le cas présent, l’idée qu’on prenne le nombre dans y pour le mettre dans x leur paraît un mouvement (remplacement) et non une copie. L’image des nombres dans les tiroirs n’est donc pas idéale pour décrire un algorithme (quand on transfère le contenu d’un tiroir à un autre tiroir, le premier tiroir est vide !). Dans le cas présent, il s’agit plus d’une copie que d’un transfert. La description des tiroirs a alors été abandonnée pour parler de téléchargement :

Lorsque vous téléchargez un logiciel sur 01net, l’original qui se trouve sur le site 01net est-il modifié ? Disparaît-il ?

Réponse de certains élèves : « Je ne télécharge rien, de peur que ce ne soit pas libre » (humour de lycéen...)

La description de la situation par le remplissage progressif d’un tableau permet de mieux préciser ce qui se passe :

  • Après la ligne 2, on a
x
  • Après la ligne 3, on a
x
y
  • Après la ligne 5, on a
x 3
y
  • Après la ligne 6, on a
x 3
y 8

Mais après la ligne 7, on a

x 8
y 8

Le 3 ayant disparu dans les limbes, on ne peut plus le récupérer !

Le même tableau a facilité le corrigé : Pour peu que l’on pense à créer une troisième variable z, on a

x 3
y 8
z

puis, après avoir mis x dans z :

x 3
y 8
z 3

ce qui permet d’écraser une des occurences du 3 sans perdre ce nombre à tout jamais. La suite de l’algorithme donne successivement

x 8
y 8
z 3

puis par « transfert » (en fait, copie) de z vers y :

x 8
y 3
z 3

ce qui répond à la question.

Aucun élève n’a réussi à trouver cet algorithme, sauf un, qui avait utilisé deux variables (en JavaScript, un problème technique ayant fait renoncer à AlgoBox) :

  1. var x=3;
  2. var y=8;
  3. var a=y;
  4. var b=x;
  5. x=a;
  6. y=b;
  7. Println(x);
  8. Println(y);

Télécharger

Seulement, à force de tâtonner dans tous les sens, cet élève a oublié le script ci-dessus, et a recréé de mémoire la version incomplète ci-dessous :

Les autres élèves ont opté pour des tentatives plus compliquées, parce que reposant sur des opérations et non des simples copies. Exemple typique :


La deuxième partie du TP, la seule qui était notée, était de la programmation : Traduire en JavaScript (pour la raison technique évoquée ci-dessus) l’algorithme de l’énoncé, puis le tester. L’erreur la plus fréquente a été l’oubli du signe de multiplication :

On remarquera à cet effet la richesse de l’affichage des erreurs de syntaxe par Rhino (moteur JavaScript), qui, s’il n’indique pas exactement la cause de l’erreur [1], met en exergue la ligne où est apparue l’erreur. Par contraste, qui se sentirait capable en moins de 10 minutes, de dire où est l’erreur dans le script AlgoBox ci-dessous ?

Or, 10 minutes quand on est dans une salle exigüe pleine d’ordinateurs surchauffés et d’élèves encore plus surchauffés (et trop nombreux) c’est énorme, surtout quand d’autres élèves appellent au secours au même moment...

Pour l’algorithme de la fin du TP, il reste à démontrer qu’il réalise bien l’échange entre x et y.

La démonstration la plus élégante consiste à décrire chacune des affectations par une matrice, et à calculer le produit des matrices pour montrer que ce produit est une symétrie par rapport à y=x (échange de x et y) :

$$\left(\begin{array}{rr}\frac{1}{4}&-\frac{1}{8} \\ 0&1 \end{array}\right)\left(\begin{array}{rr}1&0 \\ \frac{1}{2}&4 \end{array}\right)\left(\begin{array}{rr}2&-8 \\ 0&1 \end{array}\right)=\left(\begin{array}{rr}0&1 \\ 1&0 \end{array}\right)$$

Il va de soi que cette démonstration ne peut être donnée en Seconde ! La méthode de Hoare pas vraiment non plus... Par contre on peut raisonner avec un calcul littéral :

  • Si initialement, x contient $a$ et y contient $b$,
  • après la ligne 3, x contient $2a-8b$ et y contient toujours $b$ ;
  • après la ligne 4, x contient $2a-8b$ et y contient $\frac{2a-8b}{2}+4b=a-4b+4b=a$ ;
  • enfin après la ligne 5, y contient toujours $a$ et x contient $\frac{a}{4}-\frac{2a-8b}{8}=\frac{a}{4}-\left(\frac{a}{4}-b \right)=b$ cqfd

La morale de ce TP, c’est que le choix de l’outil n’est nullement anodin : Avec leur affectation « simultanée » de plusieurs variables [2], les langages lua et Python rendent tout le TP inutile, comme le montre la séance IDLE ci-dessous :


[1il s’agit alors de comprendre que, après « x=2 », JavaScript attend un point-virgule, et que cette affectation n’est pas celle voulue à cause de l’absence du signe « * » ; pas simple mais on s’y fait assez vite, ne serait-ce qu’en regardant l’expression.

[2due à des conversions spontanées en listes de nombres


Commentaires

Logo de Axel
mardi 8 mai 2012 à 23h42 - par  Axel

Echange de 2 variables -> une petite astuce :

x=x+y
y=x-y
x=x-y