hg Register Forum révision Tunisie - Bac Tunisie Algorithmique et programmation , cours, devoir, exercice,edunet

Forum révision Tunisie - Bac Tunisie Algorithmique et programmation , cours, devoir, exercice,edunet Forum Index

hg Revision tunisie scolaire Bac Tunisie Algorithmique et programmation TIC réseaux php javascript sql access activités programmation c
hg
FAQ FAQ Search Search Memberlist Memberlist Usergroups Usergroups Profile Profile Log in to check your private messages Private Messages Log in Log in


 Forum de l'excellence et l'excellence en innovation 
Pour participer à notre Forum révision tunisie , vous devez
 inscrire sur notre forum a partir d'ici
   NB :
Les membres ''zéro messages'' seront supprimés automatiquement après un nombre de jours donné !!!!
             
   
 
  
 
forum d'aide informatique : internet, réseau, programmation informatique ...
Le problème du voyageur de commerce
 
 
Post new topic   Reply to topic    Forum révision Tunisie - Bac Tunisie Algorithmique et programmation , cours, devoir, exercice,edunet Forum Index -> Algorithmique & programmation -> Enregistrements & fichiers
hg Previous topic :: Next topic   hd
Author Message
KARIMOS
Administrateur

Offline

Joined: 02 Nov 2008
Posts: 711
Masculin
Point(s): 4,448
Moyenne de points: 0

Posted: Sun 3 Oct - 07:57 (2010)    Post subject: Le problème du voyageur de commerce Reply with quote

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



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:=0;
  end;

  for i:=1 to n do
    begin
      clrscr;
      write('saisir la ville n° ',i,'  ');
      readln(nom_villes);
      for j:=1 to i-1 do
      begin
        write('distance entre la ville ',nom_villes,' et ',nom_villes[j],' en Km: ');
        readln(distance);
        distance[j,i]:=distance;
      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:=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:=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][/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
Publicité






Posted: Sun 3 Oct - 07:57 (2010)    Post subject: Publicité

PublicitéSupprimer les publicités ?
 
Revenir en haut
Display posts from previous:   
bg bd
Post new topic   Reply to topic    Forum révision Tunisie - Bac Tunisie Algorithmique et programmation , cours, devoir, exercice,edunet Forum Index -> Algorithmique & programmation -> Enregistrements & fichiers All times are GMT + 1 Hour
 
Page 1 of 1

 
Jump to:  
Index | Make forum | Free support forum | Free forums directory | Report a violation | Cookies | Charte | Conditions générales d'utilisation