Probleme de polynomes

Probleme de polynomes - C - Programmation

Marsh Posté le 10-01-2004 à 17:01:36    

Code :
  1. #include <stdio.h>                                                   
  2. #include <stdlib.h>                                                 
  3.                                                                      
  4. typedef struct MONOME *pmonome;                                   
  5. typedef struct MONOME { float coeff;
  6.                         int exp;       
  7.                         pmonome suivant;                           
  8.                        }monome;                                     
  9. typedef struct MONOME *poly;                                       
  10.                                                                      
  11. typedef poly *ppoly;                                               
  12.                                                                      
  13.                                                                      
  14.                                                                      
  15. ppoly creerpoly()                                                 
  16.                                                                      
  17. {  ppoly ptr;                                                       
  18.    ptr = (ppoly)malloc(sizeof(poly));                             
  19.                                                                      
  20.    *ptr = NULL;                                                     
  21.    return ptr;                                                       
  22. }                                                                   
  23.                                                                      
  24.                                                                      
  25. pmonome creermonome(float a, int expo)                                         
  26. {                                                                   
  27.    pmonome e;                                                       
  28.    e = (pmonome)malloc(sizeof(monome));                           
  29.    e->coeff = a;                                                   
  30.    e->exp = expo;
  31.    e->suivant = NULL;                                               
  32.    return e;                                                         
  33. }                                                                   
  37.                                                                      
  38. int estnul(ppoly ptr)                                           
  39.                                                                      
  40. { return ( *ptr == NULL);                                           
  41. }                                                                   
  42.                                                                      
  43.                                                                      
  44.                                                                  
  45.                                                                    
  46. void inserercroissant(pmonome pe, ppoly ptr)             
  47. { poly l = *ptr;                                                   
  48.                                                                      
  49.        if(estnul(ptr))
  50.       *ptr = pe;
  51.    else{  
  52.               while((l->suivant != NULL) && (l->exp < pe->exp))     
  53.                     l = l->suivant;                                 
  54.              
  55.    
  56.     if(l->suivant == NULL)
  57.        l->suivant = pe;
  59.     else{
  60.    
  61.          if(l->exp == pe->exp)
  62.             l->coeff = l->coeff + pe->coeff;
  63.                                                         
  64.                    else                                         
  65.                      {
  66.        pe->suivant = l->suivant;                                                 
  67.                        l->suivant = pe;                                 
  68.                      }
  69.       }
  70.      }                                                       
  71. }                                                                           
  72.                                                                      
  73.                                                                      
  74.                                                                      
  75.                                                                    
  76.                                                                      
  77. void ecrire_poly_rec(ppoly ptr)                                   
  78. { poly l;                                                           
  79.                                                                      
  80.   if (estnul(ptr))                                               
  81.      printf("\n" );                               
  82.   else{                                                             
  83.         l = *ptr;                                                   
  84.         printf("%0.1fX^%d", l->coeff, l->exp);
  85.  if (l->suivant != NULL) printf("  +  " );                               
  86.         ecrire_poly_rec(&(l->suivant));                             
  87.       }                                                             
  88. }       
  91. int mult(int mulv, int v)
  92. {  int a=v;
  94. while(mulv > 1)
  95.        a = a+v;
  96. return a;
  97. }
  101. float evaluer_poly(poly p, int v)
  102. {float s;
  103. int mulv=0;
  105. if (p->suivant == NULL)                                  /* Ne marche pas */
  106.      s = p->coeff;
  107. else
  108.     {  mulv = p->suivant->exp - p->exp; 
  109.  
  110.    s = p->coeff + mult(mulv, v) * evaluer_poly(p->suivant, v);
  111. }
  114. return s;
  115. }  
  119.                                                            
  120.                                                                      
  121.                                                                      
  122. void supprimer_poly(ppoly ptr)                                     
  123. { poly q, p=*ptr;                                                   
  124.                                                                      
  125.   if(estnul(ptr))                                                 
  126.      { free(ptr);                                                   
  127.        return;                                                       
  128.       }                                                             
  129.                                                                      
  130.       q = p->suivant;                                               
  131.    while( q != NULL)                                                 
  132.         { free(p);                                                   
  133.           p = q;                                                     
  134.           q = q->suivant;                                           
  135.         }                                                           
  136.         free(p);                                                     
  137.         free(ptr);                                                   
  138.         return;                                                     
  139. }                                                                   
  140.                                                                      
  141.                                                                      
  142.                                                                      
  143.                                                                      
  144.                                                                      
  145.                                                                      
  146. int main()                                                           
  147. { ppoly ptr;                                                       
  148.   pmonome px;
  149.   float c;                                                   
  150.   int e;                                                         
  151.                                                                      
  152.     ptr = creerpoly();                                             
  153.     printf("\nCreez votre polynome : (-1 pour l exposant pour stopper) :\nCoeff? : " );                                                 
  154.     scanf("%f", &c);
  155. printf("\nExposant ? : " );
  156. scanf("%d", &e);                                           
  157.     while (e != -1)                                             
  158.           {                                                         
  159.           px = creermonome(c, e);                                 
  160.           inserercroissant(px, ptr);
  161.    printf("\nCoeff ? : " );                                   
  162.           scanf("%f", &c);
  163.       printf("\nExposant ? : " );
  164.       scanf("%d", &e);                                       
  165.           }                                                         
  166.                                              
  167.  ecrire_poly_rec(ptr);                                             
  168.                                                                  
  169.      printf("\nPour quelle valeur evaluer le polynome ? : " );
  170.  scanf("%d", &e);
  171.  printf("\nResultat de l evaluation : %f\n", evaluer_poly(*ptr, e));                                             
  172.                                                                      
  173.    
  174.                                                                      
  175.     supprimer_poly(ptr);                                             
  176.     printf("\n\nDesallocation memoire effectuee...\n\n" );           
  177.                                                                      
  178.   return 0;                                                         
  179.                                                                      
  180. }


 
