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 !
[...] 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)). [...]
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.
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» ???
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?
Le Tout est souvent plus grand que la somme de ses parties.
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 …
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
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.
Le Tout est souvent plus grand que la somme de ses parties.
@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
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
Le Tout est souvent plus grand que la somme de ses parties.
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.
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, °re))
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.)
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
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; }
Le Tout est souvent plus grand que la somme de ses parties.
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
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
Le Tout est souvent plus grand que la somme de ses parties.
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".
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; }
- Edité par PierrotLeFou 18 janvier 2022 à 17:23:11
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é.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.