begin process at 2008 05 16 06:23:44
1 173 216 membres
58 nouveaux aujourd'hui
13 970 membres club

Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum.
Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

ALGORITHME DU VOYAGEUR ( NON OPTIMISÉ )


Information sur la source

Catégorie :Maths & Algorithmes Niveau : Débutant Date de création : 05/12/2001 Vu / téléchargé: 3 895 / 189

Note :
5 / 10 - par 4 personnes
5,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10

Commentaire sur cette source (5)
Ajouter un commentaire et/ou une note

Description

Source

  • #include<iostream.h>
  • #include<string.h>
  • #include<math.h>
  • const int nbmaxville=100;
  • struct ville
  • {
  • char nom[16];
  • double x,y;
  • };
  • struct liste
  • {
  • int nbville;
  • ville town[nbmaxville];
  • };
  • double distance(ville v1,ville v2)
  • {
  • double x1,y1;
  • x1=v1.x-v2.x;
  • y1=v1.y-v2.y;
  • return (sqrt(x1*x1+y1*y1));
  • }
  • void saisirville(ville &city)
  • {
  • cout<<"Entrez le nom de la fille : ";cin>>city.nom;
  • cout<<"Entrez l'abscisse de la fille : ";cin>>city.x;
  • cout<<"Entrez l'ordonnee de la fille : ";cin>>city.y;
  • }
  • void saisirliste(liste &listeville)
  • {
  • int i,j;
  • ville city;
  • bool cestbon;
  • do
  • {cout<<"combien de fille foulez fous entrer?";cin>>listeville.nbville;}
  • while ((listeville.nbville<0)||(listeville.nbville>100));
  • for (i=0;i<listeville.nbville;i++)
  • {
  • do
  • {
  • saisirville(city);
  • for (j=0;j<i;j++)
  • {
  • if ((strcmp(listeville.town[j].nom,city.nom)==0)||((listeville.town[j].x==city.x)&&(listeville.town[j].y==city.y)))
  • {
  • cout<<"Nom ou emplacement deja vendu."<<endl;
  • cestbon=false;
  • }
  • else cestbon=true;
  • }
  • }while (cestbon==false);
  • listeville.town[i]=city;
  • }
  • }
  • void supprimeville(liste &listeville,ville &city)
  • {
  • int i,j;
  • for (i=0;i<listeville.nbville;i++)
  • {
  • if ((strcmp(listeville.town[i].nom,city.nom))==0)
  • {
  • listeville.nbville--;
  • for (j=i;j<listeville.nbville;j++)
  • {
  • listeville.town[j]=listeville.town[j+1];
  • }
  • }
  • }
  • }
  • void stadtplusproche(liste &listeciudad,int &pproche,double &dist)
  • {
  • int i;
  • pproche=0;
  • dist=distance(listeciudad.town[0],listeciudad.town[listeciudad.nbville-1]);
  • for (i=1;i<listeciudad.nbville-1;i++)
  • {
  • if (distance(listeciudad.town[i],listeciudad.town[listeciudad.nbville-1])<dist)
  • {
  • dist=distance(listeciudad.town[i],listeciudad.town[listeciudad.nbville-1]);
  • pproche=i;
  • }
  • }
  • }
  • void main()
  • {
  • int i,placeville;
  • bool existe;
  • double disttot=0,dist;
  • ville stadt;
  • liste listestadt;
  • existe=false;
  • cout<<"Bonjour, fous allez bien?"<<endl;
  • saisirliste(listestadt);
  • do
  • {
  • cout<<"Feuillez saisir fotre fille de depart? ";cin>>stadt.nom;
  • for (i=0;i<listestadt.nbville;i++)
  • {
  • if ((strcmp(stadt.nom,listestadt.town[i].nom))==0)
  • {
  • stadt=listestadt.town[i];
  • placeville=i;
  • existe=true;
  • }
  • }
  • if (existe==false) cout<<"Fous nous mentez! Cette Stadt n'existe pas! Donnez nous une fille qui existe! Nous afons les moyens de fous faire barler!"<<endl;
  • } while (existe==false);
  • cout<<"Premiere stadt : "<<stadt.nom<<endl;
  • while (listestadt.nbville>1)
  • {
  • listestadt.town[placeville]=listestadt.town[listestadt.nbville-1];
  • listestadt.town[listestadt.nbville-1]=stadt;
  • stadtplusproche(listestadt,placeville,dist);
  • disttot+=dist;
  • supprimeville(listestadt,stadt);
  • stadt=listestadt.town[placeville];
  • cout<<"Stadt suivante : "<<stadt.nom<<endl;
  • cout<<"Distance entre les deux derniere ville : "<<dist<<endl;
  • }
  • cout<<endl;
  • cout<<"Distance totale : "<<disttot<<endl<<endl;
  • }
#include<iostream.h>
#include<string.h>
#include<math.h>

const int nbmaxville=100;


struct ville
{
	char nom[16];
	double x,y;
};


struct liste
{
	int nbville;
	ville town[nbmaxville];
};


