Version 1.3 du 22 mars 2023
(du 13 mars 2023, 12h00, au 26 mars, 23h59.)
Ce devoir noté consiste à écrire un programme C permettant répartir des containers à être livrés par des camions (allocation de ressources).
Nous vous demandons d’écrire tout votre code dans un seul
fichier nommé trucks.c
sur la base d’un fichier fourni, à
compléter.
Indications : Si un comportement ou une situation
donnée n’est pas définie dans la consigne ci-dessous, vous êtes libre de
définir le comportement adéquat. On considérera comme comportement
adéquat toute solution qui ne viole pas les contraintes données et qui
ne résulte pas en un crash du programme.
Par ailleurs, n’hésitez pas à regarder le code trucks.c
fourni pour clarifier la présente donnée si nécessaire.
Instructions :
Cet exercice doit être réalisé individuellement ! L’échange de code relatif à cet exercice noté est strictement interdit ! Cela inclut la diffusion de code sur le forum ou sur tout site de partage.
Le code rendu doit être le résultat de votre propre production. Le plagiat de code, de quelque façon que de soit et quelle qu’en soit la source sera considéré comme de la tricherie (et peut même, suivant le cas, être illégal et passible de poursuites pénales).
En cas de tricherie, vous recevrez la note « NA » pour l’entièreté de la branche et serez de plus dénoncés et punis suivant l’ordonnance sur la discipline.
Vous devez donc également garder le code produit pour cet exercice dans un endroit à l’accès strictement personnel.
Le fichier (source !) trucks.c
à fournir comme rendu de
ce devoir ne devra plus être modifié après la date et heure limite de
rendu.
Veillez à rendre du code anonyme : pas de nom, ni de numéro SCIPER, ni aucun identifiant personnel d’aucune sorte !
Utilisez le site Moodle du cours pour rendre votre exercice.
Vous avez jusqu’au 26 mars, 23:59 (heure du site Moodle du cours faisant foi) pour soumettre votre rendu. Aucun délai supplémentaire ne sera accordé.
Je tiens également à souligner que l’objectif de ce devoir n’est pas tant de vous évaluer que de vous entraîner. C’est pour cela que le coefficient de ce devoir est assez faible (10%). C’est également dans cet esprit qu’il a été conçu : de façon très progressive (de plus en plus difficile). Utilisez le donc comme un entraînement indicatif (sur lequel vous aurez un retour) en travaillant à votre niveau dans une durée qui vous semble raisonnable pour les crédits de ce cours (au lieu d’essayer de tout faire dans un temps déraisonnable). Ce coefficient (1 sur 10) n’est pas représentatif de la charge de travail (qui peut beaucoup varier à ce niveau d’un(e) étudiant(e) à l’autre), mais bien pour vous donner l’occasion d’avoir un premier retour sur votre niveau de programmation en C, sans prendre trop de « risques ».
Le but est donc de répartir, avec un algorithme très simple (II.4) un ensemble de containers sur un ensemble de camions en respectant leurs contraintes (allocation de ressources).
Remarques importantes :
toutes les struct
devront être systématiquement
passées par référence, constante lorsque cela est possible,
non-constante lorsque cela est nécessaire ; aucun passage par valeur de
struct
;
tous les tableaux et « chaînes de caractères » de ce devoir sont
de taille fixe, dont la taille maximale est donnée dans le code
trucks.c
fourni et spécifiée ci-dessous ; en particulier,
toutes les « chaînes de caractères » sont des tableaux de
MAX_NAME
caractères.
Les containers (type Container
) à répartir sont
représentés par leur nom (name
) et leur caractéristique
(f
). Une caractéristique (type Features
) est
représentée par un volume (volume
, de type entier) et un
« temps de traitement » (time
, de type double
)
du container pour sa livraison (chargement, déchargement, manutention,
etc.).
Dans le fichier trucks.c
fourni :
[2 points] définissez le type
Features
correspondant à la description ci-dessus et
compatible avec le main()
fourni ; ce main()
ne doit pas être modifié ;
[2 points] définissez ensuite le type
Container
correspondant à la description précédente et
compatible avec le main()
fourni ; une seule
caractéristique suffit par container ;
[2 points] définissez enfin une fonction
container_display()
qui prend en paramètres un fichier et
un container et l’affiche (dans le fichier) en respectant strictement le
format suivant :
nom (V = volume m^3, t = temps min.),
Par exemple, pour le premier container déclaré dans le
main()
fourni, la fonction container_display()
donne :
lot1 (V = 35 m^3, t = 25 min.),
Un camion (type Truck
) est représenté par :
son nom (name
),
le nombre de zones qu’il dessert
(nb_areas
) ;
un tableau (areas
) de MAX_AREAS
zones à
desservir, représentées ici très simplement par uniqument un temps
d’accès en format double
;
le nombre de containers qu’il transporte
(nb_containers
) ;
un tableau (containers
) de
MAX_CONTAINERS
containers ;
sa capacité totale en volume (capacity
, nombre
entier).
[4 points] Définissez le type Truck
correspondant à la description précédente et compatible avec le
main()
fourni ;
[7 points] définissez ensuite une fonction
truck_display()
qui prend en paramètres un fichier et un
Truck
et affiche ses propriétés comme dans l’exemple
suivant (correspondant au premier Truck
du
main()
fourni) :
Camion camion1 :
Capacité (m^3) : 90
Zones (min.) : 160, 140, 195,
vide
Si ce camion transportait les deux containers lot1
et
lot4
(cf. main()
fourni), alors son affichage
serait :
Camion camion1 :
Capacité (m^3) : 90
Zones (min.) : 160, 140, 195,
Containers :
- lot1 (V = 35 m^3, t = 25 min.),
- lot4 (V = 15 m^3, t = 35 min.),
trucks_array_display()
qui prend en paramètres un fichier
et un tableau de Truck
(et sa taille, cela va de soit et ne
sera plus rappelé !) et affiche chacun des camions de ce tableau.On vous demande maintenant de calculer le temps moyen d’accès aux zones desservies par un camion. Il s’agit simplement de la moyenne (arithmétique) des (temps d’accès à chacune des) zones.
Définissez une fonction available_time()
qui prend en
paramètres un camion et retourne son temps disponbible comme étant le
temps de travail total (constante fournie WORKING_TIME
)
moins le temps moyen d’accès sur zone fois le nombre moyen de
zones (constante fournie AVG_AREAS
).
Par exemple pour le premier camion du main()
fourni
("camion1"
), son temps disponible est de 150 minutes :
son temps moyen d’accès sur zone est de 165 minutes : (160 + 140 + 195) / 3 = 165 ;
son temps disponible est alors : WORKING_TIME
-
AVG_AREAS
* 165 = 480 - 2 * 165 = 150.
On vous demande enfin d’écrire une fonction qui va essayer d’allouer chaque container d’une liste de containers fournie à un camion d’une liste de camions fournie.
[4 points] Pour commencer, définissez la
fonction-outil add_container()
qui prend un
Truck
et un Container
et qui retourne un
int
. S’il reste encore de la place, elle ajoute le
container au camion et retourne 1 et sinon elle ne fait rien et retourne
0.
Ensuite, l’algorithme d’allocation (simple) est le suivant :
[4 points] On mémorise les caractéristiques
disponibles (volume, temps) offertes au départ par chaque camion. Pour
un camion vide, ce sont sa capacité en volume et son temps moyen
d’accès, calculé au moyen de la fonction available_time()
précédente (celle-ci sera calculée une fois pour toute et non pas
recalculée à chaque fois).
[10 points] Pour chaque container, on décide de
l’affecter au premier camion trouvé dans la liste tel que son volume et
son temps restants soient supérieurs ou égaux aux caractéristiques du
container.
Si tel est le cas, le container est affecté au camion en question et ses
caractéristiques disponibles mémorisées sont remises à jour simplement
en soustrayant les caractéristiques du container à celles encore
disponibles du camion (c.-à-d. celles mémorisées pour lui à ce
stade).
Définissez pour cela une fonction allocate()
qui prend
en paramètre un tableau de Truck
et un un tableau de
Container
(cf le main()
fourni). Cette
fonction doit retourner le nombre de containers correctement affectés à
des camions.
Si vous avez tout fait correctement et compilez et exécutez le code fourni (et complété), vous devriez obtenir :
Camion camion1 :
Capacité (m^3) : 90
Zones (min.) : 160, 140, 195,
vide
Camion camion2 :
Capacité (m^3) : 110
Zones (min.) : 170, 140, 100, 50,
vide
Camion camion3 :
Capacité (m^3) : 180
Zones (min.) : 110, 145, 100, 150.5,
vide
=== Répartition ===
Après affectation de 6 containers :
Camion camion1 :
Capacité (m^3) : 90
Zones (min.) : 160, 140, 195,
Containers :
- lot1 (V = 35 m^3, t = 25 min.),
- lot4 (V = 15 m^3, t = 35 min.),
Camion camion2 :
Capacité (m^3) : 110
Zones (min.) : 170, 140, 100, 50,
Containers :
- lot3 (V = 25 m^3, t = 215 min.),
- lot6 (V = 65 m^3, t = 35 min.),
Camion camion3 :
Capacité (m^3) : 180
Zones (min.) : 110, 145, 100, 150.5,
Containers :
- lot2 (V = 125 m^3, t = 105 min.),
- lot8 (V = 25 m^3, t = 100 min.),
N’hésitez pas à créer d’autres fonctions utilitaires si nécessaire.
Tout votre code et toutes vos fonctions doivent être robustes tant
que faire se peut (c.-à-d. sauf avis contraire). Votre code sera évalué
avec d’autres appels (et d’autres main()
).
Pensez à tester correctement chacune des fonctionnalités implémentées à chaque étape et avant de passer à l’étape suivante. Cela vous évitera bien des tracas.
A noter que le main()
fourni peut prendre un nom de
fichier en argument. Par exemple :
./trucks test.txt
Il écrit alors les résultats dans ce fichier. Vérifiez que c’est bien
le cas, c.-à.-d. que vos affichage sur le terminal
(./trucks
sans argument) correspondent au contenu du
fichier ainsi créé.