TD 2 : Structures de données et algorithmes élémentaires




Les méthodes de tous les exercices doivent être écrites dans les classes fournies en annexe (télécharger ces classes) . Donnez pour chaque méthode son en-tête et sa complexité, et accompagnez chaque itération de son invariant.

EXERCICE 1

 Le principe de la recherche dichotomique consiste à couper la tranche de tableau dans laquelle on cherche en deux demi-tranches de même taille, et à chercher éventuellement la clef dans l'une seulement de ces demi-tranches. On peut généraliser cette technique en coupant une tranche en k tranches de même taille. Dans cet exercice, on étudie le cas k = 3 qui constitue une recherche trichotomique.

Comparez la complexité en nombre de comparaisons entre les clefs dans le pire des cas pour les recherches dichotomique et trichotomique.

Ecrivez la méthode chercher de la classe Recherche qui recherche un objet de clef donnée dans un tableau trié en effectuant une recherche trichotomique.

EXERCICE 2

 Un programme source Java est un texte qui obéit à certaines règles syntaxiques. En particulier, les caractéres de regroupement (les caractères '(', '{' et '[') apparaissent toujours par deux, un caractère ouvrant et le caractère fermant correspondant. Par exemple, le texte suivant est un fragment de source Java (syntaxiquement) correct : public void affecter(Object x) { table[i.suivant()] = x; } Chaque caractère de regroupement ouvrant est suivi du caractère fermant correspondant. On dit alors que le texte est équilibré.

En supposant que le fragment de source Java à tester est dans la chaîne de caractères s, écrivez la méthode equilibree de la classe ChaineEquilibree qui teste si le texte qui est dans s est équilibré.

S'assurer que, pour chaque caractère de regroupement, il y a autant de caractères ouvrants et fermants ne suffit pas : par exemple le texte ``({)[}]'' n'est pas équilibré...

EXERCICE 3

 Etant donnée une suite d'entiers S strictement croissante et un entier n, n > 0, on cherche les valeurs x et y de S telles que y = x+n. Par exemple, si n = 3 et si la suite S contient 1, 3, 5, 6, 9, 10, 11, 12, 14, 16, les couples (x,y) vérifiant y = x+n sont (3,6), (6,9), (9,12) et (11,14).

En supposant que l'attribut s de la classe PairesSuite est une suite strictement croissante contenant des valeurss de type int, écrivez la méthode afficherLesPaires(int n) qui affiche tous les couples d'éléments x et y de S tels que y = x + n. Ecrivez ensuite la méthode de même profil de la classe PairesTableau qui fait la même chose quand la suite est stockée dans un tableau.

Dans la première méthode, utilisez une file pour stocker les entiers x tels que x + n > s.valeurCourante(). Dans la deuxième méthode, c'est une partie du tableau qui joue le rôle de la file...

EXERCICE 4

 Dans une gare de chemin de fer, on dispose d'un système rudimentaire pour composer un train, système illustré par la figure suivante :

Les wagons sont initialement sur la voie A. On désire composer le train sur la voie B, en utilisant la voie C, qui agit comme une pile. On suppose qu'on fait passer tous les wagons de la voie A vers la voie B, et que les n wagons en question sont numérotés de 0 à n-1. Les seules actions permises sont : Une suite d'actions composant un train peut être symbolisée par une suite de 'E' et de 'D' (une chaîne de caractères). On appelle une telle chaîne une commande, car elle peut être interprétée par un robot pour permuter les wagons de la voie A vers la voie B. Par exemple, on réalise la permutation de la figure précédente qui fait passer les wagons de la voie A dans l'ordre 0, 1, 2, 3 vers la voie B dans l'ordre 1, 2, 0, 3, avec la commande ``EEDEDDED''. Une chaîne quelconque formée de 'E' et de 'D' n'est pas nécessairement une commande. Par exemple, les chaînes ``DEEDD'', ``EEDDDED'' et ``EDEED'' ne sont pas des commandes, et les chaînes ``EDEEDD'' et ``EEDDEDEEDD'' ne sont pas des commandes valides pour permuter 4 wagons.

· Ecrivez la méthode valide(String s, int n) de la classe Train qui teste si s est une commande valide pour permuter n wagons.

On ne peut pas dépiler dans une pile vide et on peut empiler plusieurs éléments à la suite.

· En considérant qu'un train de n wagons est une permutation de 0, 1,..., n-1, stockée dans un tableau, écrivez la méthode valide(int[] t) de la classe Train qui teste si t[0], t[1],...,t[t.length - 1], est une permutation de 0, 1,..., t.length - 1.

Utilisez un tableau de booléens pour savoir si t contient bien une et une seule fois tous les entiers 0, 1,..., t.length - 1.

· Montrez que si l'ordre initial des wagons (de gauche à droite) sur la voie A est 0, 1,..., n-1, on peut les arranger dans l'ordre p0, p1,..., pn-1 si, et seulement si, il n'existe pas d'indices i, j et k tels que i < j < k et pj < pk < pi.

Les inégalités pj < pk < pi donnent l'ordre des wagons pi, pj et pk sur la voie A, alors que les inégalités i < j < k donnent l'ordre de ces mêmes wagons sur la voie B.

· En considérant que voieA et voieB donne respectivement l'ordre des wagons sur la voie A et sur la voie B après permutation, écrivez la méthode commande(int[] voieA, int[] voieB) de la classe Train qui retourne la commande (un objet du type String) qui réalise la permutation correspondante. Notez que la permutation voieA est quelconque et pas nécessairement la permutation 0, 1,..., n-1. On suppose que voieA et voieB sont correctes et compatibles (on peut effectivement permuter voieA en voieB).

L'algorithme consiste à composer la permutation voieB en utilisant voieA et une pile. On ne doit lire les éléments de voieB et de voieA qu'une seule fois.



This document was translated from LATEX by HEVEA.