Énoncé du T.P. 2 de IFT 1955 (hiver 1994)

IFT 1969
Énoncé du T.P. #5
Session hiver 2015
Chargé de cours: Yves Claude
Date de remise: Au plus tard le jeudi 9 avril 2015, avant minuit.
Pénalité de retard:
Chaque jour de retard entraînera une pénalité de 10 points par jour. Aucun travail ne sera accepté après le
lundi 13 avril 2015.
Note: Le travail en équipe de deux est permis. Vous ne remettez alors qu'un travail par équipe.
Barème: 100 points (compte pour 10 % de la note finale). Bonus de 30 points pour l’exercice 3 facultatif (ce bonus vous permet
d’améliorer votre note globale des TPs, il ne s’applique pas à la note globale des examens).
.
Conseil amical: N’attendez pas quelques jours avant la remise avant de commencer... vous n’aurez pas le temps!
IMPORTANT: lisez attentivement l’énoncé du T.P.
IMPORTANT: si la remise électronique n’a pas été effectuée (que vous l’ayez tentée ou non), la note est 0.
IMPORTANT: les résultats de vos programmes doivent respecter scrupuleusement les résultats présentés dans cet énoncé.
Modalités de remise
Assurez-vous d’avoir écrit votre nom ainsi que celui de votre coéquipier (s’il y a lieu) en commentaires au début de chaque
programme. Les équipes de 2 personnes ne doivent remettre qu’une seule copie du T.P. Le T.P. doit être remis en version papier et
en version électronique pour tous les numéros.
Remise sur papier:
Remplissez une feuille de remise de T.P. (disponible sur la page Web du cours à partir du site http://wwwdesi.iro.umontreal.ca/~dift1969).
Imprimez vos programmes seulement (pas les résultats: ils seront remis électroniquement).
Brochez le tout et déposez-le dans une boîte de remise de T.P. (à côté de la porte du laboratoire X-117 situé au pavillon Roger
Gaudry ou en face du local 2197 situé au pavillon André-Aisenstadt). ATTENTION: il n’y a pas d’agrafeuse dans les salles
de labos.
Les T.P. en retard (avec pénalité) peuvent aussi être déposés dans une boîte de remise.
Remise électronique:
Double-cliquez sur l’icône Branchement sur UNIX situé sur le bureau. Branchez-vous sur Unix; c’est-à-dire entrez votre nom
d’usager et votre mot de passe Unix. À l’incitation, tapez d'abord la commande suivante: ssh remise (pour accéder à la
machine «remise» qui est la seule à accepter la commande de remise électronique). Ensuite allez dans le dossier qui contient
votre fichier à remettre avec la commande cd (par exemple, si vous avez placé vos fichiers dans le dossier devoir5, tapez cd
devoir5; de plus, la commande ls permet de voir les fichiers dans le dossier courant). Vérifiez maintenant que vos fichiers
compilent ISO C99, avec la commande suivante (doit être faite pour chaque fichier à remettre):
gcc –std=c99 –lm monfichier.c (l'extension de votre fichier doit être .c, et non pas .cpp)
Ensuite tapez la commande suivante (en supposant que vos fichiers contenant le code source s'appellent tp5no1.c, tp5no2.c,
tp5no3.c):
remise ift1969 tp5 tp5no1.c tp5no2.c tp5no3.c
Finalement tapez la commande suivante pour remettre vos fichiers de résultats: remise ift1969 tp5 restuplets.txt
determinants.txt navale.txt
Faites bien attention à respecter les majuscules et les minuscules. Si les noms de vos dossiers ou fichiers contiennent des
espaces, il faut alors placer le nom entre guillemets ( ) avec les différentes commandes (cd, gcc, remise).
TP5 – IFT 1969
Hiver 2015
Page 1 de 9
À tout moment, vous pouvez vérifier quels fichiers vous avez remis en tapant la commande: remise -v ift1969 tp4
La liste des fichiers remis sera alors affichée (avec notre exemple, vous devez voir les fichiers tp5no1.c, tp5no2.c, tp5no3.c,
restuplets.txt, determinants.txt, navale.txt dans la liste; si vous ne les voyez pas, c'est que la commande remise a échoué). Si tout
c’est bien passé, faites exit, puis fermez la fenêtre de Telnet. Autrement, recommencer la procédure avec l´aide d´un démonstrateur.
La remise électronique prend note du jour de la remise; les T.P. peuvent donc être remis en retard (avec pénalité).
Vous pouvez faire une remise électronique autant de fois que vous le voulez, mais respectez la règle suivante: remettez toujours
votre T.P. du même compte. Chaque nouveau fichier remis écrase le fichier du même nom remis auparavant; seule la dernière
version sera alors conservée.
Matière exercée: Les fonctions. Les tableaux. Les fichiers.
n
1. Écrire
un
programme
qui
trouve
les
n-tuplets
ti
(t1 ,..., tn ) tel que
s , avec
0
ti
m
et
où
i 1
tj
t k ,1
j
n,1 k
n , à partir des paramètres m, n et s (ne paniquez pas, je vais clarifier). Supposons que les valeurs
lues pour m, n et s sont respectivement les entiers 9, 3 et 15. Nous voulons donc trouver tous les triplets (puisque n = 3) qui
forment l'addition du nombre 15 (puisque s = 15) en utilisant les entiers 1 à 9 (puisque m = 9) sans utiliser plus d'une fois le
même entier (c'est la signification de la condition t j t k ). Ainsi, pour cet exemple, nous obtiendrons la suite des huit triplets
suivants:
(1, 5, 9), (1, 6, 8), (2, 4, 9), (2, 5, 8), (2, 6, 7), (3, 4, 8), (3, 5, 7), (4, 5, 6)
Ce petit exemple ayant illustré ce que le programme doit trouver ne signifie pas pour autant que tout soit devenu simple.
Remarquez que vous pouvez arrêter la lecture ici et tentez de résoudre cet amusant problème (il est possible d'ailleurs que vous
trouviez un meilleur algorithme que celui qui est proposé). Toutefois, pour ceux et celles qui n'aiment trop se casser la tête, voici
un algorithme (donné en pseudo-code) qui va vous aider à réaliser le programme. Cet algorithme est basé sur la création ordonnée
de n-tuplets, les éléments respectifs d'un n-tuplet étant placés en ordre croissant.
Les symboles employés dans l'algorithme ont la signification suivante:
a: vecteur représentant les sommes partielles maximales
b: vecteur représentant les sommes partielles du tuplet courant
c: vecteur représentant l'essai courant d'un tuplet (appelé tuplet courant)
p: vecteur représentant l'essai précédent d'un tuplet (appelé tuplet précédent)
d: position de transition dans le tuplet courant
t: somme partielle des éléments placés dans le tuplet courant
i, j: indices sur les différents vecteurs utilisés
TP5 – IFT 1969
Hiver 2015
Page 2 de 9
{calcul des sommes partielles maximales: petite fonction no 1}
pour i de 1 à n: ai 0; pour j de m-i+1 à m: ai ai+j;
{initialisation du tuplet précédent}
pour i de 1 à n-2: pi i;
pn-1 n-2;
{initialisation de la position de transition}
d n-1;
{génération de tous les tuplets possibles}
répéter
{tenter de former un tuplet valide: petite fonction no 2}
t 0;
pour i de 1 à n-1
si i<d alors: ci pi;
sinon si i=d alors: ci pi+1;
sinon: ci ci-1+1;
t t+ci;
cn s-t;
{mettre à jour le tuplet précédent}
pour i de 1 à n: pi ci;
{reculer la position de transition si le tuplet est incohérent}
si cn cn-1 alors: d d-1;
sinon si cn m alors {c est un n-tuplet valide}
imprimer le vecteur c; {petite fonction no 3}
d n-1;
sinon {calculer la nouvelle position de transition: petite fonction no 4}
pour i de 1 à n: bi 0; pour j de n-i+1 à n: bi bi+cj;
pour i de n à 1: si bi>ai alors: d n-i; sortir de la boucle;
tantque d>0
Cet algorithme sera placé dans sa propre fonction et celle-ci fera appel à quatre autres fonctions:
- une petite fonction (1) sera utilisée pour l'étape «calcul des sommes partielles maximales»
- une petite fonction (2) sera utilisée pour l'étape «tenter de former un tuplet valide»
- une petite fonction (3) sera utilisée pour l'impression du tuplet valide
- finalement, une petite fonction (4) sera utilisée pour l'étape «calculer la nouvelle position de transition»
Le rôle de la fonction principale main en est un de chef d'orchestre: elle s'occupe d'ouvrir et de fermer les fichiers requis, elle
appelle les différentes fonctions nécessaires à la réalisation de la tâche du programme. Le fichier maintuplet.c disponible sur les
pages Web vous montre ce que doit être une bonne fonction principale: elle vous servira en même temps de bon point de départ
pour la réalisation de ce premier exercice.
Remarque: Le pseudo-code permet d'exprimer de façon succincte la description d'un algorithme: il ne dépend pas du langage de
programmation utilisé. Il convient donc de l'adapter lors de la traduction dans le langage de programmation choisi.
Dans cet algorithme, les vecteurs utilisés suivent la convention mathématique usuelle, c'est-à-dire que les éléments
du vecteur sont numérotés de 1 à n. En langage C, les éléments d'un tableau sont numérotés de 0 à n-1, il faut donc
veiller à modifier les bornes des boucles. Lors de la traduction, il faut porter particulièrement attention à la variable d
qui représente une position dans le vecteur c.
Remarque: Remplacez les symboles utilisés dans l'algorithme par des noms plus significatifs. Par exemple, le vecteur c pourrait
être appelé tupletCourant ou tupCour, le paramètre s pourrait être appelé somme, etc.
Remarque: Vous pouvez considérer que tous les vecteurs de l'algorithme ont une taille maximale de 20 éléments.
TP5 – IFT 1969
Hiver 2015
Page 3 de 9
Les données sont dans le fichier dontuplets.txt disponible sur les pages Web et chaque ligne du fichier comporte 3 entiers: le
premier entier est m qui indique la suite consécutive de nombres qui peuvent former un n-tuplet, le second entier est n qui indique
la taille du n-tuplet et, finalement, le dernier entier est s qui indique la somme formée par les nombres du n-tuplet.
Les sorties du programme seront envoyées dans le fichier restuplets.txt. Voici les sorties attendues par votre programme:
Suite des tuplets formes de 3 termes dont la somme est 15
et dont chaque terme est <= 9
Tuplet
Tuplet
Tuplet
Tuplet
Tuplet
Tuplet
Tuplet
Tuplet
no.
no.
no.
no.
no.
no.
no.
no.
1:
2:
3:
4:
5:
6:
7:
8:
(
(
(
(
(
(
(
(
1,
1,
2,
2,
2,
3,
3,
4,
5,
6,
4,
5,
6,
4,
5,
5,
9)
8)
9)
8)
7)
8)
7)
6)
Suite des tuplets formes de 4 termes dont la somme est 15
et dont chaque terme est <= 9
Tuplet
Tuplet
Tuplet
Tuplet
Tuplet
Tuplet
no.
no.
no.
no.
no.
no.
1:
2:
3:
4:
5:
6:
(
(
(
(
(
(
1,
1,
1,
1,
1,
2,
2,
2,
2,
3,
3,
3,
3,
4,
5,
4,
5,
4,
9)
8)
7)
7)
6)
6)
Remarque: Pour la sortie, nous vous suggérons la spécification de conversion %2d pour le numéro de n-tuplet et %2d pour les
termes du n-tuplet.
Remarque: En phase de développement du programme, nous vous suggérons d'imprimer sur stdout, cela facilitera grandement
le débogage de votre programme (autrement, vous passerez votre temps à ouvrir le fichier restuplets.txt pour vérifier
les résultats).
Remarque: Votre programme n'a pas besoin de valider les paramètres lus dans le fichier. Ceux-ci sont toujours cohérents et
respectent les contraintes suivantes:
- n 2
- m n
n
-
k
s : autrement dit, la somme des n plus petits entiers consécutifs est inférieure ou égale à la somme s
k 1
spécifiée; ainsi, si m = 9, n = 3 et s = 5, il est impossible de former un triplet puisque le plus petit triplet est (1,2,
3) dont la somme est 6 (donc s est trop petit pour le paramètre n considéré)
m
-
k
s : autrement dit, la somme des n plus grands entiers consécutifs est supérieure ou égale à la somme
k m n 1
s spécifiée; ainsi, si m = 9, n = 3 et s = 26, il est impossible de former un triplet puisque le plus grand triplet est
(7, 8, 9) dont la somme est 24 (donc s est trop grand pour les paramètres m et n considérés)
TP5 – IFT 1969
Hiver 2015
Page 4 de 9
2. Écrire un programme C qui lit les coefficients entiers de matrices et qui calcule le déterminant de celles-ci. Bien entendu,
les matrices sont carrées, c’est-à-dire de dimension n n.
Principes généraux pour le calcul du déterminant d'une matrice n n
Soit la matrice M suivante:
a11
a21
a12  a1n
a22  a2 n

an1
  
an 2  ann
Le déterminant de la matrice M est représenté de la façon suivante:
det(M)
a11
a21
a12  a1n
a22  a2 n

an1
  
an 2  ann
Le déterminant d'une matrice carrée 1 1 est calculé ainsi:
a11
a11
Le déterminant d'une matrice carrée 2 2 est calculé ainsi:
a 11
a 21
a 12
a 22
a 11 a 22
a 12 a 21
Le déterminant d'une matrice carrée 3 3 est calculé ainsi:
a11
a 21
a12
a 22
a13
a 23
a31
a32
a33
a11 (a 22 a33
a 23 a32 ) a12 (a 21 a33
a 23 a31 ) a13 (a 21 a32
a 22 a31 )
Le déterminant d'une matrice M, notée det(M), peut donc être défini de façon récursive:
n
( 1) j 1 a1 j det(M[1,j])
det(M) =
j 1
avec la notation det(M[1,j]) signifiant une nouvelle matrice carrée n-1 n-1 obtenue de M en éliminant sa première ligne et sa
jième colonne. On convient qu'une matrice vide (de dimensions n=0) a un déterminant de 1.
La seule difficulté pour écrire une fonction récursive qui calcule le déterminant est la construction de la nouvelle matrice.
Il suffit de déclarer dans la fonction récursive une matrice de taille maximale 12 12 et de se servir de cette matrice
(après l'avoir construite selon la règle expliquée ci-dessus) comme argument lors de l'appel récursif.
TP5 – IFT 1969
Hiver 2015
Page 5 de 9
Comme mentionné dans le premier exercice, le rôle de la fonction principale main en est un de chef d'orchestre: elle s'occupe
d'ouvrir et de fermer les fichiers requis, elle appelle les différentes fonctions nécessaires à la réalisation de la tâche du programme.
Dans cet exercice, quelles sont ces fonctions nécessaires? Essentiellement, il y a en au moins trois:
- une fonction qui lit la matrice
- une fonction (récursive) qui calcule le déterminant
- une fonction qui écrit la matrice
Le fichier matrices_entiers.txt disponible sur les pages Web contient, sur sa première ligne, une valeur entière
représentant la taille d’une matrice n n. Par la suite, on retrouve n lignes de données avec n colonnes d'entiers. La taille
de la matrice ne peut dépasser 12 12.
Les sorties du programme seront envoyées dans le fichier determinants.txt. Voici les sorties attendues par votre programme:
Matrice de dimensions 2 x 2
3 4
2 0
Le determinant de la matrice est -8
Matrice de dimensions 2 x 2
1 0
3 4
Le determinant de la matrice est 4
Matrice de dimensions 3 x 3
0 3 1
0 3 3
0 4 2
Le determinant de la matrice est 0
Matrice de dimensions 4 x 4
0 4 3 3
1 4 4 4
4 3 1 2
0 3 1 3
Le determinant de la matrice est 37
etc.
Remarque: Tous les calculs peuvent être faits avec des entiers (int) puisque le fichier contient des matrices avec des petits
coefficients qui ne causeront pas de dépassement de capacité.
Remarque: Pour la sortie, nous vous suggérons la spécification de conversion %3d pour les coefficients de la matrice.
Remarque: En phase de développement du programme, nous vous suggérons d'imprimer sur stdout, cela facilitera grandement
le débogage de votre programme (autrement, vous passerez votre temps à ouvrir le fichier determinants.txt pour
vérifier les résultats).
3. Écrire un programme C capable de produire des configurations de bataille navale dans un fichier appelé navale.txt. Avant d'aller
plus loin, il faut expliquer ce qu'est une configuration de bataille navale. La bataille navale est un jeu célèbre qui se joue à 2
joueurs. Chaque joueur dispose d'une grille carrée de 100 cases dont les colonnes sont numérotées de 1 à 10 et dont les lignes
sont marquées 'a' à 'j'. Avant le début de la partie, chaque joueur doit placer 5 navires sur la grille: un porte-avions, un
croiseur, un destroyer, une vedette et un sous-marin. Chaque navire occupe un nombre différent de cases (un navire peut être
placé horizontalement ou verticalement sur la grille, au choix du joueur):
TP5 – IFT 1969
Hiver 2015
Page 6 de 9
le porte-avions occupe 5 cases
le croiseur occupe 4 cases
le destroyer occupe 3 cases
la vedette occupe 2 cases
le sous-marin occupe 1 seule case
La suite du jeu n'a pas d'importance pour ce T.P. Une configuration de bataille navale, c'est simplement les 5 navires placés sur
une grille 10x10.
Voici un exemple d'une configuration de bataille navale:
a
b
c
d
e
f
g
h
i
j
1
V
-
2
V
-
3
P
-
4
P
S
5
P
C
C
C
C
-
6
P
-
7
P
-
8
-
9
D
D
D
-
10
-
La lettre P désigne le porte-avions, la lettre C désigne le croiseur, la lettre D désigne le destroyer, la lettre V désigne la vedette et la
lettre S désigne le sous-marin. Le caractère '-' indique que la case est libre de tout navire. Votre programme doit imprimer une
configuration en respectant ces conventions (il doit aussi imprimer les numéros de colonnes et les marques de lignes, comme dans
l'exemple ci-dessus).
Pour construire une configuration, il faut utiliser un tableau de caractères à 2 dimensions. Votre programme doit placer les navires
dans l'ordre décroissant de leur taille (on place donc en premier le porte-avions et on termine par le sous-marin). De plus, chaque
nouveau navire placé ne doit pas empiéter sur la zone de sécurité des autres navires. La zone de sécurité est définie comme les cases
adjacentes au navire placé. Voici un exemple d'une zone de sécurité de 2 cases pour le porte-avions (la lettre z désigne la zone de
sécurité):
a
b
c
d
e
f
g
h
i
j
1
z
z
P
z
z
-
2
z
z
P
z
z
-
3
z
z
P
z
z
-
4
z
z
P
z
z
-
5
z
z
P
z
z
-
6
z
-
7
z
-
8
-
9
-
10
-
Le placement d'un navire s'effectue en deux étapes. La première étape consiste à choisir la position du début du navire. Cette
position s'obtient avec 2 entiers choisis au hasard entre 0 et 9 (un entier représente le numéro de ligne et l'autre représente le numéro
de colonne). Si la position obtenue ne convient pas (soit parce qu'elle correspond à une position déjà occupée par un autre navire,
soit parque qu'elle coïncide avec une des cases d'une zone de sécurité), on doit recommencer. La seconde étape consiste à choisir
une direction pour déterminer comment sera placé le reste du navire (cette étape est évidemment bien inutile dans le cas du sousmarin). On choisit pour cela au hasard un entier entre 0 et 3 avec les conventions suivantes: 0 indique que le reste du navire occupe
les cases situées à droite de la position initiale; 1 indique que le reste du navire occupe les cases situées en bas de la position initiale;
2 indique que le reste du navire occupe les cases situées à gauche de la position initiale; 3 indique que le reste du navire occupe les
cases situées en haut de la position initiale. Si la direction ne convient pas (soit parce que la fin du navire excède les limites de la
grille, soit parce que la fin du navire atteint un autre navire ou sa zone de sécurité), on passe à la direction suivante. Si aucune des 4
directions ne convient, on doit retourner à la première étape et choisir une nouvelle position.
TP5 – IFT 1969
Hiver 2015
Page 7 de 9
Exigences pédagogiques:
Dans votre programme, il vous faut obligatoirement trois fonctions (en plus de la fonction principale main):
-
la première fonction sert à initialiser les cases de la grille avec le caractère '-' (toutes les cases sont libres);
la seconde fonction place les navires dans la grille;
la troisième fonction sert à imprimer la configuration de bataille navale telle que présentée ci-dessus.
Vous devez initialiser le germe pour la génération des nombres aléatoires avec la valeur 1969, comme ci-dessous:
#include <stdlib.h>
...
/* initialiser le germe pour la génération des nombres aléatoires
(à faire 1 seule fois au début du programme) */
srand(1969);
...
À noter l’importance de la directive #include <stdlib.h> qui permet l’utilisation des fonctions standards srand et rand
(exactement comme la directive #include <stdio.h> permet l’utilisation des fonctions standards scanf et printf). Tel
que mentionné dans le commentaire, la fonction srand permet d’initialiser le germe pour la génération des nombres aléatoires.
Évidemment, si on utilise toujours le même nombre pour initialiser le germe (ici l’entier 1969), on obtiendra toujours la même suite
de nombres « aléatoires » (c’est pour cela qu’en programmation, on parle plutôt de nombres « pseudo aléatoires »). Ce
comportement apparemment non souhaitable est en fait très utile pour la mise au point des programmes (en effet, lorsqu’un bogue
survient dans un programme, il est plus facile à repérer si on peut reproduire exactement le cheminement avec les mêmes nombres)
et, accessoirement, pour la correction des travaux pratiques...
Remarques:
-
Pour générer au hasard un entier entre 0 et 9, faire: rand() % 10;
-
Pour générer au hasard un entier entre 0 et 3, faire: rand() % 4;
-
Vous pouvez définir plus de 3 fonctions si vous en avez besoin.
-
Pour faciliter la mise au point du programme, il est souvent plus simple d’écrire les résultats sur la sortie standard stdout
(la console d’écran). Lorsque le programme est correct, il suffit alors de remplacer le premier argument stdout du
fprintf par l’argument approprié et le tour est joué.
-
Voici l’en-tête suggérée de chacune des fonctions (on suppose #define NBCOL 10):
void Initialise(char grille[][NBCOL])
void Place(char grille[][NBCOL])
void Imprime(FILE* fEcr, char grille[][NBCOL])
Données pour la remise:
Deux zones de sécurité de 1 case et deux zones de sécurité de 2 cases. Votre programme n’a pas besoin de lire ces données du
clavier. Il doit simplement faire une boucle sur ces différents nombres: à chaque tour de boucle, il suffit d’appeler les 3 fonctions
mentionnées ci-dessus.
Pour obtenir de l´aide en dehors des périodes de travaux pratiques:
Envoyez vos courriels à l'adresse électronique suivante: [email protected]
En procédant ainsi, vous augmentez vos chances d´avoir une réponse dans les plus brefs délais.
TP5 – IFT 1969
Hiver 2015
Page 8 de 9
Barème de correction: Chaque numéro vaut 50 points; l’exercice 3 facultatif vaut 30 points indiqués entre ().
Commentaires: 10 points (5 points)
Description du programme (auteurs, but):
Description des fonctions et des paramètres:
Description des constantes et des variables:
Programmation: 25 points (15 points)
Utilisation des constantes et/ou des variables:
Identificateurs significatifs:
Indentation et lisibilité:
Algorithme:
2 points (1 point)
6 points (3 points)
2 points (1 point)
3 points (2 points)
3 points (2 points)
3 points (2 points)
16 points:12 points pour les fonctions et 4 points pour la fonction principale
(9 points pour les fonctions)
Résultats: 15 points (10 points)
Chaque groupe correct de résultats:
0.75 point (2.5 points)
Varia:
Programme qui ne compile pas
Pas de remise électronique
Pas de remise papier
Programmation C non ANSI C99
-50 points (-30 points)
-50 points (-30 points)
-25 points (-15 points)
-25 points (-15 points)
Amusez-vous bien!
Bonne chance et bon travail!
Équipe du IFT 1969, hiver 2015.
TP5 – IFT 1969
Hiver 2015
Page 9 de 9

Download Report