Algorithme du voyageur ( non optimisé )

Soyez le premier à donner votre avis sur cette source.

Vue 7 356 fois - Téléchargée 289 fois

Description


Source / Exemple :


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

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
7
Date d'inscription
dimanche 15 décembre 2002
Statut
Membre
Dernière intervention
29 décembre 2002

ENFIN, IL FONCTIONNE... C VITE DIT!
En fait, il se compile comme il faut, mais pour la boucle, ou la la !
Messages postés
7
Date d'inscription
dimanche 15 décembre 2002
Statut
Membre
Dernière intervention
29 décembre 2002

Pour info, c'a l'air de fonctionner sur DevC
Messages postés
1
Date d'inscription
vendredi 11 octobre 2002
Statut
Membre
Dernière intervention
11 octobre 2002

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..
Messages postés
64
Date d'inscription
mercredi 24 juillet 2002
Statut
Membre
Dernière intervention
26 novembre 2009

faut pas essayer de faire l'allemand qui farle français
Messages postés
6
Date d'inscription
dimanche 13 janvier 2002
Statut
Membre
Dernière intervention
27 janvier 2002

bien marrant comme source :)
Afficher les 9 commentaires

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.