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).
Solution