Salut tlm
J'ai écris ces algos de manipulation de polynomes mais la fonction evaluer_poly ne marche pas :/ Vous pourriez m'aider svp ?
Ps : J'ai du faire des bêtises dans le reste du code, alors si vous avez des remarques... :)


---------------
- mon feed-back
Reply

Marsh Posté le 10-01-2004 à 17:01:36   

Reply

Marsh Posté le 10-01-2004 à 18:23:10    

déboggage à distance j'écoute ?
Veuillez faire une trace en utilisant les points d'arrêts.  
 
Dire qu'une fonction "ne marche pas" veut dire quoi exactement ?

Reply

Marsh Posté le 10-01-2004 à 18:48:34    

!! je cromprends pas trop ta fonction evaluer_poly
elle me semble un peu compliquée.. pas besoin de recursivité selon moi, sauf si c la consigne
en ittératif, tu t'en sortiras mieux je pense

Reply

Marsh Posté le 10-01-2004 à 18:54:07    

Citation :


float evaluer_poly(poly p, int v )
{
     float s=0;
     if (p!=NULL)
     {
 while(p!=NULL)
 {
  s=s+(p->coeff)*pow(v,p->exp);
  p=p->suiv;
 }
 return s;
      }
      else
        return 0;
}


 
voila, je pense que c plus simple, en oubliant pas d'inclure math.h pour la fonction pow

Reply

Marsh Posté le 10-01-2004 à 19:46:47    

Code :
  1. int mult(int mulv, int v)
  2.   {  int a=v;
  3.    
  4.      while(mulv > 1)
  5.            a = a+v;
  6.     return a;
  7.   }


 
la deja tu as une boucle infinie des que mulv > 1...
 
A+,  
   


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 10-01-2004 à 19:57:42    

         printf("\nCoeff ? : " );                                      
                scanf("%f", &c);
 
->  
 
          printf("\nCoeff ? : " );            
          fflush(stdout);                          
                scanf("%f", &c);

