IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Pascal Discussion :

Tri par fusion


Sujet :

Pascal

  1. #1
    Futur Membre du Club
    Inscrit en
    Août 2005
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : Août 2005
    Messages : 4
    Points : 6
    Points
    6
    Par défaut Tri par fusion
    bonjour à vous chers developpeurs svp je voudrais savoir s'il y a quelqu'un qui pourrait corriger mon algorithme de tri par fusion en pascal, je ne vois pas ou se trouve le pb,il compile mais l'execution ne produit l'effet escompté.

    Merci

    voici le code source:


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
     program trifusion;
    uses crt;
    type vecteur=array [1..100] of real;
    var tab,tab1,tab2:vecteur;
        c,nf,ns:integer;
        {procedure de remplissage du tableau avec des valeurs al‚atoires}
    procedure remplitab(var tab:vecteur;n:integer);
    var i:integer;
    begin
          randomize;
          for i:=1 to n do
            begin
                  tab[i]:=random(50);
            end;
    end;
    { procedure d'affichage des elts du tableau}
    procedure affichtab(var tab:vecteur;n:integer);
    var i:integer;
    begin
          writeln('Voici les ‚l‚ments du tableau');
          for i:=1 to n do
           begin
                 writeln(tab[i]:0:0);
           end;
    end;
    {procedure qui copie les  n1 premiers elts  du tableau tab ds tab1 et le reste dans tab2}
    procedure scinder(tab:vecteur;n:integer;var tab1:vecteur;n1:integer;var tab2:vecteur);
    var i,j:integer;
    begin
          i:=1;
          j:=1;
          while (i<=n1) do
          begin
                tab1[i]:=tab[i];
                i:=i+1;
          end;
          while (i<=n) do
          begin
                tab2[j]:=tab[i];
                j:=j+1;
                i:=i+1;
          end;
    end;
    {procedure qui copie tab2 a la fin de tab1 de taille initiale n1.la copie
     debute … l'indice i2 dans tab2.aprŠs la copie la nvelle taille de tab1 est retourn‚e par la fonction}
    function concatener(var tab1:vecteur;n1:integer; tab2:vecteur;n2:integer;i2:integer):integer;
    var i:integer;
    begin
           i:=0;
           while (i<n2) do
           begin
                tab1[n1+1]:=tab2[i2+i];
                n1:=n1+1;
                i:=i+1;
           end;
           concatener:=n1;
    end;
    {procedure qui recopie les elts des tableaux tab1 et tab2 dans tab de fa‡on … ce qu'ils soient tri‚s
    les elts de tab1 et tab2 sont suppos‚s tri‚s}
    procedure fusionner(var tab:vecteur; tab1:vecteur;n1:integer; tab2:vecteur;n2:integer);
    var i1,i2,i:integer;
    begin
          i1:=1;
          i2:=1;
          i:=1;
          while (i1<=n1) and (i2<=n2) do
          begin
               if (tab1[i1]<tab[i2]) then
                  begin
                        tab[i]:=tab1[i1];
                        i1:=i1+1;
                  end
                  else
                  begin
                        tab[i]:=tab2[i2];
                        i2:=i2+1;
                  end;
                  i:=i+1;
          end;
          i:=concatener(tab,i,tab1,n1-i1,i1);
          concatener(tab,i,tab2,n2-i2,i2);
    end;
    {tri les n elts du tableau tab par la methode de tri par fusion}
    procedure trierfusion(var tab:vecteur;n:integer);
    begin
     
          if (n>1) then
          begin
          nf:=n div 2;
          ns:=n-nf;
          scinder(tab,n,tab1,nf,tab2);
          trierfusion(tab1,nf);
          trierfusion(tab2,ns);
          fusionner(tab,tab1,nf,tab2,ns);
          end;
    end;
    {debut du bloc principal}
    begin
         clrscr;
         gotoxy(20,12);
         write('Vous voulez un tableau de combien d''‚l‚ments:');
         readln(c);
         remplitab(tab,c);
         affichtab(tab,c);
         trierfusion(tab,c);
         affichtab(tab,c);
         readln;
    end.

  2. #2
    Membre à l'essai
    Inscrit en
    Juin 2006
    Messages
    14
    Détails du profil
    Informations forums :
    Inscription : Juin 2006
    Messages : 14
    Points : 10
    Points
    10
    Par défaut
    En fait c'est ça le problème. Ta procédure de tri tu l'as faite en procédure. Et tu l'appelles dans le programme principal. Le Pascal est limité quand il s'agit de faire de telles procédures surtout si, à l'intérieur, il y a une recursivité.
    J'ai déjà fait un programme (comme projet de fin d'année) : il fallait mettre l'algorithme de tri par fusion, quicksort et le tri par insertion.
    Je met les 3 en tant que procédures, je les appelle une par une; jusque la y a pas de problème de compilation. Malheureusement, il n'entre pas dans la procédure.
    Cependant, fais ton programme sans mettre l'algorithme de tri par fusion sous forme de procédure. Il doit faire partie du programme principal et ne dois pas etre appelé et là ça marchera.

  3. #3
    Responsable Pascal, Lazarus et Assembleur


    Avatar de Alcatîz
    Homme Profil pro
    Ressources humaines
    Inscrit en
    Mars 2003
    Messages
    7 930
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 57
    Localisation : Belgique

    Informations professionnelles :
    Activité : Ressources humaines
    Secteur : Service public

    Informations forums :
    Inscription : Mars 2003
    Messages : 7 930
    Points : 59 398
    Points
    59 398
    Billets dans le blog
    2
    Par défaut
    Bonjour !
    Citation Envoyé par jack_spyrow
    En fait c'est ça le problème. Ta procédure de tri tu l'as faite en procédure. Et tu l'appelles dans le programme principal. Le Pascal est limité quand il s'agit de faire de telles procédures surtout si, à l'intérieur, il y a une recursivité.
    Faire de la récursivité sans faire de sous-routine, c'est très fort.
    As-tu un exemple à proposer ?
    Règles du forum
    Cours et tutoriels Pascal, Delphi, Lazarus et Assembleur
    Avant de poser une question, consultez les FAQ Pascal, Delphi, Lazarus et Assembleur
    Mes tutoriels et sources Pascal

    Le problème en ce bas monde est que les imbéciles sont sûrs d'eux et fiers comme des coqs de basse cour, alors que les gens intelligents sont emplis de doute. [Bertrand Russell]
    La tolérance atteindra un tel niveau que les personnes intelligentes seront interdites de toute réflexion afin de ne pas offenser les imbéciles. [Fiodor Mikhaïlovitch Dostoïevski]

  4. #4
    Membre expérimenté
    Avatar de Juju_41
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Février 2003
    Messages
    974
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués

    Informations forums :
    Inscription : Février 2003
    Messages : 974
    Points : 1 557
    Points
    1 557
    Par défaut
    Citation Envoyé par jack_spyrow
    En fait c'est ça le problème. Ta procédure de tri tu l'as faite en procédure. Et tu l'appelles dans le programme principal. Le Pascal est limité quand il s'agit de faire de telles procédures surtout si, à l'intérieur, il y a une recursivité.
    Donc selon vous les procédures en Pascal existent mais il ne faut pas les utiliser sinon ça plante tout ???

    Citation Envoyé par jack_spyrow
    J'ai déjà fait un programme (comme projet de fin d'année) : il fallait mettre l'algorithme de tri par fusion, quicksort et le tri par insertion.
    Je met les 3 en tant que procédures, je les appelle une par une; jusque la y a pas de problème de compilation. Malheureusement, il n'entre pas dans la procédure.
    Permettez moi de mettre en doute le fait que l'erreur vienne du langage Pascal et non de votre programme

    Plus sérieusement, en ce qui concerne le problème de meoliver : les variables nf et ns (Integer) sont déclarées en tant que variables globales. Ces deux variables sont utilisées dans la procédure trierfusion, qui est appelée de manière récursive. Il font donc déclarer ces 2 variables en tant que variables locales à la procédure, sans quoi à chaque appel récursif, leurs nouvelles valeurs respectives seront perdues.

    Je peux détailler un peu plus ce problème si vous le désirez

    Sinon le programme ne fonctionne toujours pas même avec cette modification, il va donc falloir apprendre à debugger Je vous conseille de placer des writeln dans vos procedures pour vérifier le bon fonctionnement de celles-ci.

    Une dernière remarque : le fait d'avoir mis le même nom de variable pour vos paramètres de procédure et pour vos variables globales (tab, tab1 et tab2) n'est pas très conseillé. En effet ça porte à confusion ... sans mauvais jeu de mots.

    Bon courage
    Avant de poster, merci de consulter les règles du forum

  5. #5
    Membre à l'essai
    Inscrit en
    Juin 2006
    Messages
    14
    Détails du profil
    Informations forums :
    Inscription : Juin 2006
    Messages : 14
    Points : 10
    Points
    10
    Par défaut
    Citation Envoyé par Juju_41
    Donc selon vous les procédures en Pascal existent mais il ne faut pas les utiliser sinon ça plante tout ???
    je n'ai pas dit qu'il ne fallait pas utiliser les procedures en pascal..c^pendant pour ce cas specifique des tris ca ne marche pas...les procedure ne sont pas executés.c'est comme si le compilateur les considerait comme des commentaires....

    est ce que tu pourrais dettailler sur les debugger

  6. #6
    Membre expérimenté
    Avatar de Juju_41
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Février 2003
    Messages
    974
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués

    Informations forums :
    Inscription : Février 2003
    Messages : 974
    Points : 1 557
    Points
    1 557
    Par défaut
    Citation Envoyé par jack_spyrow
    je n'ai pas dit qu'il ne fallait pas utiliser les procedures en pascal..c^pendant pour ce cas specifique des tris ca ne marche pas...les procedure ne sont pas executés.c'est comme si le compilateur les considerait comme des commentaires....
    Avant de mettre en cause le compilateur, il faut remettre en question son code

    Citation Envoyé par jack_spyrow
    est ce que tu pourrais dettailler sur les debugger
    Je ne parlais pas d'un "debugger" particulier mais d'apprendre à débugger.

    Un exemple :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    var
      b: byte;
     
    procedure maprocedure;
    begin
      b := b + 5;
    end;
     
    begin
      b := 0;
      if (1.33 + 1 = 2.33) then maprocedure;
      writeln('Le résultat est b=',b);
    end.
    J'exécute ce petit programme qui ne me donne pas le résultat escompté : il m'affiche b=0 au lieu de b=5
    Avant de dire que pour le cas de mon programme, le Pascal ne gère pas les procédures, on peut "debugger" à la main comme ceci :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    var
      b: byte;
     
    procedure maprocedure;
    begin
      writeln('Maprocedure : entrée');
      b := b + 5;
      writeln('Maprocedure : sortie');
    end;
     
    begin
      b := 0;
      if (1.33 + 1 = 2.33) then
        begin
          writeln('Avant appel maprocedure');
          maprocedure;
          writeln('Après appel maprocedure');
        end;
      writeln('Le résultat est b=',b);
    end.
    En exécutant ceci, on se rend compte que le programme n'entre pas dans le bloc "begin end" du "if" (car aucune sortie écran avant "Le résultat est b=0"). Celà met donc en cause la condition, on peut donc enfin écrire :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    begin
      writeln(1.33+1 = 2.33);
    end.
    Ceci nous écrit "FALSE", le problème (un problème de précision dans le codage des nombres réels que je ne détaillerai pas) vient donc de là et non de la non gestion de procédures par le compilateur pour cet exemple.
    Avant de poster, merci de consulter les règles du forum

  7. #7
    Membre averti

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Décembre 2006
    Messages
    242
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Décembre 2006
    Messages : 242
    Points : 354
    Points
    354
    Par défaut
    Tout a fait daccord.. Les procédures marchent très bien en Pascal !
    Je vous propose ici une version du tri fusion qui pourra peutetre inspirer meoliver a régler son problème.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
     
    PROCEDURE tri_fusion(var M:tab;d,f:integer);
       VAR mil:integer;
     
       PROCEDURE fusionner(var M:tab;d,mil,f:integer);
        VAR P:tab;
            i,j,k,l:integer;
        BEGIN
         i:=d;
         j:=mil+1;
         k:=d;
         while (i<=mil) and (j<=f) do
          begin
           if M[i]<M[j] then begin
                              P[k]:=M[i];
                              i:=i+1;
                             end
                        else begin
                              P[k]:=M[j];
                              j:=j+1;
                             end;
           k:=k+1;
          end;
     
         if (i>mil) then for l:=j to f do
                          begin
                           P[k]:=M[l];
                           k:=k+1;
                          end
                    else for l:=i to mil do
                          begin
                           P[k]:=M[l];
                           k:=k+1;
                          end;
         for l:=d to f do
          M[l]:=P[l];
        END;
     
     
     
     
       BEGIN
        if (d<f) then begin
                       mil:=(d+f) div 2;
                       tri_fusion(M,d,mil);
                       tri_fusion(M,mil+1,f);
                       fusionner(M,d,mil,f);
                      end;
     
       END;

  8. #8
    Candidat au Club
    Inscrit en
    Octobre 2009
    Messages
    1
    Détails du profil
    Informations forums :
    Inscription : Octobre 2009
    Messages : 1
    Points : 3
    Points
    3
    Par défaut Tri par fusion
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    program triefusion;
    uses wincrt;
    type
    tab = array[1..5] of integer;
    var
    t:tab;
    n :byte;
     
    {*******************}
    procedure saisie(var t:tab ; n:integer);
    var
    i:integer;
    begin
         repeat
               readln(n);
         until n in [2..5];
         for i:=1 to n do
         begin
              writeln('T[',i,']');
              readln(t[i]);
         end;
     
    end;
     
    {*******************}
    procedure affiche(t:tab ; n:integer);
    var
    i:integer;
    begin
     
         for i:=1 to n do
         begin
              writeln('T[',i,']');
              write(t[i]:5);
         end;
     
    end;
     
    {*******************}
     
    procedure fusion(var t:tab ; d,m,f:integer);
    var
    k,j,aux:integer;
    begin
         for k:=d to m do
         begin
              j:=m-1;
              aux := T[m];
         end;
     
         while (T[j]>aux) and (j>=1) do
         begin
              T[j+1] := T[j];
              j:=j-1;
         end;
         T[j+1]:= aux;
         end;
    {*******************}
    Procedure triefus(d,f:integer ; var t:tab);
    var
    m:byte;
              begin
                   m:=((f-d) div 2 )+d;
                   triefus(d,m,t);
                   triefus(m+1,f,t);
                   fusion(t,d,m,f); {le decoupage}
              end;
     
     
    {PP}
    begin
    saisie(t,n);
    affiche(t,n);
    triefus(1,n,t);
    affiche(t,n);
    end.

  9. #9
    Expert confirmé

    Inscrit en
    Août 2006
    Messages
    3 941
    Détails du profil
    Informations forums :
    Inscription : Août 2006
    Messages : 3 941
    Points : 5 652
    Points
    5 652
    Par défaut
    Sia,

    1) Ta procédure saisie ne peut pas mettre n global à jour (tu le passes par valeur !!)

    Il faudrait d'ailleurs la couper en 2 :
    - lecture de n
    - lecture des n données du tableau

    2) tes affichages sont bizarres :
    exemple
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    procedure affiche(t:tab ; n:integer);
    var
    i:integer;
    begin
     
         for i:=1 to n do
         begin
              writeln('T[',i,']');
              write(t[i]:5);
         end;
     
    end;
    va donner quelque chose comme ça (avec n = 2)
    Mais comme ton programme ne peut pas fonctionner à cause de 1), ce n'est pas le plus grave (mais c'est quand même à voir).

    Bref, tu postes un programme qui ne fonctionne pas, et n'a donc pas été testé.

    Du coup, je n'ai même pas regardé tes procédures de tri.
    Si les cons volaient, il ferait nuit à midi.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Tri par fusion
    Par oussamadag dans le forum Pascal
    Réponses: 4
    Dernier message: 17/01/2010, 09h54
  2. Tri par fusion
    Par marsilla02 dans le forum Pascal
    Réponses: 2
    Dernier message: 06/02/2008, 20h38
  3. Réponses: 9
    Dernier message: 12/09/2007, 13h56
  4. Tri par fusion
    Par ousunas dans le forum Langage
    Réponses: 3
    Dernier message: 25/02/2006, 03h52
  5. Tri par fusion d'un tableau
    Par Mailgifson dans le forum C
    Réponses: 5
    Dernier message: 12/12/2002, 15h53

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo