Forum programmation
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez | 
 

 Le problème du voyageur de commerce

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Le problème du voyageur de commerce   Mer 23 Avr - 15:45

Citation :
L'énoncé du problème du voyageur de commerce est le suivant : étant donné n points (des « villes ») et les distances séparant chaque point, trouver un chemin de longueur totale minimale qui passe exactement une fois par chaque point et revienne au point de départ
d'apres www.wikipedia.org

Code:
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.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
makram
modérateur
modérateur
avatar

Nombre de messages : 549
Age : 28
Date d'inscription : 29/12/2006

MessageSujet: Re: Le problème du voyageur de commerce   Lun 28 Avr - 17:43

merci mohamed
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
 
Le problème du voyageur de commerce
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum programmation :: Programmation :: Delphi & Pascal :: Pascal :: Cours-
Sauter vers: