La traversée du pont

Soyez le premier à donner votre avis sur cette source.

Snippet vu 3 390 fois - Téléchargée 33 fois

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 !

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;
}

A voir également

Ajouter un commentaire Commentaires
Messages postés
12
Date d'inscription
samedi 7 février 2004
Statut
Membre
Dernière intervention
29 mai 2007

Je n'ai pas trouvé nécessaire de donner un nom particulier aux variables i,j,k car ce sont des compteurs. En revanche le nom de s aurait pu etre plus explicite en effet. Merci pour la remarque au sujet de cette variable et du sizeof, ma version fait un peu bricolage car je ne savais pas comment retourner la taille du type int, en effet pour le main, j'ai laissé le script initial de dev-C++ par paresse, excellent soft d'ailleurs... Oui c mon premier prog en C++ mais g deja prgmé pas mal en qbasic, pascal et énormément sur ma hp48gx :) je suis beaucoup plus matheux mais j'aime bien programmer c intéressant et le c++ me plaît. Merci pour vos commentaires
Messages postés
6
Date d'inscription
lundi 16 juillet 2001
Statut
Membre
Dernière intervention
24 mai 2007

si tu fait :

s = sizeof(Suite)/4;

pour avoir le nombre d'elements du tableau, ca ne marchera pas sur un cpu 64 bits parce que le type int est fait selon la taille du bus du cpu.

pour avoir la bonne taille tout le temps, il faut faire :

s = sizeof(Suite) / sizeof(Suite[0]);

et pour ton main pas besoin de passer les argc, ... puisque tu les utilises pas.

Au sinon pas mal pour un 1er programme mais on dirait que tu as deja programmé avant en basic ou en turbo pascal.
Messages postés
23
Date d'inscription
samedi 24 janvier 2004
Statut
Membre
Dernière intervention
17 octobre 2004

c'est quoi ce "s=sizeof(Suite)/4;" ?

surtout le 4 ???

Ensuite, utilise des noms de variable explicite, parce que i,j,k,s c'est incompréhensible.

Sinon, pas d'autre commentaire après 30" de lecture.
Bon amusement avec le C++ :)
Messages postés
249
Date d'inscription
mercredi 27 novembre 2002
Statut
Membre
Dernière intervention
9 août 2008

le temps mimium = 17 ?

:D

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.