Les quatre musiciens

Quatre musiciens sont à gauche d'un pont; il fait nuit et il y a une seule torche; deux personnes au maximum peuvent traverser à la fois, et celui ou ceux qui traversent doivent avoir la torche pour éclairer le pont, sinon ils tombent dans l'eau. Le premier met 10 minutes pour traverser le pont, le deuxième 5 minutes, le troisième 2 minutes et le quatrième une minute.

Si le premier traverse en même temps que le deuxième, le temps de leur traversée sera de 10 minutes.

Ils doivent traverser le pont en 17 minutes.

Introduction

Nous allons réaliser le programme qui trouve les solutions de ce problème.

On commence par présenter les données :

1) - les musiciens qui sont à gauche du pont

2) - les musiciens qui sont à droite du pont

3) - le temps de traversée pour chacun

4) - le temps total de traversée

5) - l'endroit où se trouve la torche.

Et voici la modélisation de ces données :

1) - gauche : array[1..4] of boolean;

Si le premier musicien est à gauche du pont alors gauche[1]=true, sinon false. En même temps que gauche[1]=true, on a droite[1]=false, car le musicien ne peut pas se trouver en deux endroits différents au même moment

2) - droite : array[1..4] of boolean;

Si le premier musicien est à droite du pont alors droite[1]=true, sinon false.

3) const temps : array[1..4] of integer = (10,5,2,1); // minutes nécessaires

4) var minutes : integer;

5) var torche_a_gauche : boolean;

Analyse du problème

Les musiciens traversent le pont au maximum deux à la fois.

S'ils sont deux, les possibilités sont :

1,2; 1,3; 1,4; 2,3; 2,4; 3,4

Cela se traduit par deux boucles imbriquées :

for i:=1 to 4 do

for j:=i+1 to 4 do

Si à un instant donné on a la torche à gauche et qu'on veut traverser le pont, alors on considère que la torche va passer à droite, donc on écrit tout simplement :

torche_a_gauche:=false;

La traversée d'un musicien de gauche à droite se traduit par :

gauche[i]:=false;

droite[i]:=true; //--- "i" étant le numéro du musicien

Ce programme étant récursif (c'est à dire qu'il fait des essais de traversée successifs de la gauche vers la droite, de la droite vers la gauche et ainsi de suite), il faut mémoriser la position en cours avant chaque traversée (de façon à la restaurer si la traversée faite débouche plus tard sur un échec (temps total supérieur à 17 minutes)).

On note le sens de traversée par un entier égal à "1" ou "-1", ce qui facilite l'appel récursif avec un appel "chercher(-sens)"; au début sens=1, ensuite dans le parcours de l'arbre, suivant le niveau de profondeur, il sera égal à 1 ou -1.

On va ajouter un autre paramètre à la procédure "chercher" qui représente le chemin parcouru à un instant donné, au bout de n traversées.

Si, par exemple, on a deux musiciens ("i" et "j") qui traversent le pont, alors on les mets dans une chaîne de caractères "s1" :

s1:=inttostr(i)+','+inttostr(j);

On appelle ensuite récursivement la procédure "chercher", avec le chemin déjà parcouru noté "s" auquel on ajoute le sens de la traversée (indiqué par une flèche "<-" ou "->";

chercher(-sens,s+' <-'+s1+';');

On doit ensuite prendre en compte le dernier déplacement effectué par un ou deux musiciens. En effet, rien n'empêche le programme récursif de faire le mouvement suivant:

- déplacement vers la droite du musicien 1. La torche se trouve donc à droite.

- déplacement vers la gauche du musicien 1. La torche est maintenant à gauche.

- déplacement vers la droite du musicien 1. La torche est maintenant à droite.

Et ainsi de suite, ce qui nous entraîne dans une boucle infinie (en fait ici elle n'est pas infinie à cause du temps qui s'additionne pendant les traversées; mais cela nous fait perdre énormément de temps pendant la récursivité). On doit donc sauvegarder le dernier mouvement effectué et le comparer à celui que nous allons effectuer. Supposons que nous déplaçons le musicien "1" vers la droite; on mémorise dans une chaîne "1". Si ensuite on veut déplacer "1" vers la gauche, on compare avec la chaîne mémorisée, et on voit qu'elles sont égales, donc ce mouvement ne sera pas effectué.

Voici l'entête de la procédure "chercher" :

procedure chercher(sens : integer; s,last : string);

où "s" est le chemin parcouru et "last" le(s) musicien(s) ayant effectué la dernière traversée; pour deux musiciens on a :

s1:=inttostr(i)+','+inttostr(j);

if s1<>last then

chercher(-sens,s+' <-'+s1+';',s1);

Une traversée complète d'un musicien "i" sera donc codée par :

droite[i] := true; gauche[i] := false; // traversée
torche_a_gauche := false; // on déplace la torche à droite
inc(minutes, temps[i]); // addition nombre de minutes
s1 := inttostr(i);
if s1 <> last then // si mouvement différent du mouvement précédent
 chercher(-sens, s + s1 + '->;', s1); // alors appel récursif
droite[i] := false; gauche[i] := true; // restauration positions initiales
torche_a_gauche := true; // on remet la torche à gauche
dec(minutes, temps[i]); // restauration nombre de minutes

La procédure récursive sera donc constituée de deux boucles imbriquées, et de nombreux tests pour déterminer quels sont les musiciens qui se déplacent, d'affectations de positions et de restauration de positions. Il est plus intéressant de commencer par déplacer les musiciens deux par deux au lieu de un par un (c'est à dire tout seuls).

Le point d'arrêt de la procédure est le suivant :

 if minutes = 17 then
 if droite[1] and droite[2] and droite[3] and droite[4] then
 begin
 fini := true;
 listbox1.items.add('trouvé !');
 listbox1.items.add(s);
 listbox1.refresh;
 exit;
 end
 else
 exit;

En exécutant cette procédure on constate que le programme affiche des solutions doubles. Cela est dû à l'opération suivante :

une fois qu'on a fait "3,4 ->" alors on teste :

"<- 1,2"

"<- 1,3" 3 part tout seul à gauche car droite[1]=false; (*)

"<- 1,4" 4 part tout seul à gauche car droite[1]=false;

"<- 2,3" 3 part tout seul à gauche car droite[1]=false; (*)

L'ordinateur prend donc deux fois le musicien "3" (pendant le parcours récursif) et le déplace à gauche, et comme ce mouvement mène à la solution, on a des doublons dans l'affichage.

Il faut donc mémoriser les solutions trouvées et comparer chaque nouvelle solution à celles déjà trouvées.

Télécharger le code source Delphi