Reply

Marsh Posté le 10-01-2004 à 19:59:32    

taz a écrit :

         printf("\nCoeff ? : " );                                      
                scanf("%f", &c);
 
->  
 
          printf("\nCoeff ? : " );            
          fflush(stdout);                          
                scanf("%f", &c);


 
je veux pas t'embeter  
mais c pas fflush(stdin) ?

Reply

Marsh Posté le 10-01-2004 à 20:00:37    

non

Reply

Marsh Posté le 10-01-2004 à 20:01:30    

ah
pourtant, on veut vider le tampon du periph d'entrée, pas de sortie..

Reply

Marsh Posté le 10-01-2004 à 20:02:48    

captainneuneu a écrit :

ah
pourtant, on veut vider le tampon du periph d'entrée, pas de sortie..

c'est l'inverse

Reply

Marsh Posté le 10-01-2004 à 20:02:48   

Reply

Marsh Posté le 10-01-2004 à 20:10:10    

je lis dans mon livre :
"la fonction fflush fait disparaitre les informations presentes dans un flot, y compris le flot d'entree standard[...]"
plus loin, dans le listing :
"fflush(stdin);
scanf("%s",name)"
 
on m'a toujours dit qu'il fallait mettre fflush(stdin) avant tout scanf
 
maintenant, j'aimerais que tu m'explique, sans t'emporter, a koi sert fflush(stdout) et quel est son interet dans ce cas

Reply

Marsh Posté le 10-01-2004 à 20:10:55    

ton bouquin est mauvais, tes enseignements sont faux

Reply

Marsh Posté le 10-01-2004 à 20:12:59    

gilou > j'ai des palpitations et une douleur dans le bras gauche

Reply

Marsh Posté le 10-01-2004 à 20:14:57    

taz a écrit :

ton bouquin est mauvais, tes enseignements sont faux


 
premiere reponse de google :
 
http://iihm.imag.fr/dubois/fr/Ense [...] _CCI/TD3.c

Reply

Marsh Posté le 10-01-2004 à 20:17:00    

captainneuneu a écrit :


 
premiere reponse de google :
 
http://iihm.imag.fr/dubois/fr/Ense [...] _CCI/TD3.c

joue pas au plus malin, je sais très bien de quoi je parle et j'ai déjà rabattu les oreilles à tout le monde ici à ce propos. Procure toi un livre de C (et un vrai). Et je suis payé pour faire les recherches sur le forum à ta place

Reply

Marsh Posté le 10-01-2004 à 20:18:01    

hum
autre réponse de google :
 

Citation :

14.4 Pourquoi ne jamais faire fflush(stdin) ?
La fonction fflush() a un comportement défini uniquement sur les flux ouverts en écriture tels que stdout. Il est possible que sur votre système, appliquer cette fonction à stdin soit possible, mais c'est alors une extension non standard. Le comportement est indéterminé, et imprévisible.  
Il faut bien comprendre que stdin n'est pas forcément relié au clavier, mais peut être rattaché à un réseau, un fichier, etc.  
 


 
je reste perplexe, et ca remet en cause tout ce que g appris
je comprends plus rien la

Reply

Marsh Posté le 10-01-2004 à 20:19:04    

taz a écrit :

joue pas au plus malin, je sais très bien de quoi je parle et j'ai déjà rabattu les oreilles à tout le monde ici à ce propos. Procure toi un livre de C (et un vrai). Et je suis payé pour faire les recherches sur le forum à ta place


 
conseille moi un bon livre dans ce cas..
j'ai le Langage C collection Le Programmeur aux édtions Campus Press

Reply

Marsh Posté le 10-01-2004 à 20:19:26    

parce que c'est la première fois que tu vois la lumière

Reply

Marsh Posté le 10-01-2004 à 20:19:49    

captainneuneu a écrit :


 
conseille moi un bon livre dans ce cas..
j'ai le Langage C collection Le Programmeur aux édtions Campus Press

