Informatique T.D 1

Marie-Pierre Béal et Laurent Moll

Quelques adresses WEB pour trouver des informations sur : les TDs:

http://www-igm.univ-mlv.fr/~beal/index.html

la bibliothèque MacLib:

http://lix.polytechnique.fr/~chassign/MACLIB/maclib intro.html

le polycopié, langage Pascal et fonctions graphiques:

http://www.polytechnique.fr/poly/~www/poly/

L’objectif pour ce premier TP est de se familiariser avec le logiciel Think ou Delphi Pascal (édition, compilation, exécution). L’exercice 1 consiste en un tri d’objets graphiques. N’abordez les exercices 2 et 3, qui demandent plus de réflexion, que s’il vous reste du temps.

Exercice 1.— On demande de tracer le bord d’un rectangle représentant une fenêtre de jeu. On dessinera un petit carré gris et un petit carré noir sur le bord haut et gauche. Lorsqu’on clickera sur le bouton noir, le processus s’arrêtera. Lorsque l’on clickera sur le bouton gris, on lancera le tri et l’affichage des objets triés. Les objets, quels sont-ils ? Il s’agit de rectangles que l’on saisira par un click à la souris. On clickera d’abord une fois pour saisir le point du bord haut et gauche, puis en maintenant le bouton de la souris enfoncé, on glissera vers le point du bord bas et droit. Le relachement définira le deuxième point. Les rectangles seront stockés dans un tableau. On fera un tri simple suivant l’abscisse du bord gauche, en cas d’égalité on prendra en considération l’ordonnée du bord haut. On affichera les rectangles pleins lors de la saisie et aussi après un tri, en suivant l’ordre obtenu. Programmez de façon modulaire et progressive. Pour programmer le tri, triez une table d’objets de type générique ”élément”. Vos procédures de tri doivent être réutilisables dans un autre programme.

Exercice 2.— On appelle mot une suite de lettres. Par exemple abxabbyzabta est un mot. On appelle sous-mot une sous-suite de lettres d’un autre mot. Ainsi le mot xyzt est un sous-mot de abxabbyzabta. On se donne deux mots, l’un de longueur n: x[1]...x[n], l’autre de longueur m: y[1]...y[m] et on cherche un plus long sous-mot commun. On construit pour cela un tableau t de taille nm. La valeur de t[i, j] est la longueur d’un plus long sous-mot commun à x[1]...x[i] et y[1]...y[j]. Exprimer t[i, j] en fonction de t[i − 1, j], t[i − 1, j − 1], t[i, j − 1]. Ecrire un programme de calcul de t. Afficher la longueur d’un plus long sousmot commun. En déduire un programme de calcul d’un plus long sous-mot commun à deux mots.

Exercice 3.— On considère un tableau t de n entiers (positifs, négatifs ou nuls). Trouver un algorithme en O(n) permettant trouver une suite contiguë t[i]t[i+1]...t[j] telle que t[i]+t[i+1]+...+t[j] soit maximale. Ecrire un procédure pour le faire. On affichera le maximum cherché.