double distance(ville v1,ville v2)
{
	double x1,y1;
	x1=v1.x-v2.x;
	y1=v1.y-v2.y;
	return (sqrt(x1*x1+y1*y1));
}


void saisirville(ville &city)
{
	cout<<"Entrez le nom de la fille : ";cin>>city.nom;
	cout<<"Entrez l'abscisse de la fille : ";cin>>city.x;
	cout<<"Entrez l'ordonnee de la fille : ";cin>>city.y;
}


void saisirliste(liste &listeville)
{
	int i,j;
	ville city;
	bool cestbon;
	do
	{cout<<"combien de fille foulez fous entrer?";cin>>listeville.nbville;}
	while ((listeville.nbville<0)||(listeville.nbville>100));
	for (i=0;i<listeville.nbville;i++)
	{
		do
		{
			saisirville(city);
			for (j=0;j<i;j++)
			{
				if ((strcmp(listeville.town[j].nom,city.nom)==0)||((listeville.town[j].x==city.x)&&(listeville.town[j].y==city.y)))
				{
					cout<<"Nom ou emplacement deja vendu."<<endl;
					cestbon=false;
				}
				else cestbon=true;
			}
		}while (cestbon==false);
		listeville.town[i]=city;
	}
}


void supprimeville(liste &listeville,ville &city)
{
	int i,j;
	for (i=0;i<listeville.nbville;i++)
	{
		if ((strcmp(listeville.town[i].nom,city.nom))==0)
		{
			listeville.nbville--;
			for (j=i;j<listeville.nbville;j++)
			{
				listeville.town[j]=listeville.town[j+1];
			}
		}
	}
}

void stadtplusproche(liste &listeciudad,int &pproche,double &dist)
{
	int i;
	pproche=0;
	dist=distance(listeciudad.town[0],listeciudad.town[listeciudad.nbville-1]);
	for (i=1;i<listeciudad.nbville-1;i++)
	{
		if (distance(listeciudad.town[i],listeciudad.town[listeciudad.nbville-1])<dist)
		{
			dist=distance(listeciudad.town[i],listeciudad.town[listeciudad.nbville-1]);
			pproche=i;
		}
	}
}


void main()
{
	int i,placeville;
	bool existe;
	double disttot=0,dist;
	ville stadt;
	liste listestadt;
	existe=false;
	cout<<"Bonjour, fous allez bien?"<<endl;
	saisirliste(listestadt);
	do
	{
		cout<<"Feuillez saisir fotre fille de depart? ";cin>>stadt.nom;
		for (i=0;i<listestadt.nbville;i++)
		{
			if ((strcmp(stadt.nom,listestadt.town[i].nom))==0) 
			{
				stadt=listestadt.town[i];
				placeville=i;
				existe=true;
			}
		}
	if (existe==false) cout<<"Fous nous mentez! Cette Stadt n'existe pas! Donnez nous une fille qui existe! Nous afons les moyens de fous faire barler!"<<endl;
	} while (existe==false);
	cout<<"Premiere stadt : "<<stadt.nom<<endl;
	while (listestadt.nbville>1)
	{
		listestadt.town[placeville]=listestadt.town[listestadt.nbville-1];
		listestadt.town[listestadt.nbville-1]=stadt;
		stadtplusproche(listestadt,placeville,dist);
		disttot+=dist;
		supprimeville(listestadt,stadt);
		stadt=listestadt.town[placeville];
		cout<<"Stadt suivante : "<<stadt.nom<<endl;
		cout<<"Distance entre les deux derniere ville : "<<dist<<endl;
	}
	cout<<endl;
	cout<<"Distance totale : "<<disttot<<endl<<endl;
} 
  • signaler à un administrateur
    Commentaire de Tylos le 24/01/2002 22:48:19

    bien marrant comme source :)

  • signaler à un administrateur
    Commentaire de BaFM le 24/07/2002 17:10:56

    faut pas essayer de faire l'allemand qui farle français

  • signaler à un administrateur
    Commentaire de thelogos le 11/10/2002 15:59:17

    Je n'ai pas lu la suite du code concernant la recherche du plus court chemin, car je pense que l'auteur ne l'a pas compilé ni exécuté.. Apparemment il ne sait pas saisir une liste de villes dont les noms et coordonnées, sont tous différents, donc j'ai de gros doutes pour la suite.. Revoir les boucles  et surtout le problème des boucles infinies..

  • signaler à un administrateur
    Commentaire de caraldesail le 23/12/2002 21:47:30

    Pour info, c'a l'air de fonctionner sur DevC

  • signaler à un administrateur
    Commentaire de caraldesail le 23/12/2002 21:49:55

    ENFIN, IL FONCTIONNE... C VITE DIT!
    En fait, il se compile comme il faut, mais pour la boucle, ou la la !

Ajouter un commentaire

Appels d'offres

Pub



CalendriCode

Mai 2008
LMMJVSD
   1234
567891011
12131415161718
19202122232425
262728293031 

VS Express FR Gratuit !

VS Express en français et 100% gratuit !

Boutique

Boutique de goodies CodeS-SourceS