ben le K&R

Reply

Marsh Posté le 10-01-2004 à 20:23:00    

taz a écrit :

ben le K&R


 
merci :jap:

Reply

Marsh Posté le 10-01-2004 à 22:11:16    

taz a écrit :

gilou > j'ai des palpitations et une douleur dans le bras gauche


Moi aussi, en lisant le code C, j'ai eu un peu d'urticaire... :D
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 10-01-2004 à 22:27:26    

Code :
  1. void inserercroissant(pmonome pe, ppoly ptr)               
  2. {
  3.   poly l = *ptr;                                                     
  5.   if (estnul(ptr))
  6.     *ptr = pe;
  7.   else
  8.     {   
  9.       while((l->suivant != NULL) && (l->exp < pe->exp))       
  10. l = l->suivant;                                   
  12.       if (l->suivant == NULL)
  13.        // Bon mes modifs sont le statement qui suit
  14. {
  15.   if (l->exp == pe->exp)
  16.     l->coeff = l->coeff + pe->coeff;
  17.   else
  18.     l->suivant = pe;
  19. }
  20.       else
  21. { 
  22.   if(l->exp == pe->exp)
  23.     l->coeff = l->coeff + pe->coeff;
  24.   else                                           
  25.     { 
  26.       pe->suivant = l->suivant;                                                 
  27.       l->suivant = pe;                                   
  28.     } 
  29. } 
  30.     }                                                         
  31. }

 
 
sinon tu as des coeffs de meme rang qui se suivent sans etre regroupes.
 
A+,


Message édité par gilou le 10-01-2004 à 22:36:16

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 10-01-2004 à 23:03:25    

Et pour ta fonction d'eval, si tu expliquais l'algo que tu veux appliquer...
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 10-01-2004 à 23:57:49    

gilou a écrit :

Code :
  1. void inserercroissant(pmonome pe, ppoly ptr)               
  2. {
  3.   poly l = *ptr;                                                     
  5.   if (estnul(ptr))
  6.     *ptr = pe;
  7.   else
  8.     {   
  9.       while((l->suivant != NULL) && (l->exp < pe->exp))       
  10. l = l->suivant;                                   
  12.       if (l->suivant == NULL)
  13.        // Bon mes modifs sont le statement qui suit
  14. {
  15.   if (l->exp == pe->exp)
  16.     l->coeff = l->coeff + pe->coeff;
  17.   else
  18.     l->suivant = pe;
  19. }
  20.       else
  21. { 
  22.   if(l->exp == pe->exp)
  23.     l->coeff = l->coeff + pe->coeff;
  24.   else                                           
  25.     { 
  26.       pe->suivant = l->suivant;                                                 
  27.       l->suivant = pe;                                   
  28.     } 
  29. } 
  30.     }                                                         
  31. }

 
 
sinon tu as des coeffs de meme rang qui se suivent sans etre regroupes.
 
A+,


 
Ah oui t'as raison ca testait pas pour le dernier monome si les exposants étaient égaux, j'ai corrigé :)


---------------
- mon feed-back
Reply

Marsh Posté le 10-01-2004 à 23:58:48    

captainneuneu a écrit :

!! je cromprends pas trop ta fonction evaluer_poly
elle me semble un peu compliquée.. pas besoin de recursivité selon moi, sauf si c la consigne
en ittératif, tu t'en sortiras mieux je pense


 
Oui évidemment la consigne était de l'écrire en récursivité :crazy:
Sinon en itératif c simple.


---------------
- mon feed-back
Reply

Marsh Posté le 10-01-2004 à 23:59:42    

gilou a écrit :

Code :
  1. int mult(int mulv, int v)
  2.   {  int a=v;
  3.    
  4.      while(mulv > 1)
  5.            a = a+v;
  6.     return a;
  7.   }


 
la deja tu as une boucle infinie des que mulv > 1...
 
