Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1291 connectés 

  FORUM HardWare.fr
  Programmation
  C++

  trie par fusion

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

trie par fusion

n°247346
weblook$
happy face
Posté le 18-11-2002 à 01:31:58  profilanswer
 

j'essaye de realiser le trie par fusion mais ce code affiche des valeurs bidons!
pourquoi tout ma pourtant l'air correct?
 

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. #define TAILLE 20
  7. void TriFusion(int* t ,int deb,int fin);
  8. void Fusion(int* t,int deb,int fin);
  9. int* RemplirTab(int max);
  10. void print(int* tab)
  11. { int i; for(i=0;i<TAILLE;i++) printf("%d ",tab[i]); }
  13. main()
  14. {
  15.   int* tab;
  16.   int i=0;
  17.  
  18.   tab=RemplirTab(30);
  19.  
  20.   TriFusion(tab,0,TAILLE);
  21.  
  22.   print(tab);
  24. }
  26. void Fusion(int* tab, int deb, int fin)
  27. {
  28.   int milieu=(deb+fin)/2;
  29.   int j,i=0,i1=deb,i2=milieu+1;
  30.   int temp[50];
  31.  
  33.   while(i1<milieu && i2<fin)
  34.     {
  35.       if(tab[i1] < tab[i2])
  36. {
  37.   temp[i]=tab[i1];
  38.   i1++;
  39. }
  40.       else
  41. {
  42.   temp[i]=tab[i2];
  43.   i2++;
  44. }
  45.       i++;
  46.     }
  47.  
  48.   if(i1 < milieu)
  49.     {
  50.       for(j=i1;j<milieu;j++,i++)     
  51.   temp[i]=tab[j];
  52.     }
  54.   else if(i2 < fin)
  55.     {
  56.       for(j=i2;j<fin;j++,i++)
  57.   temp[i]=tab[j];
  58.     }
  60.   for(i=deb;i<fin;i++)
  61.     tab[i]=temp[i];
  63. }
  65. void TriFusion(int* tab, int deb, int fin)
  66. {
  67.   int milieu;
  69.   if(deb<fin)
  70.     {
  71.       milieu=(deb+fin)/2;
  73.       TriFusion(tab,deb,milieu);
  74.       TriFusion(tab,milieu+1,fin);
  75.       Fusion(tab,deb,fin);
  76.     }
  77. }
  79. int* RemplirTab(int max)
  80. {
  81.   int* tab;
  82.   int i;
  84.   tab=(int*)malloc(TAILLE*sizeof(int));
  86.   srand((unsigned)time(NULL));
  87.  
  88.   for(i=0;i<TAILLE;i++)
  89.       tab[i]=rand()%max;   
  91.   return tab;
  92. }


 
les valeurs affichées sont du style '134554347 ... ...'

mood
Publicité
Posté le 18-11-2002 à 01:31:58  profilanswer
 

n°247441
blackgodde​ss
vive le troll !
Posté le 18-11-2002 à 10:30:28  profilanswer
 

