La traversée du pont
Contenu du snippet
Tout commence par une petite histoire...
Quatre voyageurs V1,V2,V3,V4 sont sur la rive gauche d'une rivière à côté d'un pont fragile qui ne peut pas supporter le poids de plus de 2 voyageurs à la fois. Ils souhaitent se rendre sur la rive droite de la rivière. Il fait nuit et ils ne disposent que d'une torche lumineuse indispensable à la traversée du pont. Il n'est pas possible de lancer la torche donc celle ci doit faire des allers et retours pour permettre le passage des voyageurs en plusieurs fois, des voyageurs traversant la rivière de droite à gauche pour ramener la torche. Les voyageurs ont des capacités physiques différentes, V1 traverse en 1 min, V2 en 2 min, V3 en 5 min, V4 en 10 min.
La solution est la suivante, dans le cas général (nombre de voyageurs >=4)
Tous les voyageurs qui on besoins d'un temps ti > 2t2-t1 doivent traverser par 2 après que V1 et V2 aient rejoint la rive droite selon le schéma: [V1V2 ->] [<-V1] [ViVj][<-V2]. Les groupements par 2 doivent se faire dans l'ordre: les 2 voyageurs les plus lents ensemble, puis les 2 plus lents restants....tant qu'il reste des voyageurs lents (ti>2t2-t1). Les autres voyageurs doivent ensuite traverser accompagnés de V1 qui ramène la torche selon le schéma: [V1Vj->][V1<-]
L'algorithme que j'ai réalisé présente le cas de 4 voyageurs mais il suffit de modifier la taille de la matrice ligne 'Suite' et de rentrer les temps de traversée de chaque voyageurs pour obtenir la solution de n'importe quel autre cas.
Je précise qu'il s'agit de mon tout premier programme C++, enfin le 2e juste après le "hello world" :) donc merci d'être indulgent, il est sûrement possible de faire plus court, d'utiliser un minimum de ressources, créer des fonctions, variables locales ... J'attends donc vos réflexions à ce sujet, car j'aimerais l'améliorer: demande à l'utilisateur du nombre de voyageurs, des temps de passage, tri croissant des temps de passage dans une nouvelle matrice, affichage en fenêtre windows, animation.... bref on peut s'amuser !
Quatre voyageurs V1,V2,V3,V4 sont sur la rive gauche d'une rivière à côté d'un pont fragile qui ne peut pas supporter le poids de plus de 2 voyageurs à la fois. Ils souhaitent se rendre sur la rive droite de la rivière. Il fait nuit et ils ne disposent que d'une torche lumineuse indispensable à la traversée du pont. Il n'est pas possible de lancer la torche donc celle ci doit faire des allers et retours pour permettre le passage des voyageurs en plusieurs fois, des voyageurs traversant la rivière de droite à gauche pour ramener la torche. Les voyageurs ont des capacités physiques différentes, V1 traverse en 1 min, V2 en 2 min, V3 en 5 min, V4 en 10 min.
La solution est la suivante, dans le cas général (nombre de voyageurs >=4)
Tous les voyageurs qui on besoins d'un temps ti > 2t2-t1 doivent traverser par 2 après que V1 et V2 aient rejoint la rive droite selon le schéma: [V1V2 ->] [<-V1] [ViVj][<-V2]. Les groupements par 2 doivent se faire dans l'ordre: les 2 voyageurs les plus lents ensemble, puis les 2 plus lents restants....tant qu'il reste des voyageurs lents (ti>2t2-t1). Les autres voyageurs doivent ensuite traverser accompagnés de V1 qui ramène la torche selon le schéma: [V1Vj->][V1<-]
L'algorithme que j'ai réalisé présente le cas de 4 voyageurs mais il suffit de modifier la taille de la matrice ligne 'Suite' et de rentrer les temps de traversée de chaque voyageurs pour obtenir la solution de n'importe quel autre cas.
Je précise qu'il s'agit de mon tout premier programme C++, enfin le 2e juste après le "hello world" :) donc merci d'être indulgent, il est sûrement possible de faire plus court, d'utiliser un minimum de ressources, créer des fonctions, variables locales ... J'attends donc vos réflexions à ce sujet, car j'aimerais l'améliorer: demande à l'utilisateur du nombre de voyageurs, des temps de passage, tri croissant des temps de passage dans une nouvelle matrice, affichage en fenêtre windows, animation.... bref on peut s'amuser !
Source / Exemple :
#include <iostream>
#include <stdlib.h>
using namespace std;
int Suite[5];
int Temps;
int i,j,k,s;
int Temps_Total;
int main(int argc, char *argv[])
{ s=sizeof(Suite)/4;
Suite[0]=0;
Suite[1]=1;
Suite[2]=2;
Suite[3]=5;
Suite[4]=10;
Temps=2*Suite[2]-Suite[1];
Temps_Total=0;
for(i=s-1, j=s-2; Suite[i]>Temps+1, Suite[j]>Temps; i=i-2, j=j-2)
{
cout << "[V" << 1 << " V" << 2 << " ->]" << "\n";
cout << "[V" << 1 << " <-]" << "\n";
cout << "[V" << j << " V" << i << " ->]" << "\n";
cout << "[V" << 2 << " <-]" << "\n";
Temps_Total=Temps_Total+Suite[2]+Suite[1]+Suite[i]+Suite[2];
}
cout << "[V" << 1 << " V" << 2 << " ->]" << "\n";
Temps_Total=Temps_Total+Suite[2];
k=3;
while(k<j+2)
{
cout << "[V" << 1 << " <-]" << "\n";
cout << "[V" << 1 << " V" << k << " ->]" << "\n";
k=k+1;
Temps_Total=Temps_Total+Suite[1]+Suite[k];
}
cout << "\n" << "Temps total de la traversee: " << Temps_Total << " minutes." << "\n";
system("PAUSE");
return 0;
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.