Les méthodes de tous les exercices doivent être écrites
dans les classes fournies en annexe
(télécharger ces classes)
.
EXERCICE 1
On veut enrichir la classe Liste vue en cours avec de nouvelles fonctions, c'est à dire de nouvelles méthodes qui ne modifient pas leurs
arguments. Ces méthodes sont non primitives, c'est à dire de
méthodes pouvant s'écrire à l'aide des méthodes primitives
étudiées en cours.
Ecrivez les méthodes itératives suivantes dans la classe
Liste :
longueur(), qui retourne le nombre d'éléments de la
liste
element(int i), qui retourne le iième
élément de la liste (avec i = 1 pour le premier élément)
position(Object x), qui retourne la position de la première
occurence de l'objet x dans la liste, ou 0 si l'objet n'est pas dans la
liste
Aucune difficulté
EXERCICE 2
On veut enrichir la classe Liste vue en cours avec de nouvelles procédures, c'est à dire de nouvelles méthodes qui peuvent modifier
certains de leur arguments. Ces méthodes sont non primitives, c'est
à dire de méthodes pouvant s'écrire à l'aide des méthodes primitives étudiées en cours.
Ecrivez les méthodes itératives suivantes de la classe
Liste :
ajouter(Object x, int i), qui ajoute à la liste l'objet xaprès le iième élément. Pour i valant 0,
l'objet x est ajouté en tête de la liste. Si i est plus grand
que la longueur de la liste, alors l'objet x est ajouté en fin de
liste.
supprimer(int i), qui supprime le iième élément
de la liste. Si i est plus grand que la longueur de la liste, la
méthode ne fait rien.
Aucune difficulté.
EXERCICE 3
Et maintenant, un peu de récursivité !
Reprenez les exercices 1 et 2 en donnant maintenant une version récursive des différentes méthodes.
Aucune difficulté.
EXERCICE 4
On désire manipuler des ensembles d'entiers, comme {0,2,59},
{-7}, {} ou {1,2,3,4}.
On peut représenter un tel ensemble comme une liste strictement
croissante d'entiers. L'ensemble vide est représenté par la liste
vide. Un ensemble peut être considérée comme une valeur non
modifiable, les opérations sur les ensembles créant éventuellement de
nouveaux ensembles (union, intersection, etc.).
En utilisant uniquement l'ensemble (réduit) des primitives de la
classe Ensemble donnez le corps de toutes les méthodes non
primitives (cardinal, contient, estInclusDans, union, intersection, difference).
Utilisez la récursivité et le fait qu'une liste représentant un
ensemble est triée en ordre strictement croissant.
EXERCICE 5
On désire manipuler des polynômes en une variable, à
coefficients entiers. Voilà des exemples de polynômes :
3x2+5x-1
x123
123412x-1
7x7+6x6+5x5+4x4+3x3+2x2+x+1
On peut représenter un polynôme comme une liste de monômes ordonnée suivant les puissances décroissantes. Le monôme de tête est
alors le monôme de plus haut degré. Le polynôme nul est représenté
par la liste vide. Un polynôme est une valeur non modifiable, les
opérations sur les polynômes créant éventuellement de nouveaux
polynômes (somme, produit, etc.).
La classe Polynome implémente des polynômes. La classe Monome
implémente des monômes. Notez que la classe Monome est privée et
qu'un monôme demeure invisible à l'extérieur de la classe
Polynome.
Donnez le corps de toutes les méthodes non primitives de la classe Polynome, méthodes définissant les opérations sur les polynômes.
Utilisez la récursivité et programmez à l'économie en utilisant au
maximum les méthodes entre elles.
EXERCICE 6
On désire manipuler des intervalles d'entiers. Un intervalle est soit
un intervalle simple, soit la réunion de plusieurs intervalles simples. Un
intervalle simple est soit l'intervalle vide, soit une suites d'entiers
consécutifs. Un intervalle simple peut-être spécifié à l'aide de
ses bornes, deux entiers x, y tels que x £ y. L'intervalle
est alors représenté par [x,y]. Voilà des exemples d'intervalles
simples :
[1,3]
[-2,5]
[0,10273]
[-1,1]
et des exemples d'intervalles (le signe È signifie union) :
[1,2] È [5,9]
[-5,3] È [11,21] È [100,12312]
Un intervalle peut être réduit à un seul élément :
[1,1]
[2,2]
[-3,-3]
On peut représenter de tels intervalles à l'aide de liste d'intervalles
simples en adoptant les conventions suivantes :
l'intervalle vide est représenté par la liste vide
un intervalle simple [x,y] doit être tel que x £ y
les intervalles simples formant un intervalle doivent apparaitre dans
l'ordre croissant, et ne doivent ni se chevaucher, ni se coller
Par exemple, les intervalles suivants respectent ces conventions :
[1,1]
[1,2] È [7,15] È [19,123]
[1,2] È [4,10] È [12,12]
alors que les intervalles suivants sont incorrects :
[3,-1]
[7,10] È [2,4] È [15,20]
[1,2] È [3,5] È [6,10]
Notez que le dernier des intervalles précédents est en fait
l'intervalle [1,10] .
Construisez une classe Intervalle qui offre toutes les
fonctionnalités attendues pour la manipulation des intervalles
(test d'appartenance d'un entier à un intervalle, cardinal, test
d'inclusion, union et intersection)