Problème de voyageur de commerce

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

haiethem

Messages : 410
Points : 13703
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

haiethem

Messages : 410
Points : 13703
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 ne pouvez pas répondre aux sujets dans ce forum