TD 3 - Calcul sur des polynômes
Problème
On veut faire des calculs sur des polynômes de la forme :
.
On utilisera pour cela une représentation compacte par liste
chaînée qui ne code que les ci non nuls.
Cette liste sera ordonnée selon les exposants décroissants.
Par exemple, le polynôme X5 - 2X4 + 1
sera représenté par la liste :
Pour simplifier, les coefficients seront de type int.
On va écrire les sous-programmes suivant :
un constructeur p_X, permettant des expressions de la forme :
p_X(1, 5, p_X(-2, 4, p_X(1, 0, NULL)))
une procédure print_X qui, pour cet exemple, imprime :
X^5 - 2.X^4 + 1
les opérateurs add_X, mul_X, pow_X et
eval_X.
Étant donnés deux polynômes P(X) et Q(X)
déjà construits et un entier n, ces quatre
opérateurs construisent respectivement P(X)+Q(X),
P(X).Q(X), P(X)n et P(Q(X)).
Pour le calcul de P(X)n, on utilisera un algorithme qui
effectue O(log n) produits de polynômes.
Modularité
Pour pouvoir réutiliser ces sous-programmes dans d'autres TD nous
allons en faire un module indépendant du programme d'utilisation.
Pour cela, on va utiliser trois fichiers :
- un fichier polynome.c qui va contenir le code des sous-programmes,
- un fichier test_poly.c qui va contenir le code de la fonction
main permettant de tester ces sous-programmes,
- un fichier polynome.h donné, qui
va décrire l'interface entre les deux précédents.
La compilation du tout peut se faire par la commande :
gcc -g -Wall polynome.c test_poly.c -o test_poly
L'inconvénient est que cela revient à tout recompiler à
chaque modification.
Il est préférable d'utiliser la commande make
après avoir mis un fichier
Makefile dans le répertoire
courant.
Travail demandé
- Écrire p_X et print_X et tester, par exemple :
- print_X(p_X(1, 5, p_X(-2, 4, p_X(1, 0, NULL))));
- Écrire les opérateurs add_X, mul_X,
pow_X et eval_X et tester (quelques
exemples).
- Étudier le coût en mémoire de chaque opération.
- Mettre en oeuvre un recyclage des listes intermédiaires.
On écrira donc la procédure free_X mais aussi la
fonction copy_X qui sera utilisée pour éviter le
partage des listes.
URL: http://www.enseignement.polytechnique.fr/profs/informatique/Philippe.Chassignet/97-98/TD/td_3.html
Dernière mise à jour :
13/10/1998
Pour toutes suggestions, commentaires ou remarques,
email : Philippe.Chassignet@polytechnique.fr