Note : pour tous les exercices, écrivez l'algorithme et la traduction en langage Java.
Piles et files
Inversion d'une chaîne de caractères
Écrivez un algorithme permettant d'inverser une chaîne de caractère en utilisant une pile.
Palindrôme
Écrivez un algorithme permettant de déterminer si un mot est un palindrôme en utilisant une pile et une file. La chaîne de caractère qui contient le mot ne devra être parcourue qu'une seule fois.
Problème de Josephus
Josephus Flavius était un historien juif célèbre du premier siècle. Pendant la guerre juive-romaine, il a été pris au piège dans une caverne avec un groupe de 40 soldats cernés par des Romains. La légende dit que, préférant la mort à la capture, les Juifs décidèrent de former un cercle et de tuer la troisième personne vivante rencontrée en suivant le parcours autour du cercle, et ceci jusqu'à ce qu'il ne reste qu'une personne : cette personne devant alors se suicider. Josephus, peu enthousiaste à l'idée de mourir, trouva rapidement la bonne place dans le cercle afin de rester en vie.
On généralise le problème en considérant n éléments disposés en cercle, et le processus élimine chaque m-ième élément dans un parcours autour du cercle. Le but est de déterminer quel est le dernier élément.
Écrivez un algorithme résolvant le problème de Josephus, en utilisant une file. La file contiendra les entiers de 1 à n, et devra déterminer quel est le dernier entier dans la file en supprimant chaque m-ième élément.
Tri avec des piles
Dans cet exercice, on veut trier une pile d'entiers, le plus petit étant situé au sommet de la pile triée.
On définira deux fonctions annexes : la fonction depilerEmpiler(Pile,Pile) qui dépile le sommet de la première pile et l'empile sur la seconde ; et la fonction compare(Pile,Pile):booleen qui renvoie vrai si le sommet de la première pile est inférieur au sommet de la seconde.
En utilisant ces deux fonctions et trois piles (une pile d'entrée, une pile de travail et une pile pour le résultat), écrivez un algorithme de tri.
Triangle de Pascal avec une file
Le m-ième élément de la n-ième ligne du triangle de Pascal peut être défini à partir des éléments de la ligne précédente : pn, m=pn-1, m-1+pn-1, m. Sachant que la n-ième ligne comporte n éléments et que le premier et le dernier sont toujours égaux à 1, donnez un algorithme affichant les n premières lignes du triangle de Pascal en vous servant d'une file.
Structures de données
Date
Créez une structure Date comprenant trois champs entiers nommés jour, mois et annee. Adaptez les fonctions du TD 2 de P11 pour en faire des procédures manipulant votre structure Date.
Écrivez une fonctions de type Date × Date → int donnant le nombre de jours entre deux dates. Écrivez ensuite une fonction donnant la date n jours après une date passée en paramètre (n pouvant être négatif).
Quel avantage apporte l'utilisation de la structure ?
File à partir d'une liste
En vous servant des opérations add, get et remove de la classe List, créez trois procédures add, element et remove permettant d'émuler le comportement d'une file à partir d'une liste.
Formes géométriques
Définissez une structure Point représentant un point dans le plan euclidien. Écrivez les fonctions suivantes :
-
addition : Point×Point→Point qui additionne les coordonnées des deux points ;
-
soustraction : Point×Point→Point qui soustrait les coordonnées des deux points ;
-
multiplication : Point×float→Point qui multiplie les coordonnées d'un point par un scalaire ;
-
produitScalaire : Point×Point→float qui renvoie le produit scalaire des deux vecteurs ;
Créez les structures de données Cercle, Rectangle et Triangle représentant les formes géométriques correspondantes. Pour chacune des classes, écrivez une fonction donnant le périmètre et une fonction donnant l'aire d'une forme passée en paramètre.
Jeu de tarot
Créez une structure Carte permettant de représenter les cartes du jeu de tarot, contenant un champ Couleur et un champ Rang. On supposera que les rangs des cartes de couleur (de l'as au dix et du valet au roi) sont codées par un entier : le valet est codé par 11, le cavalier par 12, la dame par 13 et le roi par 14.
Écrivez une fonction estCoupe(List<Carte> pliEnCours) qui détermine si une coupe a été réalisée sur le pli en cours. Écrivez ensuite une fonction carteValide(List<Carte> pliEnCours, Carte carte, int atoutMax) qui détermine si le joueur courant peut jouer la carte donnée en fonction de son atout le plus fort donné également.
Les règles du tarot sont disponibles ici.