Problème de voyageur de commerce

Poster un nouveau sujet   Répondre au sujet

Voir le sujet précédent Voir le sujet suivant Aller en bas

Problème de voyageur de commerce

Message par haiethem le Dim 14 Avr - 0:23

Le prolème de voyageur de commerce est issu du faite qu'un voyageur commercial est appélé à visiter n villes en passant une seule fois par ville et termine par revenir à la ville de départ. Tout ça en parcourant la distance minimale.

_________________
=================================
Haiethem Elguediri
Lycée Secondaire Mareth
+21652084191
+21652906038
+21631139805
+21675321050
haiethem@gmail.com
www.haiethem.tk
avatar
haiethem

Messages : 414
Points : 13858
Réputation : 3
Date d'inscription : 08/11/2010
Age : 40

Voir le profil de l'utilisateur http://www.haiethem.tk

Revenir en haut Aller en bas

Re: Problème de voyageur de commerce

Message par haiethem le Dim 14 Avr - 0:25

Program pvc;
uses wincrt;
type
nv=array[1..10] of string[10];
dis=array[1..10,1..10]of real;
traj=array[1..10] of byte;
vis=array[1..10] of boolean;

var
nom_villes:nv;
distance:dis;
v_depart:byte;
trajet:traj;
visite:vis;
n:byte;


procedure saisie_liste(var n:byte;var nom_villes:nv;var distance:dis);
var
i,j:byte;
begin
repeat
write('Combien de ville vous allez visiter? ');
readln(n);
until (n in [1..20]);

for i:=1 to n do
begin
distance[i,i]:=0;
end;

for i:=1 to n do
begin
clrscr;
write('saisir la ville n° ',i,' ');
readln(nom_villes[i]);
for j:=1 to i-1 do
begin
write('distance entre la ville ',nom_villes[i],' et ',nom_villes[j],' en Km: ');
readln(distance[i,j]);
distance[j,i]:=distance[i,j];
end;
end;
end;

procedure saisie_ville(n:byte; var v_depart:byte);
begin
repeat
write('saisir le numéro de la ville de départ : ');
readln(v_depart);
until (v_depart in [1..n]);
end;

function ville_proche_non_visite(vv:byte; distance :dis; visite:vis; n:byte): byte;
var
k,pv:byte;
begin
k:=1;
while (visite[k]=true) do
begin
k:=k+1;
end;

pv:=k;
for k:=k+1 to n do
begin
if (visite[k]=false) and (distance[vv,k]< distance[vv,pv]) then
pv:=k;
end;

ville_proche_non_visite:=pv;
end;

procedure former_trajet(n:byte; distance:dis;v_depart:byte; var visite:vis; var trajet :traj);
var
i,vv:byte;
begin
for i:=1 to n do
visite[i]:=false;

trajet[1]:=v_depart;
visite[v_depart]:=true;

vv:=v_depart;
for i:=2 to n do
begin
vv:=ville_proche_non_visite(vv,distance,visite,n);
trajet[i]:=vv;
visite[vv]:=true;
end;
end;

procedure affiche_trajet(n:byte;trajet:traj;nom_villes:nv);
var
i:byte;
begin
for i:= 1 to n do
write(nom_villes[trajet[i]], ' --> ');

write(nom_villes[trajet[1]]);
end;

begin
saisie_liste(n,nom_villes,distance);
saisie_ville(n,v_depart);
former_trajet(n,distance,v_depart,visite,trajet);
affiche_trajet(n,trajet,nom_villes);
end.

_________________
=================================
Haiethem Elguediri
Lycée Secondaire Mareth
+21652084191
+21652906038
+21631139805
+21675321050
haiethem@gmail.com
www.haiethem.tk
avatar
haiethem

Messages : 414
Points : 13858
Réputation : 3
Date d'inscription : 08/11/2010
Age : 40

Voir le profil de l'utilisateur http://www.haiethem.tk

Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous pouvez répondre aux sujets dans ce forum