A+,  
   
 


 
ah ben voila jcrois que c ca lol jdevais pas etre très réveillé à ce moment là :p
Jvais tester


---------------
- mon feed-back
Reply

Marsh Posté le 11-01-2004 à 00:09:46    

gilou a écrit :

Code :
  1. int mult(int mulv, int v)
  2.   {  int a=v;
  3.    
  4.      while(mulv > 1)
  5.            a = a+v;
  6.     return a;
  7.   }


 
la deja tu as une boucle infinie des que mulv > 1...
 
A+,  
   
 


 
Mouais j'ai rajouté la condition d'arrêt mulv-- à la fin de la boucle mais l'algo ne marche que lorsque tous les monomes du polynome ont des degrés qui se suivent (par ex. x^0 + x^1 + x^2) et il affiche un résultat faux pour par exemple x^0 + x^2)  
 
Pour le fonctionnement, c'est repris sur la représentation d'Horner. Mais j'ai rajouté l'histoire du mulv pask mes monomes peuvent ne pas etre d'exposant qui se suivent, donc je multiplie ma valeur par la différence de l'exposant du monome n avec celui du monome n-1
Fin ché pas si c bien expliqué, jreviendrai demain pour faire un truc plus clair bnone nuit :)


---------------
- mon feed-back
Reply

Marsh Posté le 11-01-2004 à 00:24:18    

captainneuneu a écrit :


voila, je pense que c plus simple, en oubliant pas d'inclure math.h pour la fonction pow


 
Non c'est en récursif qu'il faut le faire (Horner)


---------------
- mon feed-back
Reply

Marsh Posté le 11-01-2004 à 03:44:20    

Bon alors:
1) Horner c'est pas du recursif, mais de l'iteratif. Voir par exemple ce lien http://www.umh.ac.be/math/an/courses/Horner.pdf qui est tres tres clair
2) Horner se fait en triant le polynome par ordre decroissant
 
donc

Code :
  1. void insererdecroissant(pmonome pe, ppoly ptr)               
  2. { poly l = *ptr;                                                     
  4. if (estnul(ptr))
  5.    *ptr = pe;
  6. else{   // on inverse l' ordre de comparaison donc  
  7.    while((l->suivant != NULL) && (l->exp > pe->exp))       
  8.      l = l->suivant;


 
3) Pour horner, ta fonction int mult(int mulv, int v) doit clairement calculer la puissance mulv-ienne de v
 

Code :
  1. int mult(int mulv, int v)
  2. {  int a=v;
  4. while(mulv > 1)
  5. {
  6.   // donc pas une addition
  7.    a = a*v;
  8.    mulv--;
  9. }
  10. return a;
  11. }


 
 
4) et c' est donc un algo iteratif ecrit a la va vite comme suit:

Code :
  1. float evaluer_poly(poly p, int v)
  2. {
  3.   float s= p->coeff;
  4.   int mulv;
  6.   while(p->suivant)
  7.   { // inverse car l' ordre est decroissant maintenant
  8.     mulv =  p->exp - p->suivant->exp;
  9.     s = p->suivant->coeff + mult(mulv, v) * s;
  10. p = p->suivant;
  11.   }
  12.   if (p->exp)
  13.   s = mult(p->exp, v) * s;
  15. return s;
  16. }


 
J'ai ecrit cette forme de l' algo a vue de nez a partir de la formule du lien donne en 1)
Cette ecriture peut sans doute s' ameliorer.
 
A+,


Message édité par gilou le 11-01-2004 à 03:46:36

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 11-01-2004 à 11:54:14    

gilou a écrit :

Bon alors:
1) Horner c'est pas du recursif, mais de l'iteratif. Voir par exemple ce lien http://www.umh.ac.be/math/an/courses/Horner.pdf qui est tres tres clair
2) Horner se fait en triant le polynome par ordre decroissant
 
donc