les valeurs tordus de ce genre sont en général due à une erreur d'indirection ou d'allocation avec les pointeurs. (g lu le code et j'y comprends rien, mais g souvent des nombres pareils et c du à ca)


---------------
-( BlackGoddess )-
n°247470
barbarella
Posté le 18-11-2002 à 11:07:25  profilanswer
 

salut,
 
j'ai pas la reponse a ta question, par contre prend l'habitude de remplacer tes :
 
(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.
 
Effectivement une division prend de 10 a 30 cycles au microprocesseur et un décalage a droite (qui l'équivalent d'une division par 2) de 1 a 2 cycles (plus les chiffres exactes en tete, mais les ordres de grandeur sont bons)

n°247496
kadreg
profil: Utilisateur
Posté le 18-11-2002 à 11:50:40  profilanswer
 

barbarella a écrit a écrit :

par contre prend l'habitude de remplacer tes :
 
(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.




 
Oui, prend l'habitude de faire du code incompréhensible, déjà que le C, c'est facilement le bordel, rajoute en encore.


---------------
brisez les rêves des gens, il en restera toujours quelque chose...  -- laissez moi troller sur discu !
n°247502
barbarella
Posté le 18-11-2002 à 11:56:12  profilanswer
 

kadreg a écrit a écrit :

 
 
Oui, prend l'habitude de faire du code incompréhensible, déjà que le C, c'est facilement le bordel, rajoute en encore.




 
:lol:

n°247544
weblook$
happy face
Posté le 18-11-2002 à 12:29:39  profilanswer
 

:( snif! toujours pas de réponse à mon pbm

n°248034
Ace17
Posté le 18-11-2002 à 22:02:42  profilanswer
 

barbarella a écrit a écrit :

salut,
j'ai pas la reponse a ta question, par contre prend l'habitude de remplacer tes :
(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.




 
Il faut surtout prendre l'habitude d'optimiser a la fin! Voire laisser soin au compilo de faire ca tout seul.

n°248036
Ace17
Posté le 18-11-2002 à 22:03:31  profilanswer
 

weblook$ a écrit a écrit :

:( snif! toujours pas de réponse à mon pbm  




Je veux bien jeter un oeil a ton code, mais pourrais tu expliquer en quoi ca consiste le tri par fusion? On m'a déja expliqué mais je ne me souviens plus.

n°248059
fabsk
Posté le 18-11-2002 à 22:33:37  profilanswer
 

barbarella a écrit a écrit :

 
(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.




 
Ca c'était valable il y a quelques années. Les compilateurs modernes savent très bien détecter ces genres de cas. D'ailleurs on peut vérifier ca en activant la sortie assembleur de la compilation (sous Visual C++ c'est Project Settings / C++ / Preprocessor / Listing files je crois).
 
Si tu veux optimiser, apprends a connaitre ton compilateur, Luke !

n°248069
barbarella
Posté le 18-11-2002 à 23:06:50  profilanswer
 

Ace17 a écrit a écrit :

 
 
Il faut surtout prendre l'habitude d'optimiser a la fin! Voire laisser soin au compilo de faire ca tout seul.




 
c'est en rien une optimisation, faur arreter cinq minutes. c'est un opérateur.  
 
Faut pas confondre optimisation et utilisation d'operateur.  

mood
Publicité
Posté le 18-11-2002 à 23:06:50  profilanswer
 

n°248072
barbarella
Posté le 18-11-2002 à 23:08:31  profilanswer
 

fabsk a écrit a écrit :

 
 
Ca c'était valable il y a quelques années. Les compilateurs modernes savent très bien détecter ces genres de cas. D'ailleurs on peut vérifier ca en activant la sortie assembleur de la compilation (sous Visual C++ c'est Project Settings / C++ / Preprocessor / Listing files je crois).
 
Si tu veux optimiser, apprends a connaitre ton compilateur, Luke !




 
au lieu de donner des leçons, tu devrais essayé de sortir dans le vaste monde, et te rendre compte qu'il n'y pas que VC :D
 
Et c'est quoi cette aggressivité, j'ai donné un conseil, j'ai rien ordonné du tout, alors venez pas le prendre de haut.

n°248084
kadreg
profil: Utilisateur
Posté le 18-11-2002 à 23:41:16  profilanswer
 

barbarella a écrit a écrit :

 
il n'y pas que VC :D




 
J'ai essayé sur le gcc que j'ai au bureau (2.7.2, donc putoujeune), il fait aussi l'optimisation lui-même.


---------------
brisez les rêves des gens, il en restera toujours quelque chose...  -- laissez moi troller sur discu !
n°248132
Kristoph
Posté le 19-11-2002 à 00:11:06  profilanswer
 

Juste une remarque, fais gaffe à tes intervalles. Le standard en C c'est que la borne initialle est incluse mais pas la borne de fin. Donc dans ce cas TriFusion deviens :
 

Code :
  1. void TriFusion(int* tab, int deb, int fin)
  2. {
  3. int milieu;
  5. if(deb<fin-1)
  6.    {
  7.      milieu=(deb+fin)/2;
  9.      TriFusion(tab,deb,milieu);
  10.      TriFusion(tab,milieu,fin);
  11.      Fusion(tab,deb,fin);
  12.    }
  13. }

n°248148
weblook$
happy face
Posté le 19-11-2002 à 00:52:52  profilanswer
 

bon j'ai pas réussi à trouver l'erreur, mais je suis à peu prés certain qu'un problème d'adressage est en cause.
 
sinon j'ai réussi à faire ce que je voulais en modifiant le code de     Fusion()
 
Pour les intéréssés:

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  5. typedef char BOOL;
  6. enum{faux,vrai};
  8. int TAILLE;
  11. void TriFusion(int* t ,int deb,int fin);
  12. void Fusion(int* t,int deb,int fin);
  13. int* RemplirTab(int max);
  14. void Permut(int*,int,int);
  15. void print(int* tab,int m,int s,char* mes);
  17. main(int argc,char **argv)
  18. { 
  19.   if(argc>1)    TAILLE=atoi(argv[1]);
  20.   else      {    exit(0);              }
  21.    
  22.   tab=RemplirTab(30);
  24.   print(tab,0,TAILLE-1,"Tab avant traitement: " );
  26.   TriFusion(tab,0,TAILLE-1);
  28.   print(tab,0,TAILLE-1,"Tab aprés traitement: " );
  30. }
  32. void Fusion(int* tab,int deb,int fin)
  33. {
  34.   BOOL continuer;
  35.   int mid=(deb+fin)/2;
  36.   int j,i=mid+1;
  38.   while(i<=fin)
  39.   {
  40.       j=0;
  41.       continuer=vrai;
  42.       while(j<i && continuer)
  43.       {
  44. if( tab[i-j-1] > tab[i-j] )
  45.   Permut(tab,i-j-1,i-j);
  46. else
  47.   continuer=faux;
  48. j++;
  49.       }
  50.       i++;
  51.   }
  52. }
  54. void TriFusion(int* tab, int deb, int fin)
  55. {
  56.   int milieu;
  57.   if(deb<fin)
  58.     {
  59.        milieu=(deb+fin)/2;
  60.      
  61.        if(milieu>deb)
  62.  TriFusion(tab,deb,milieu);
  63.      
  64.        if(milieu+1<fin)
  65.  TriFusion(tab,milieu+1,fin);
  66.      
  67.        Fusion(tab,deb,fin); 
  68.     }
  69. }
  71. void Permut(int* tab,int a,int b)
  72. {
  73.   int temp;
  74.   temp=tab[a];
  75.   tab[a]=tab[b];
  76.   tab[b]=temp;
  77. }
  79. int* RemplirTab(int max)
  80. {
  81.   int* tab;
  82.   int i;
  84.   tab=(int*)malloc(TAILLE*sizeof(int));
  86.   srand((unsigned)time(NULL));
  87.  
  88.   for(i=0;i<TAILLE;i++)
  89.       tab[i]=rand()%(max+1);   
  91.   return tab;
  92. }
  94. void print(int* tab,int m,int s,char* mes)
  95. {
  96.   int i;
  97.   if(strlen(mes)>0)
  98.     printf("%s",mes);
  100.   for(i=m;i<=s;i++)
  101.     printf("%d ",tab[i]);
  102.  
  103.   putchar('\n');
  105. }


Message édité par weblook$ le 19-11-2002 à 00:54:48
n°248163
Angel_Doog​las
Le dernier des humains
Posté le 19-11-2002 à 04:16:37  profilanswer
 

L'erreur ne viendrait pas du fait que comme il ne respecte pas l'intervalle de son tableau (il faut mettre TriFusion(tab,0,TAILLE-1) dans ton main), il va dans trifusion chercher des valeurs dans des zones memoires bidon et donc du coup va les rapatrier dans son tableau tout beau?


Message édité par Angel_Dooglas le 19-11-2002 à 04:22:12
n°248164
Musaran
Cerveaulté
Posté le 19-11-2002 à 04:17:59  profilanswer
 

Code :
  1. TriFusion(tab,0,TAILLE); //très probablement TAILLE-1
  3. int temp[50]; //je m'étonne d'une taille fixe...
  5. //ceci...
  6. while(i1<milieu && i2<fin)
  7. {
  8. if(tab[i1] < tab[i2])
  9. {
  10.  temp[i]=tab[i1];
  11.  i1++;
  12. }
  13. else
  14. {
  15.  temp[i]=tab[i2];
  16.  i2++;
  17. }
  18. i++;
  19. }
  20. //...peut s'écrire comme ça.
  21. for(i= 0 ; i1<milieu && i2<fin ; ++i){
  22. int* pi= (tab[i1] < tab[i2]) ? &i1 : &i2 ;
  23. temp[i]= tab[*pi];
  24. (*pi)++;
  25. }


 
J'ai eu la flemme de vérifier l'alorithme... désolé.
 

Citation :

(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.

A condition que ce soient (1)des entiers (2)positifs représentés en (3)base 2 en (4)numération arabe.
 
Il faut coder l'opération qu'on veut faire, et laisser au compilateur ce genre d'optimisation.


---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone
n°248178
Tetedeienc​h
Head Of God
Posté le 19-11-2002 à 06:58:33  profilanswer
 

barbarella a écrit a écrit :

salut,
 
j'ai pas la reponse a ta question, par contre prend l'habitude de remplacer tes :
 
(a+b)/2 par (a+b) >> 1 si a et b sont des entiers.
 
Effectivement une division prend de 10 a 30 cycles au microprocesseur et un décalage a droite (qui l'équivalent d'une division par 2) de 1 a 2 cycles (plus les chiffres exactes en tete, mais les ordres de grandeur sont bons)  




 
Le compilateur fait ca vraiment tres bien tout seul tu sais.
 
Remplacer /2 par >>1 , n'importe quel compilo bidon peux le faire.
 
Par contre, si tu veux produire du code incomprehensible, oui, fais comme ca.
 


---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !
n°248200
Carbon_14
Posté le 19-11-2002 à 09:44:00  profilanswer
 

Ai déja essayé mesurer différences de rapidité avec BC 3 sous Windows 3.11 sur mon 486/100MHz, car on voit mieux au chrono :D.
 
Multipl/divis par 2^n ou décalages, pas vu la moindre différence de rapidité. J'ai donc opté pour lecture facile.

n°250290
weblook$
happy face
Posté le 20-11-2002 à 23:56:28  profilanswer
 

ouf enfin c'est trouvé  :)
c'était tout simplement des erreurs d'indice dans la fonction Fusion :sarcastic:


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C++

  trie par fusion

 

Sujets relatifs
[Page Web] Fusion de pages en une seule.Récupérer l'adresse IP du client [Cold Fusion]
[Access] Fusion vers Excel?[Access] Fusion Etat vers Excel....
trie et affichage[ACCESS] Fusion Champ formulaire vers word
problème pour faire une fusion/publipostage en code vb[Pascal] Tri fusion
Cold Fusion et Easyphp 1.6[URGENT POUR LE BTS] Cold Fusion et Mysql - Il faut que ça marche
Plus de sujets relatifs à : trie par fusion

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.112 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR