I. 181. Nous devons aider à la création d’un motif fabriqué par une usine de textile. Le fichier texte  grenouille.txt contient la moitié d’un motif donné par des caractères (les caractères sont séparés par des tabulations).

Lire le fichier grenouille.txt à l’aide du tableur de telle façon que la première donnée lue soit stockée dans la cellule A1 de la feuille de calcul ,,Grenouille''. (Les données contiennent aussi des cellules vides. A ces emplacements, il n’y aura pas d’élément de motif.)

La signification du contenu des cellules:

Pour l’affichage de l’image (voir la figure  ci-dessous), on doit effectuer quelques réglages. Déterminer la largeur des colonnes A:AX et la hauteur des lignes 1:50 de telle façon que les cellules soient visibles sur l’écran et qu’elles soient de forme carrée. Les données correspondantes à la moitié de l’image se trouvent dans la zone A1:Y50. La création de la deuxième moitié (symétrique) de l’image de la grenouille doit être effectuée par une fonction copiable. Pour l’affichage des couleurs, on peut appliquer une mise en forme conditionnelle.

A partir de la cellule AY:51, établir les statistiques des couleurs des éléments selon le motif. Utiliser de préférence une expression qui donnera un résultat correct après copie.

Dans la feuille de calcul ,,Grenouille_couchée'' afficher le motif de la grenouille avec une rotation de 90 degrés dans un sens au choix, à l’aide de fonctions. Dans la feuille de calcul ,,Grande_grenouille'', agrandir au double le motif  de la feuille de calcul  ,,Grenouille''.

Envoyer le classeur (181.xls, 181.ods, ...) ainsi qu’une documentation brève (181.txt, 181.pdf, ...) qui contient le nom du tableur utilisé, sa version et la description brève de la solution.

(10 points)

I. 182. Ecrire un programme simulant la circulation de voitures à un rond-point, avec affichage sur un écran en mode texte. Le rond-point relie deux routes perpendiculaires. Les routes arrivant au rond-point sont numérotées de 1 à 4, au sens contraire des aiguilles d’une montre. Les voitures sont symbolisées par ces chiffres sur l’écran en mode texte de telle façon que chaque voiture porte le numéro de la route par laquelle elle veut quitter le rond-point. Celle-ci peut-être la même par laquelle elle est arrivée: dans ce cas, la voiture fait le tour complet du rond-point et retourne dans la direction d’où elle vient.

Au début des différentes routes, dans les cases menant au rond-point, à chaque pas de la simulation, de nouvelles voitures arrivent avec une probabilité de p_i (i4) (si la case se trouvant au début de la i-ème route est libre). Les probabilités sont des nombres réels compris entre 0 et 1 que le programme reçoit par les quatre premiers arguments de la ligne de commande. Les voitures avancent à vitesse constante tant que la case précédente est libre. Si une voiture plus lente roule devant elles, alors elles prennent provisoirement la vitesse de celle-ci. La vitesse des voitures est un entier compris entre 1 et 5: si cette valeur est égale à 1, La voiture avance à chaque pas de simulation (si elle peut), si cette valeur est 5, elle essaye d’avancer seulement tous les cinquièmes pas, sinon elle reste sur place. Les voitures se trouvant dans le rond-point ont la priorité sur celles voulant s’y engager. Les voitures quittant le rond-point disparaissent au bout de la route de sortie.

Le programme doit présenter le mouvement des voitures en appliquant les probabilités reçues en entrées. La simulation doit s’arrêter en appuyant la barre d’espacement; la vitesse de la simulation doit être régulable par les touches numériques de 1 à 9.

Envoyer le code source du programme (i182.pas, i182.cpp, ...), ainsi que sa documentation brève (i182.txt, i182.pdf, ...) qui contient la description de la solution et le nom de l’environnement où le code source peut être compilé.

(10 points)

I. 183. A l'hôpital de Tataouine-les-Oies, on essaye de diminuer les frais de fonctionnement. Les draps troués ne seront plus jetés mais raccomodés. On dispose d’une machine moderne de reconnaissance de trou laquelle détermine pour chaque drap, avec un certain taux de résolution, si le tissu est intact ou troué. (Le trou ne peut se trouver au bord du drap car celui-ci est très solide à cet endroit.)

La machine donne une valeur V pour une cellule intacte, L pour une cellule trouée. Sur une zone trouée, on veut coudre un bout de tissu rectangulaire couvrant juste le manque de matière, les côtés du raccomodage étant parallèles aux côtés du drap. La zone trouée est contiguë si les cellules L sont en contact par leurs côtés, non contiguë si les cellules ne sont pas en contact ou si elles sont en contact par leurs coins. Les recouvrements entre raccomodations sont possibles.

Ecrire un programme qui, en se basant sur le fichier donné par la machine de reconnaissance de trou, affichera sur la sortie standard les numéros d’ordre des raccomodations d’un drap ainsi que les coordonnées de leurs coins supérieurs gauches et celles de leurs coins inférieurs droits (numéro de ligne, numéro de colonne, dans l’ordre), par rapport au coin supérieur gauche du drap.

Sur la ligne de commande, le paramètre en entrée du programme doit être le nom du fichier décrivant le drap. La première ligne du fichier contient un nombre entier: N (3N200) le nombre de lignes; la deuxième ligne du fichier contient M (3M200) le nombre de colonnes. Les N  lignes suivantes contiennent chacune M  caractères décrivant l’état des cellules correspondantes (V ou L).

Envoyer le code source du programme (i183.pas, i183.cpp, ...), ainsi que sa documentation brève (i183.txt, i183.pdf, ...) qui contient la description de la solution et le nom de l’environnement où le code source peut être compilé.

(10 points)

S. 34. Le roi du pays des légendes pense qu’il serait temps de marier sa fille, c’est pourquoi il fait construire par son meilleur architecte un labyrinthe plein de dragons. La main de la princesse sera obtenue par le preux chevalier qui, en entrant par n’importe quelle entrée du labyrinthe, peut en sortir avec succès par n’importe quelle autre entrée. Selon l’ordre du roi, le labyrinthe doit être créé de telle façon que le chevalier soit obligé, en choisissant n’importe quelle sortie, de couper sur son chemin un certain nombre de têtes de dragon.

Pour une décision d’une telle importance, le roi ne peut faire confiance à personne, pas même à ses serviteurs les plus fidèles. C’est pourquoi il nous a demandé d’écrire un programme qui vérifiera si les plans de labyrinthe de l’architecte correspondent à ses exigences.

Le programme doit lire les plans à partir d’un fichier et doit écrire le résultat dans un fichier. Les noms des fichiers en entrée et en sortie sont les deux paramètres de la ligne de commande.

La première ligne du fichier en entrée contient W, H  et F, séparés par des caractères d’espacement, la largeur du labyrinthe, sa hauteur et le nombre minimum F  de têtes de dragon à couper (3W,H100). Chacune des H  lignes suivantes contient W  caractères qui sont:

- Un caractère d’espacement, si la case donnée est un couloir menant à un couloir quelconque voisin

- J, B, F et L, si la case donnée est un couloir ayant une porte qui ne permet pas de quitter la case vers la droite, vers la gauche, vers le haut ou vers le bas

- *, si la case est un mur

- un chiffre N=1-9  si la case est un couloir dans lequel se cache un dragon à N  têtes qu’on doit vaincre si on est arrivé sur la case.

Un couloir se trouvant en bordure du labyrinthe est considéré comme entrée; on peut supposer que ces couloirs sont toujours vides et qu’ils sont délimités par au moins un mur.

La seule ligne de la sortie doit contenir trois nombres sous forme de , séparés par des caractères d’espacement: si le projet est correct, les trois valeurs doivent être égales à 0, sinon la ligne doit donner la description d’un itinéraire entre l’entrée A  et la sortie B  au cours duquel on ne doit couper que K (K<F) têtes de dragon. Numéroter les entrées à partir du coin supérieur gauche dans le sens des aiguilles d’une montre, en commençant par 1; s’il existe plusieurs solutions, on écrit d’abord celle avec le plus petit K, puis celle avec le plus petit  A, et celle avec la plus petite valeur de B.

Envoyer le code source du programme (s34.pas, s34.cpp, ...), ainsi que sa documentation brève (s34.txt, s34.pdf, ...) qui contient la description de la solution et le nom de l’environnement où le code source peut être compilé.

(10 points)