Pendant une journée, un bureau de poste reçoit n clients. Chaque client i est caractérisé par deux choses : l'heure d'arrivée ai et la durée des opérations di. Ces données sont du type float. On dispose du tableau clients qui les donnent sous forme de couples (ai,di) triés dans l'ordre croissant des ai (ordre d'arrivée au bureau de poste).
Le but de l'exercice est de calculer combien de guichets doivent être ouverts pour n'avoir jamais d'attente.
1) On suppose qu'il n'y a qu'un guichet. Ecrivez une fonction heures_depart qui à partir du tableau clients rend le tableau departs indiquant l'heure de départ de chaque client. Indice : il y a forcément une récurrence.
On crée d'abord un tableau de flottants ayant le même nombre d'éléments que clients. La fonction qui remplit ce tableau va procéder ainsi :
Si on s'intéresse au premier client, l'heure du départ est forcément a1 + d1
Sinon, pour un client i on a deux choix. Soit lorsqu'il arrive le guichet est déjà occupé par (i-1). Alors il doit attendre que (i-1) parte donc l'heure de départ de i sera départ(i-1) + di. Si le guichet est libre à l'arrivée de i, alors l'heure de départ de i est simplement ai + di.
let heures_departs clients =
let n = Array.length clients in
let departs = Array.make n 0. in
let rec aux i =
if i = n then departs
else if i = 0 then (departs.(i) <- (fst clients.(i)) +. (snd clients.(i)); aux 1)
else if fst clients.(i) > departs.(i-1) then (departs.(i) <- (fst clients.(i)) +. (snd clients.(i)); aux (i+1))
else (departs.(i) <- departs.(i-1) +. (snd clients.(i)); aux (i+1))
in aux 0;;
2) Dans cette question, on suppose qu'il y a assez de guichets. Ecrivez une fonction qui prend en argument le tableau clients et rend le nombre de guichets occupés à l'arrivée de chaque client (sous forme d'un tableau d'entiers).
On doit modifier la fonction précédente. En effet, on suppose à présent qu'il y a assez de guichets. Du coup, lorsque quelqu'un arrive, il a un guichet. Alors le départ de i se fait à l'heure ai + di.
let heures_departs2 t =
let n = Array.length t in
let departs = Array.make n 0. in
let rec aux i =
if i = n then departs
else (departs.(i) <- (fst t.(i)) +. (snd t.(i)); aux (i+1))
in aux 0;;
Du coup, lorsqu'un client i arrive, le nombre de guichets occupés correspond au nombre de clients j arrivés avant ai qui partiront après ai, soit le nombre de j tels que aj < ai et départs(j) > ai. Du coup, on va parcourir les éléments du tableau avant i (ce sont exactement ceux pour lesquels aj < ai puisque les éléments sont triés) et compter ceux pour lesquels départs(j) > ai.
Il y a un cas particulier pour i = 0 : pour celui-ci on sait que la réponse est 0. On va donc remplir le tableau initial de 0, et passer directement au client 1. Je fais ici une version impérative mais une récurrence est possible.
let guichets_occupes t =
let n = Array.length t in
let departs = heures_departs2 t and resultats = Array.make n 0 in
for i = 1 to (n-1) do
let compteur = ref 0 in
for j = 0 to (i-1) do
if departs.(j) > fst t.(i) then incr compteur else ()
done;
resultats.(i) <- !compteur
done;
resultats;;
3) Déduisez-en une fonction qui prend en argument le tableau clients et rend le nombre de guichets à ouvrir pour éviter toute attente. Vous pouvez tester avec le tableau [|8.,0.2;8.5,0.5;9.,0.5;9.2,0.5;11.5,0.3;11.8,0.5;14.,0.5;15.,0.7|], avec lequel 2 guichets sont nécessaires.
Solution
> Haut de la page
