begin process at 2010 02 10 10:06:38
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > LA TRAVERSÉE DU PONT

LA TRAVERSÉE DU PONT


 Information sur la source

Note :
7 / 10 - par 2 personnes
7,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths & Algorithmes Niveau :Débutant Date de création :16/10/2004 Vu :1 784
Auteur : marcdid

Ecrire un message privé
Commentaire sur cette source (4)
Ajouter un commentaire et/ou une note

 Description

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

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



 Sources de la même categorie

Source avec Zip OPERATION SUR LES MATRICES CARREES AVEC CLASSE GENERIQUE par chouhad
Source avec une capture OPÉRATIONS SUR MATRICES C++ par Minilogus
[DEV-C++] CALCUL DE LA RACINE CARRÉE D'UN RÉEL par Jhep
PROGRAMME QUI CALCUL LE PPCM ET LE PGCD par AnoSantino
EVALUER UNE EXPRESSION MATHÉMATIQUE par begueradj
Toutes les sources de la catégorie Maths & Algorithmes

Commentaires et avis

Commentaire de albert0 le 16/10/2004 23:21:43

le temps mimium = 17 ?

:D

Commentaire de ccarniel le 17/10/2004 10:24:19

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++ :)

Commentaire de MPH le 17/10/2004 12:58:28

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.

Commentaire de marcdid le 17/10/2004 23:28:24

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

 Ajouter un commentaire

Nos sponsors


Sondage...

CalendriCode

Février 2010
LMMJVSD
1234567
891011121314
15161718192021
22232425262728

Consulter la suite du CalendriCode
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,484 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)