TD d'informatique No. 4 :
les listes
Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr
Lundi 4 décembre 2000
1 Rappel de java
Pour quelques rappels sur les classes, les objets, static ou public,
regardez la page :
http://w3.edu.polytechnique.fr/profs/informatique/Patrick.Gros/java/classes.html.
2 Arithmétique en précision infinie
On veut faire de l'arithmétique avec des entiers aussi grand que l'on veut.
Pour cela, on représente chaque nombre par une liste. Chaque noeud de la
liste contient un entier et un pointeur. Le premier entier d'une liste
représente les unités, le deuxième les dizaines...
On cherche alors à écrire quelques fonctions simples pour manipuler ces
nombres. Pour chacune des fonctions, vous modifierez la fonction main afin
de pouvoir les tester au fur et à mesure de leur écriture.
Les fonctions simples à écrire :
-
création d'une liste à partir d'une chaîne de caractère représentant un entier ;
- affichage de l'entier représenté par une liste ;
- copie d'une liste ;
Il est plus simple de faire des fonctions récursives.
Deux fonctions plus avancées :
-
addition de deux nombre représentés par des listes ;
- multiplication de deux nombres représentés pas des listes.
Question facultative.
Une fois arrivé à ce point, essayez d'écrire une version itérative des trois
premières fonctions. Comparez leur temps d'exécution (en les faisant tourner
10000 fois chacune), et leur temps de développement.
3 Calcul sur les polynôme creux
Faire l'exercice précédent avec des polynômes creux.
This document was translated from LATEX by
HEVEA.