Partage
  • Partager sur Facebook
  • Partager sur Twitter

Quelqu'un pourrait m'aider avec un algo adapté?

    13 janvier 2022 à 19:49:16

    Je travaille sur un programme qui fait l'addition de deux polynômes avec liste chaînée.  Notre tuteur dit qu'il veut que l'utilisateur entre tout le polynôme d'un coup au lieu d'entrer les coefficients et les degrés successivement !  Je travaille avec des listes chaînées et j'ai une fonction qui ajoute des monômes pour former un polynôme à travers une liste chaînée (c'est-à-dire : fonction addmonome(Poly p, coef, deg)).  Si vous voulez du code, dites le moi !
    • Partager sur Facebook
    • Partager sur Twitter
      13 janvier 2022 à 20:55:37

      Bonjour,

      SteeveIlboudo a écrit:

      Quelqu'un pourrait m'aider avec un algo adapté ?

      Les forums sont fait pour ça.

      Tu as décris ce que tu fais, c'est bien, mais il te reste à poser ta question.

      SteeveIlboudo a écrit:

      Notre tuteur dit qu'il veut que l'utilisateur entre tout le polynôme d'un coup...

      Saisie d'une chaîne de caractères à décortiquer ensuite ? C'est cela ?



      • Partager sur Facebook
      • Partager sur Twitter
        13 janvier 2022 à 22:47:38

        Bonjour,

        Tu dis :

        SteeveIlboudo a écrit:

        [...] j'ai une fonction qui ajoute des monômes pour former un polynôme à travers une liste chaînée (c'est-à-dire : fonction addmonome(Poly p, coef, deg)).  [...]


        Mais dans ton autre sujet tu n'as pas ça. Tu as bien des maillons de liste 

        typedef struct Polynome *Poly;
        struct Polynome{
            int degre;
            float coef;
            struct Polynome *suivant;
        };


        Tu n'ajoutes pas un monôme (ou ce qui pourrait représenter un monôme) à un polynôme (ou une liste qui le représenterait). Tu ne fais qu'ajouter un maillon dans une suite de maillons.

        Poly ajouteMonome(Poly polynome,float coef,int degre)
        {
            Poly tmp;
            tmp=malloc(sizeof *tmp);
            tmp->coef=coef;
            tmp->degre=degre;
            tmp->suivant=polynome;
            return tmp;
        }



        Tu pourrais te dire que je pinaille sur le mots … mais je veux juste souligner un manque dans la phase de conception.

        Si tu dois manipuler des monômes alors ce serait une bonne idée d'avoir quelque chose qui représente un monôme, quelque chose comme :

        struct monomial {
            unsigned int power;
            double coef;
        };

        avec des fonctions qui manipulent des monômes.

        Tu pourras ensuite construire une liste de monômes qui ne représentera pas directement un polynôme mais juste une liste de monômes. Un type comme :

        struct mlist {
            struct monomial monomial;
            struct mlist *next;
            struct mlist *previous; // si on décide d'avoir une liste doublement chaînée
        };
        

        Cette liste pourra avantageusement être créée et maintenue triée (par degrés croissant par exemple).

        Seulement ensuite tu pourras créer une structure de données représentant un polynôme comme :

        struct polynomial {
            struct mlist *mlist;
            ...
        };

        L'avantage de cette démarche est qu'elle va séparer le fait de rechercher/modifier/ajouter/retirer un monôme d'une liste facilement, sachant que ce sera au niveau du polynôme que l'on va gérer des cas comme «éliminer les monômes de coef nul», «gérer le cas particulier d'un polynôme nul», …


        Puis si tu dois lire «tout le polynôme d'un coup» alors le plus difficile sera sans doute de résoudre le problème de lire un monôme, lire un polynôme revient à lire des monômes tant que tu peux et les ajouter (en sachant que tu gères les cas particuliers).

        Ensuite tout va dépendre de ce que ton tuteur comprend par «tout lire d'un coup», dois-tu pouvoir parser quelque chose comme "2*x^2-x-1" ou plus complexe comme un "2x2 + -1x - +1" ou plus simple comme "2 2 -1 1 -1 0". Bon ça donne quoi un «1-x²+x-2x+x+x²-1» ???



        • Partager sur Facebook
        • Partager sur Twitter
          14 janvier 2022 à 2:21:17

          Je pensais que tu avais compris dans l'autre sujet. Il semble que non.
          Ma perception de ce que dit White Crow est ce que j'ai dit:
          il te faut une tête de liste, ou descripteur de liste.
          On pourrait dire que le polynôme est la liste au complet et les monômes sont les maillons de la liste.
          Je trouve plutôt ambigu la consigne de ton tuteur sur le fait de lire tout le polynôme "d'un seul coup".
          Ça ne devrait en rien interférer avec le reste du programme.
          J'ai bien fait un test en générant mes coefficients et mes exposant "au hasard" avec la fonction rand().
          Je l'ai fait "d'un seul coup". Est-ce que ça veut dire quelque chose?
          • Partager sur Facebook
          • Partager sur Twitter

          Le Tout est souvent plus grand que la somme de ses parties.

            14 janvier 2022 à 9:27:10

            Ce que je dis surtout est qu'il vaut mieux passer du temps à réfléchir avant, tester des idées avant, voire même regarder ce qui a déjà été fait avant qu'à débuguer un code spaghetti après et faire appel à un forum parce qu'on est perdu dans son propre code.

            Mais, en tant que débutant c'est aussi ainsi qu'on l'apprend, the hard way …

            • Partager sur Facebook
            • Partager sur Twitter
              14 janvier 2022 à 10:00:50

              L'analyse de l'expression qui représente un polynôme, c'est simple (mais ennuyeux) quand on sait faire, mais pas de la tarte pour les débutants.

              Voila un programme qui, quand on lance les tests

              int main()
              {
                  test(" 123 ");
                  test("  -   123  ");
                  test(" x ");
                  test(" -x");
                  test(" -x - 123");
                  test(" - 12 x ^2 - 3 x + 4");
              
                  return EXIT_SUCCESS;
              }


              affiche les monômes  de chaque polynôme

              # test :  123 
              -> 123 X^0
              
              # test :   -   123  
              -> -123 X^0
              
              # test :  x 
              -> 1 X^1
              
              # test :  -x
              -> -1 X^1
              
              # test :  -x - 123
              -> -1 X^1
              -> -123 X^0
              
              # test :  - 12 x ^2 - 3 x + 4
              -> -12 X^2
              -> -3 X^1
              -> 4 X^0
              
              

              Comme c'est jour de fête, j'ai fait ça bien en définissant des types pour les monômes, les polynômes et le "lecteur" chargé d'analyser une chaîne. Le polynôme reste à implémenter, avec une liste chaînée si vous voulez.

              Attention, aucune détection d'erreur n'est effectuée.

              #include <stdio.h>
              #include <stdlib.h>
              #include <stdbool.h>
              #include <ctype.h>
              
              typedef struct s_reader {
                  const char *string;
                  const char *next;
              } reader;
              
              typedef struct s_monomial {
                  int coefficient;
                  int degree;
              } monomial;
              
              typedef struct s_polynomial {
                  int todo;
              } polynomial;
              
              char reader_next_char(reader *r)
              {
                  return *(r->next);
              }
              
              void reader_advance(reader *r)
              {
                  r->next += 1;
              }
              
              void reader_skip_spaces(reader *r)
              {
                  while (isspace(reader_next_char(r))) {
                      reader_advance(r);
                  }
              }
              
              bool reader_reached_the_end(reader *r)
              {
                  reader_skip_spaces(r);  // one never knows
                  return *(r->next) == '\0';
              }
              
              unsigned  reader_parse_natural(reader *r)
              {
                  unsigned value = 0;
                  reader_skip_spaces(r);
                  for (char c; isdigit(c = reader_next_char(r)); reader_advance(r)) {
                      value = 10 * value + c - '0';
                  }
                  reader_skip_spaces(r);
                  return value;
              }
              monomial reader_parse_monomial(reader *r)
              {
                  reader_skip_spaces(r);
              
                  // sign?
                  int signum = 1;
                  if (reader_next_char(r) == '-') {
                      signum = -1;
                      reader_advance(r);
                  } else if (reader_next_char(r) == '+') {
                      reader_advance(r);
                  }
                  // digits ?
                  reader_skip_spaces(r);
                  int coefficient = 1;        // default
                  if (isdigit(reader_next_char(r))) {
                      coefficient = reader_parse_natural(r);
                  }
                  coefficient *= signum;
              
                  int degree = 0;         // default
                  // letter x ?
                  reader_skip_spaces(r);
                  if (tolower(reader_next_char(r)) == 'x') {
                      degree = 1;       // new default
                      reader_advance(r);
                      reader_skip_spaces(r);
                      // symbol ^ ?
                      if (reader_next_char(r) == '^') {
                          reader_advance(r);
                          degree = reader_parse_natural(r);
                      }
                  }
                  return (monomial) {
                      .coefficient = coefficient,
                      .degree = degree
                  };
              }
              
              
              polynomial reader_parse_polynomial(reader *r)
              {
                  reader_skip_spaces(r);
                  do {
                      monomial m = reader_parse_monomial(r);
                      printf("-> %d X^%d\n", m.coefficient, m.degree);
                  } while (! reader_reached_the_end(r));
              
                  return (polynomial) {
                      .todo = 1789  // fake
                  };
              }
              
              void test(const char string[])
              {
                  printf("# test : %s\n", string);
                  reader r = {
                      .string = string,
                      .next = string
                  };
              
                  (void)  reader_parse_polynomial(&r);
                  printf("\n");
              }
              
              int main()
              {
                  test(" 123 ");
                  test("  -   123  ");
                  test(" x ");
                  test(" -x");
              	test(" -x - 123");
                  test(" - 12 x ^2 - 3 x + 4");
              
                  return EXIT_SUCCESS;
              }
              

              Si c'était moi l'enseignant je leur dirais de lire le polynôme sous forme d'une liste de paires de nombres (coefficient et degré) terminée par un "coeff' 0.

              Exemple  123 3  45 1  -6 0 0 pour   123x^2 + 45x -6

              Et puis peut être que les coeffs seraient des nombres flottants. Y  pas de raison que ça soit que des entiers.

              Déjà, lire une suite de nombres avec une valeur sentinelle, ça pose des problèmes à certains.

              -
              Edité par michelbillaud 14 janvier 2022 à 10:10:55

              • Partager sur Facebook
              • Partager sur Twitter
                14 janvier 2022 à 19:09:40

                SteeveIlboudo a écrit:
                >Si vous voulez du code, dites le moi !
                On n'a pas le code final dans ce post, ni ce que veut exactement le tuteur quand il dit de tout lire "d'un coup".
                @michelbillaud:
                N'est-ce pas trop avancé pour un débutant?
                Comme je l'ai déjà dit, la saisie des éléments est indépendante de l'addition des polynômes.
                • Partager sur Facebook
                • Partager sur Twitter

                Le Tout est souvent plus grand que la somme de ses parties.

                  14 janvier 2022 à 19:43:36


                  PierrotLeFou a écrit:


                  @michelbillaud:
                  N'est-ce pas trop avancé pour un débutant?
                  Comme je l'ai déjà dit, la saisie des éléments est indépendante de l'addition des polynômes.


                  Bien sur que si. C'était pour montrer, code à l'appui, que la lecture sous forme d'expressions que certains ont évoqué plus haut, c'était nettement plus chaud que le coeur de l'exercice, qui va consister à parcourir deux listes simultanément en additionnant les monômes de même degré (et pas en faisant deux boucles), soit une variante de la fusion de listes ordonnées. Ce qui pose déjà assez de soucis aux débutants.

                  C'est bien pour ça que j'ai précisé :

                  > Si c'était moi l'enseignant je leur dirais de lire le polynôme sous forme d'une liste de paires de nombres (coefficient et degré) terminée par un "coeff' 0.

                  et que je me suis abstenu d'y placer les 5 lignes qui construisent effectivement la représentation sous forme de liste chaînée (en réalité un peu plus parce qu'il faudrait ordonner les monômes si on ne les suppose pas ordonnés), parce que je ne suis pas là pour faire les exercices. De toutes façons si quelqu'un ressort le code que j'ai fourni, il va avoir du mal à faire croire que c'est lui qu'il l'a écrit je pense, vu les écarts de style qu'il y aura avec les morceaux qu'il faut rajouter :-)

                  Mais bon, l'OP, il faut qu'il cause avec son prof qui lui a posé l'exercice. Nous, on peut pas savoir ce qu'il a dans sa tête à lui. Et c'est son boulot de donner des spécifications claires de l'exercice, même si c'est juste pour dire de faire comme on veut.

                  -
                  Edité par michelbillaud 14 janvier 2022 à 19:49:27

                  • Partager sur Facebook
                  • Partager sur Twitter
                    14 janvier 2022 à 20:20:31

                    Dans le post précédent, j'avais mis une version de l'addition qui supposait que les listes étaient ordonnées.
                    Je n'ai pas inclus la fonction d'insertion des monômes dans la liste.

                     On doit prévoir que la puissance à insérer existe déjjà dans la liste.

                    L'addition se fait en effet comme une fusion de deux listes avec possibilité (forte, on l'espère) d'avoir des éléments identiques.
                    J'ai refait le code en envoyant la somme dans une troisième liste.
                    Ce que je constate, et dont je me doutais, est que la fonction de création des monômes doit inclure le malloc et initialiser le maillon.
                    Cela simplifie grandement la fonction d'addition / fusion.

                    -
                    Edité par PierrotLeFou 14 janvier 2022 à 20:25:42

                    • Partager sur Facebook
                    • Partager sur Twitter

                    Le Tout est souvent plus grand que la somme de ses parties.

                      15 janvier 2022 à 16:18:50

                      la somme par "fusion", un bel exemple d'utilisation de la récursivité (en Lisp)

                      (setq a '((4 3) (-3 2) (8 0)))
                      (setq b '((12 5) (6 3) (3 2) (7 1)))
                      
                      
                      (defun somme (p1 p2)
                          (cond 
                              ((null p1) p2)
                              ((null p2) p1)
                              
                              ((> (cadar p1)(cadar p2)) 
                                  (cons (car p1)(somme (cdr p1) p2)))
                              
                              ((> (cadar p2)(cadar p1)) 
                                  (cons (car p2)(somme (cdr p2) p1)))
                              
                              (t (let ((c (+ (caar p1) (caar p2)))
                                      (s  (somme (cdr p1)(cdr p2))))
                                      (if (= c 0) 
                                          s
                                          (cons (list c (cadar p1)) s)
                                      )))
                                          
                          ))
                                          
                      (write (somme a b))

                      Résultat

                      $clisp main.lisp
                      ((12 5) (10 3) (7 1) (8 0))
                      


                      Il faut bien s'occuper en attendant d'en savoir plus sur le format d'entrée voulu.

                      Représentation polynome : liste de paires (coeff, degré) dans l'ordre des degrés décroissants.

                      EDIT: en attendant que quelqu'un nous montre que l'analyse de la chaine, on fait jamais comme ça, ça serait plus simple avec lex et yacc.

                      -
                      Edité par michelbillaud 15 janvier 2022 à 17:54:43

                      • Partager sur Facebook
                      • Partager sur Twitter
                        15 janvier 2022 à 18:22:28

                        Toujours pour s'occuper en attendant...

                        Si on me demandait de rentrer le polynôme d'un coup tout en me laissant la liberté de comment le faire, je choisirais une syntaxe simple : rentrer les coefficients par ordre croissant, séparés par un espace.

                        Exemple :

                        Coefficients > 0 0 -2.5 0 3.14159 -1
                        P(X) = -1.000000 X^5 + 3.141590 X^4 - 2.500000 X^2 
                        

                        Idée : on lit la ligne sous forme de chaîne de caractère, et on parcourt cette ligne caractère par caractère en remplissant une chaîne temporaire. Chaque fois qu'on rencontre un espace, on traite la chaîne temporaire avec 'sscanf'. Si 'sscanf' n'échoue pas, il retourne un coefficient, que j'ai choisi de mettre dans un tableau (parce que les listes chaînées, fouyouyouye...)

                        Voici ce que ça donne (j'ai essayé pas mal de cas, ça a l'air de marcher, mais je n'ai pas approfondi. C'était surtout pour illustrer une méthode pour lire le polynôme d'un coup.

                        #include <stdbool.h>
                        #include <stdio.h>
                        #include <stdlib.h>
                        #define MAXLIGNE 1000
                        #define MAXDEGRE 1000
                        #define EPSILON 1E-12
                        
                        bool extraire_poly(char lig[MAXLIGNE], double tcoeff[MAXDEGRE], int* pdeg)
                        // retourne false si on n'a pas réussi à extraire le polynôme
                        {
                            int i = 0 ;             // n° dans la ligne
                            int nb_coeff = 0 ;
                            bool pas_erreur = true ;
                            bool pas_fini = true ;
                            char coeff[MAXLIGNE] ;  // chaîne contenant un coefficient
                            int j = 0 ;             // n° dans 'coeff'
                            while (pas_erreur && pas_fini && (i <= MAXLIGNE))
                            {
                                //printf("lig[%d] = |%c|\n", i, lig[i]) ;
                                if ((lig[i] == ' ') || (lig[i] == '\n'))    // fin du coeff
                                {
                                    //printf("    Fin du coeff\n") ;
                                    coeff[j] = '\0' ;   // pour terminer la chaîne !
                                    pas_erreur = (sscanf(coeff, "%lf", &(tcoeff[nb_coeff])) == 1) ;
                                    if (!pas_erreur)
                                        printf("Erreur lecture polynôme\n") ;
                                    //else
                                        //printf("--> coeff[%d] = %lf\n", nb_coeff, tcoeff[nb_coeff]) ;
                                    nb_coeff ++;
                                    if (lig[i] == '\n') // c'était le dernier coeff
                                    {
                                        pas_fini = false ;
                                        *pdeg = nb_coeff - 1 ;
                                        //printf("    C'était le dernier coeff, degré = %d\n", *pdeg) ;
                                    }
                                    j = 0 ;         // ré-initialisation de 'coeff'
                                }
                                else    // on remplit le tableau 'coeff'
                                {
                                    coeff[j] = lig[i] ;
                                    j++ ;
                                }
                                i++ ;
                            }
                            return pas_erreur ;
                        }
                        
                        void afficher_monome(char nomvar, double x, int n, int deg, double eps)
                        // 'nomvar' : nom de la variable, exemple 'X'
                        // 'x'      : coefficient d'exposant 'n' dans le polynôme de degré 'deg'
                        // 'eps'    : précision (tout nombre compris entre -eps et eps est considéré nul)
                        {
                            if (n == deg)   // '+' non affiché, '-' collé au coeff
                            {
                                if (x <= -eps)
                                    printf("-%lf ", -x) ;
                                else if (x >= eps)
                                    printf("%lf ", x) ;
                            }
                            else
                            {
                                if (x <= -eps)
                                    printf("- %lf ", -x) ;
                                else if (x >= eps)
                                    printf("+ %lf ", x) ;
                            }
                            if ((x <= -eps) || (x >= eps))
                            {
                                if (n > 1)
                                    printf("%c^%d ", nomvar, n) ;
                                else if (n == 1)
                                    printf("%c ", nomvar) ;
                            }
                        }
                        
                        void afficher_poly(double coeff[MAXDEGRE], int deg)
                        {
                            printf("P(X) = ") ;
                            for (int i = deg ; i >= 0 ; i--)
                                afficher_monome('X', coeff[i], i, deg, EPSILON) ;
                            printf("\n") ;
                        }
                        
                        int main(void)
                        {
                            char ligne[MAXLIGNE] ;      // Ligne saisie
                            double coeff[MAXDEGRE] ;    // tableau des coeffs du polynôme
                                                        // coeff[i] = coeff de la puissance i
                            int degre ;                 // degré du polynôme                                    
                            printf("Coefficients > ") ;
                            fgets(ligne, MAXLIGNE, stdin) ;
                            if (extraire_poly(ligne, coeff, &degre))
                                afficher_poly(coeff, degre) ;
                            return EXIT_SUCCESS ;
                        }
                        


                        (J'ai laissé les 'printf' de mise au point. Je trouve que c'est une bonne idée de mettre ce genre d'affichage au fur et mesure de la mise au point d'un programme. Là ça m'a servi par exemple à ne pas oublier de faire -1 dans le calcul de *pdeg, ligne 33.)

                        -
                        Edité par robun 15 janvier 2022 à 18:27:04

                        • Partager sur Facebook
                        • Partager sur Twitter
                          15 janvier 2022 à 19:23:03

                          Voici ma version de la somme de polynôme postée en toute illégalité. :)
                          Je renvoie la somme dans un troisième polynôme.
                          -
                          #include <stdio.h>
                          #include <stdlib.h>
                          #include <time.h>
                          #include <limits.h>
                          typedef struct Term Term;
                          struct Term {
                              int degree;
                              double coefficient;
                              Term *next;
                          };
                          typedef struct Polynome Polynome;
                          struct Polynome{
                              Term *first;
                          };
                          void *getArea(char *name, int size) {
                              void *area = malloc(size);
                              if(area) return area;
                              perror(name);
                              printf("Required: %d\n", size);
                              exit(EXIT_FAILURE);
                          }
                          Polynome *getPolynome() {
                              Polynome *head = getArea("getPolynome", sizeof(Polynome));
                              head->first = NULL;
                              return head;
                          }
                          Term *getTerm(int degree, double coefficient) {
                              Term *term = getArea("getTerm", sizeof(Term));
                              term->degree = degree;
                              term->coefficient = coefficient;
                              term->next = NULL;
                              return term;
                          }
                          void display(Polynome *polynome) {
                              Term *current = polynome->first;
                              char *plus = "";
                              while(current) {
                                  if(current->coefficient != 0) {
                                      if(current->coefficient < 0)
                                      plus = "";
                                      printf("%s%.0f", plus, current->coefficient);
                                      plus = "+";
                                      if(current->degree != 0) {
                                          printf("X");
                                          if(current->degree != 1)
                                          printf("^%d", current->degree);
                                      }
                                  }
                                  current = current->next;
                              }
                              printf("\n");
                          }
                          void insert(Polynome *polynome, int degree, double coefficient) {
                              Term **previous = &polynome->first;
                              Term *current = *previous;
                              while(current && current->degree > degree) {
                                  previous = &current->next;
                                  current = current->next;
                              }
                              if(current && current->degree == degree) {
                                  current->coefficient += coefficient;
                              } else {
                                  Term *term = getTerm(degree, coefficient);
                                  term->next = *previous;
                                  *previous = term;
                              }
                          }
                          Term *addTerm(Term *term1, Term *term2) {
                              if( !term1 && !term2) return NULL;
                              int degree1 = (term1) ? term1->degree : INT_MIN;
                              int degree2 = (term2) ? term2->degree : INT_MIN;
                              Term *term3;
                              if(degree1 == degree2) {
                                  term3 = getTerm(degree1, term1->coefficient + term2->coefficient);
                                  term1 = term1->next;
                                  term2 = term2->next;
                              } else if(degree1 > degree2) {
                                  term3 = getTerm(degree1, term1->coefficient);
                                  term1 = term1->next;
                              } else {
                                  term3 = getTerm(degree2, term2->coefficient);
                                  term2 = term2->next;
                              }
                              term3->next = addTerm(term1, term2);
                              return term3;
                          }
                          Polynome *addPolynome(Polynome *polynome1, Polynome *polynome2) {
                              Polynome *polynome3 = getPolynome();
                              polynome3->first = addTerm(polynome1->first, polynome2->first);
                              return polynome3;
                          }
                          void destroy(Polynome *polynome) {
                              Term *current = polynome->first;
                              while(current) {
                                  Term *scratch = current;
                                  current = current->next;
                                  free(scratch);
                              }
                              free(polynome);
                          }
                          int main(void) {
                              Polynome *polynome1 = getPolynome();
                              Polynome *polynome2 = getPolynome();
                              srand(time(NULL));
                              for(int i=0; i<10; i++) {
                                  insert(polynome1, rand()%10, rand()%100-25);
                                  insert(polynome2, rand()%10, rand()%100-25);
                              }
                              printf("Termes ajoutés\n");
                              display(polynome1);
                              display(polynome2);
                              Polynome *polynome3 = addPolynome(polynome1, polynome2);
                              display(polynome3);
                              destroy(polynome1);
                              destroy(polynome2);
                              destroy(polynome3);
                              printf("Polynômes effacés\n");
                              return EXIT_SUCCESS;
                          }
                          -
                          Termes ajoutés                                                                                                          
                          115X^7+66X^6+66X^5+69X^3+57X^2-8X                                                                                       
                          46X^7+38X^6+97X^4-7X^3-1                                                                                                
                          161X^7+104X^6+66X^5+97X^4+62X^3+57X^2-8X-1                                                                              
                          Polynômes effacés
                          • Partager sur Facebook
                          • Partager sur Twitter

                          Le Tout est souvent plus grand que la somme de ses parties.

                            16 janvier 2022 à 19:18:01

                            Le probléme avec les données générées aléatoirement c'est que personne ne  va vérifier que les résultats affichés sont corrects.

                            Idée pour vérifier automatiquement que le résultat est correct :

                            • écrire la fonction qui évalue un polynôme pour un X donné
                            • vérifier que P1(x) + P2(x) = (P1+P2)(x) pour un certain nombre de valeurs de x
                            • pour "un certain nombre", prendre le max des deux degrés + 1
                            Derrière, il y a le théorème qui dit que si deux polynômes de degré n coïncident sur n+1 points, alors ils sont égaux. Exemple, si on a deux polynômes de degré 1, ils représentent des droites, et si deux droites ont deux points en commun...
                            Donc pas la peine de tirer des x au hasard, 0,1,2,...n, ça fait l'affaire.
                            PS attention aux grands nombres, si on a des degrés élevés.

                            -
                            Edité par michelbillaud 16 janvier 2022 à 19:21:58

                            • Partager sur Facebook
                            • Partager sur Twitter
                              16 janvier 2022 à 19:26:59

                              C'est vrai que ça n'est pas commode à vérifier. Je ne faisais à la main.
                              J'ai tout de même limité les degrés et les coefficients.
                              En utilisant mes primitives, on peut facilement faire un produit de polynômes.
                              -
                              Polynome *mulPolynome(Polynome *polynome1, Polynome *polynome2) {
                                  Polynome *polynome3 = getPolynome();
                                  Term *term1 = polynome1->first;
                                  while(term1) {
                                      Term *term2 = polynome2->first;
                                      while(term2) {
                                          insert(polynome3, term1->degree + term2->degree, term1->coefficient * term2->coefficient);
                                          term2 = term2->next;
                                      }
                                      term1 = term1->next;
                                  }
                                  return polynome3;
                              }
                              • Partager sur Facebook
                              • Partager sur Twitter

                              Le Tout est souvent plus grand que la somme de ses parties.

                                16 janvier 2022 à 21:36:00

                                Hum je pense qu'on y gagnerait à introduire une fonction qui retourne le produit d'un monome et d'un  polynome. Ça et utiliser la somme de deux polynômes, ca devrait éviter de manipuler trop de détails d'implémentation (chainage first next...) dans le code de la multiplication.

                                -
                                Edité par michelbillaud 16 janvier 2022 à 21:36:58

                                • Partager sur Facebook
                                • Partager sur Twitter
                                  17 janvier 2022 à 3:02:10

                                  Pour faire le produit de deux polynômes, on doit multiplier chaque terme d'un polynome par chaque terme de l'autre.
                                  En faisant le produit d'un monôme par un polynôme, on obtiendra autant de polynômes que de termes dans le premier.

                                  M0*P0 + M1*P0 + M2*P0 + ...
                                  On peut sans doute se contenter de un ou deux polynômes intermédiaires:
                                  M0 * P0 -> P1
                                  M1 * P0 -> P2
                                  P1 + P2 -> P1
                                  M2 * P0 -> P2
                                  P1 + P2 -> P1
                                  etc.
                                  Le produit d'un monôme par un polynôme ne sera pas plus simple que la boucle intérieure de ma fonction.
                                  Parce que c'est effectivement ce que je fais, sauf que je ne sépare pas les étapes.

                                  Ma fonction insert() tient compte des termes ayant le même exposant.

                                  @robun:
                                  Ton code aurait sans doute pu être simplifié avec l'utilisation de strtok()
                                  Voici un exemple simpliste sans validation:
                                  -
                                  #include <stdio.h>
                                  #include <string.h>
                                  int main(void) {
                                      int coef[100];
                                      char line[100];
                                      fgets(line, 100, stdin);
                                      line[strlen(line)-1]='\0';
                                      char *from = line;
                                      int nd = 0;
                                      char *token;
                                      while((token = strtok(from, " "))) {
                                          sscanf(token, "%d", &coef[nd++]);
                                          from = NULL;
                                      }
                                      for(int i=0; i<nd; i++) printf("%d ", coef[i]);
                                      printf("\n");
                                  }

                                  -
                                  Edité par PierrotLeFou 17 janvier 2022 à 5:19:03

                                  • Partager sur Facebook
                                  • Partager sur Twitter

                                  Le Tout est souvent plus grand que la somme de ses parties.

                                    17 janvier 2022 à 11:04:12

                                    Pierrot : je n'ai jamais utilisé 'strtok', je viens de regarder le « man » et ton exemple, effectivement ça a l'air bien adapté. Merci pour l'idée !
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      17 janvier 2022 à 11:58:11

                                      strtok, c'est le genre de truc mal fichu qu'on se trimballe depuis les débuts de C.

                                      • c'est pas réentrant (*) parce que le premier appel stocke l'adresse de la chaîne dans une variable statique...
                                      • on ne peut donc pas s'en servir pour parcourir deux chaines en parallèles (mise en correspondance des tokens de l'une et de l'autre, par exemple), ni dans des threads.
                                      • ça nique la chaine qui est en cours d'analyse en y casant des caractères nuls,  on perd les données d'origine et ne peut donc pas traiter une chaine "const".
                                      voir par exemple l'implémentation d'Apple
                                      (*)
                                      il y a des versions réentrantes

                                      -
                                      Edité par michelbillaud 17 janvier 2022 à 12:02:12

                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        18 janvier 2022 à 15:01:56

                                        Puisque le PO ne donne pas encore signe de vie ...
                                        @michelbillaud:
                                        D'accord avec tes objections pour la récursivité, les thread et la comparaison de deux chaînes.
                                        Dans le contexte actuel, ce n'est pas grave de détruire la chaîne d'entrée.
                                        @robun:
                                        J'ai repris ta fonction extraire_poly(). J'ai utilisé un truc ressemblant un peu à strtok()
                                        Notte que sscanf retourne 1 même si le nombre est suivi de n'importe quoi (comme 3.3A)
                                        J'utilise donc cela et ne modifie pas la chaîne d'entrée. sscanf va se buter sur le délimiteur.

                                        On peut simplifier si le seul délimiteur est l'espace. On peut faire sauter le '\n' dans le main.
                                        -
                                        bool est_dans_liste(char c, char *s) {
                                            while(*s)  if(c == *s++)  return true;
                                            return false;
                                        }
                                         
                                        bool extraire_poly(char lig[MAXLIGNE], double tcoeff[MAXDEGRE], int* pdeg) {
                                            int nb_coeff = 0 ;
                                            char *delimiteur = " ,;:\n";
                                            char *courant = lig;
                                            while(est_dans_liste(*courant, delimiteur))  courant++;
                                             while(*courant) {
                                                char *suivant = courant;
                                                while(*suivant && !est_dans_liste(*suivant, delimiteur))  suivant++;
                                                while(est_dans_liste(*suivant, delimiteur))  suivant++;
                                                if(sscanf(courant, "%lf", &tcoeff[nb_coeff++]) == 0)  return false;
                                                courant = suivant;
                                            }
                                            *pdeg = nb_coeff - 1;
                                            return true;
                                        }

                                        -
                                        Edité par PierrotLeFou 18 janvier 2022 à 17:23:11

                                        • Partager sur Facebook
                                        • Partager sur Twitter

                                        Le Tout est souvent plus grand que la somme de ses parties.

                                        Quelqu'un pourrait m'aider avec un algo adapté?

                                        × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                        • Editeur
                                        • Markdown