Algorithmique

Compromis espace/temps

Savez-vous qu'il faut 3 instructions pour échanger 2 variables ?

Oui, bien sûr.

Solution 1 :
ABtmp
au départ :    5      12     ?
tmp <--- A5125
A <--- B12125
B <--- tmp1255

 

Mais savez-vous que l'on peut choisir entre deux compromis différents :

 

Donc comment faire sans 3ème variable ?

Cherchez un peu avant de regarder la solution ...

 

Solution 2 :
AB
0.  au départ :      5       12
1.A <--- A + B1712
2.B <--- A - B175
3.A <--- A - B125

Démonstration en affectant les indices des lignes ci-dessus aux valeurs successives des deux variables :

0.  A0B0
1.A1 <--- A0 + B0B1 = B0
2. A2 = A1 = A0 + B0 B2 <--- A1 - B1 = A0 + B0 - B0 = A0
3. A3 <--- A2 - B2 = A0 + B0 - A0 = B0     B3 = B2 = A0

 

Attention !

La solution 2 ne fonctionne que pour des variables d'un type supportant l'addition et la soustraction sans perte de précision, et pour des valeurs dont la somme ou la différence ne dépassent pas la valeur maximale représentable pour ce type.