Cours complet d’initiation à la programmation

• État initial : tas 1 avec un nombre quelconque de cartes, les autres tas sont vides.
• État final : tas 1, 3 et 4 vides, le tas 2 contient toutes les cartes du tas 1 initial.

La résolution du problème nécessite de déplacer (une à une) toutes les cartes du tas 1 vers le tas 2. Ce qu'on peut décrire par

Une boucle tant que se termine lorsque sa condition n'est plus satisfaite. Par conséquent à la sortie de la boucle, on est assuré que la condition est fausse

tant que condition faire

  actions

fin tant que

{condition est fausse}

Comme bien des langages de programmation, Caml permet d'écrire des instructions conditionnellement répétées. La syntaxe de l'instruction tant que est décrite de manière générale ci-dessous.

while < condition > do
  (* sequence d'instructions *)
done

Exemple traduction en Caml de l'algorithme décrit à la section 3.2Algorithme.

while tas_non_vide(1) do
  deplacer_sommet(1,2)
done

Lorsqu'elle sera exécutée, cette instruction testera si le tas 1 est non vide. Si ce n'est pas le cas (c'est-à-dire si le tas 1 est vide) alors l'instruction est terminée, sinon (si le tas 1 n'est pas vide), une carte sera déplacée du tas numéro 1 vers le tas numéro 2. Ce déplacement effectué, la vacuité du tas numéro 1 sera à nouveau testée, et selon le cas l'instruction est terminée ou un déplacement est effectué. Et on poursuit ainsi tant que le tas 1 n'est pas vide.

La conception d'une boucle tant que nécessite plusieurs points d'attention :

• la situation avant d'entrer dans la boucle (précondition) est-elle celle souhaitée ?
  Par exemple, l'instruction qui suit peut être source d'erreur.

   

  Sélectionnez

  1.
  2.
  3.
  

  while sommet_trefle(1) do
    deplacer_sommet(1,2)
  done
  

En effet, la condition du tant que porte sur la couleur de la carte au sommet du tas 1. Pour cela on utilise la fonction sommet_trefle. Mais pour être utilisée, celle-ci nécessite que le tas numéro 1 ne soit pas vide.

• la situation à la sortie de la boucle (postcondition) est-elle bien celle souhaitée ?

• la boucle ne risque-t-elle pas d'être infinie (problème de l'arrêt) ?

Par exemple, l'instruction qui peut conduire à une répétition infinie de déplacement d'une carte du tas 1 vers le tas 2, puis d'un retour de la carte déplacée vers son tas d'origine. En effet si le tas 1 n'est pas vide au moment d'exécuter cette instruction, la condition du tant que est satisfaite et l'action est exécutée, action qui aboutit à la même situation que celle de départ : le tas 1 ne sera jamais vide.

while tas_non_vide(1) do
  deplacer_sommet(1,2);
  deplacer_sommet(2,1)
done

Exercice 3-1

Décrivez les relations satisfaites entre a, b et c à l'issue des boucles qui suivent :

1. tant que a = b faire
     actions
   fin tant que
2. tant que a ≤ b faire
     actions
   fin tant que
3. tant que (a ≠ b) ou (a > c) faire
     actions
   fin tant que

Exercice 3-2

Les exercices de manipulation de cartes.