Code :
  1. void insererdecroissant(pmonome pe, ppoly ptr)               
  2. { poly l = *ptr;                                                     
  4. if (estnul(ptr))
  5.    *ptr = pe;
  6. else{   // on inverse l' ordre de comparaison donc  
  7.    while((l->suivant != NULL) && (l->exp > pe->exp))       
  8.      l = l->suivant;


 
3) Pour horner, ta fonction int mult(int mulv, int v) doit clairement calculer la puissance mulv-ienne de v
 

Code :
  1. int mult(int mulv, int v)
  2. {  int a=v;
  4. while(mulv > 1)
  5. {
  6.   // donc pas une addition
  7.    a = a*v;
  8.    mulv--;
  9. }
  10. return a;
  11. }


 
 
4) et c' est donc un algo iteratif ecrit a la va vite comme suit:

Code :
  1. float evaluer_poly(poly p, int v)
  2. {
  3.   float s= p->coeff;
  4.   int mulv;
  6.   while(p->suivant)
  7.   { // inverse car l' ordre est decroissant maintenant
  8.     mulv =  p->exp - p->suivant->exp;
  9.     s = p->suivant->coeff + mult(mulv, v) * s;
  10. p = p->suivant;
  11.   }
  12.   if (p->exp)
  13.   s = mult(p->exp, v) * s;
  15. return s;
  16. }


 
J'ai ecrit cette forme de l' algo a vue de nez a partir de la formule du lien donne en 1)
Cette ecriture peut sans doute s' ameliorer.
 
A+,


 
Salut,
Jte remercie mais en fait c'est pas ce que je cherche, puisque comme je l'ai dis je dois le faire en Récursif et non Itératif !
Pour avoir une idée du fonctionnement voir ici http://benrida.univ-tln.fr
Dans la sous-partie "Récursivité" puis "Horner".
En fait comme je l'ai dit hier, j'arrive à le faire si les monomes qui se suivent ont des exposant qui se suivent (dans ce cas il faut enlever qqes trucs avec mulv dans mon code) mais ac ne marche pas quand les exposant ne se suivent pas, l'idée étant de multiplier v par la différence de 2 exposants côte à côte.
Voila voila
Merci :)


---------------
- mon feed-back
Reply

Marsh Posté le 11-01-2004 à 16:34:28    

Je viens de voir le texte.
C'est neanmoins ainsi que je te l'ai dit (bon, il veut faire ca de maniere recursive alors que c'est naturellement iteratif  :sarcastic:)
Neanmoins, si tu regardes, tu verras que contrairement a ce que tu as initialement fait,
1) On commence par le degre le plus fort, donc tri drecroissant
2) ta fonction mult doit bien etre l'exponentiation que je te decris.  
Relis le lien que tu m'as donné, c'est tres clair.
 
Autant ecrire une exponentiation complete:
 

Code :
  1. int mult1(int mulv, int v)
  2. {
  4. if (mulv)
  5. {
  6. int a=v;
  7. while(mulv > 1)
  8. {
  9. a = a*v;
  10.  mulv--;
  11. }
  12. return a;
  13. }
  14. return 1;
  15. }

 
 
 
 
3) si tu veux une fonction recursive, comme le resultat obtenu doit etre multiplie par les puissances intermediaires a chaque appel, il va falloir que tu le passes en parametre.
Tu auras donc qque chose comme:
 
 
 

Code :
  1. void evaluer_poly1(poly p, int v, float *s)
  2. {
  3.   int mulv=p->exp;
  5.   *s += p->coeff;
  6.   if (p->suivant)
  7.   {
  8.     mulv -= p->suivant->exp;
  9.    *s *= mult1(mulv, v);
  10. evaluer_poly1(p->suivant, v, s);
  11.   }
  12.   else
  13. *s *= mult1(mulv, v);
  15. return;
  16. }

   
 
 
que tu appelles avec  

Code :
  1. c = 0;
  2. evaluer_poly1(*ptr, e, &c);


 
Bon la encore un truc ecrit vite fait (entre deux decoupes de papier peint), a toi d'ameliorer ce type de code.
 
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed