RECHERCHE :
Bienvenue sur le site de Michel VOLLE
Powered by picosearch  


Vous êtes libre de copier, distribuer et/ou modifier les documents de ce site, à la seule condition de citer la source.
 GNU Free Documentation License.

Organiser un tour de garde


21 juillet 2004

Liens utiles

- La programmation comme hobby
- Télécharger DrScheme
- Programme source


NB : Pour utiliser ce programme, il faut disposer de DrScheme que l'on peut télécharger gratuitement à partir de www.DrScheme.org, et choisir dans le menu "langage" l'option Pretty Big.
 

Ce programme fournit une liste aléatoire de personnes qui devront assurer chaque jour une garde (que l'on pense à des médecins, des pharmaciens etc.).

Cette liste doit respecter les contraintes suivantes :
- une même personne ne peut pas être de garde deux jours de suite, sauf le week-end ;
- la même personne assure la garde le samedi et le dimanche qui suit ;
- une même personne ne peut pas être de garde un même jour de la semaine deux semaines de suite.

Pour paramétrer le programme, il faut choisir  l’année considérée et indiquer la liste des partenaires. La liste doit être saisie sous le format suivant :


((Pierre Dupont) (Paul Martin) (Marcel Dubois) (Jacques Stahl) (François Humbert) (Yves Clot) (Michel Floret) (Gérard Flandrin)))
 

Le nombre des partenaires doit être supérieur à quatre. Le millésime de l'année doit être supérieur à 1999.

Le résultat est édité sous la forme d'une liste comportant une ligne par jour :


((jeudi 1 janvier 2004 françois humbert)
 (vendredi 2 janvier 2004 marcel dubois)
 (samedi 3 janvier 2004 michel floret)
 (dimanche 4 janvier 2004 michel floret)
 (lundi 5 janvier 2004 pierre dupont)

… (lignes intercalaires)...


 (lundi 27 décembre 2004 pierre dupont)
 (mardi 28 décembre 2004 yves clot)
 (mercredi 29 décembre 2004 jacques stahl)
 (jeudi 30 décembre 2004 michel floret)
 (vendredi 31 décembre 2004 marcel dubois))
 

Pour conserver et utiliser ce résultat, faire un copier-coller vers Word ou vers Excel.

Le programme fournit aussi le décompte des jours de garde par personne pour chaque semestre :


Nombre de gardes au premier semestre 2004 :
((pierre dupont) 23)
((paul martin) 24)
((marcel dubois) 22)
((jacques stahl) 21)
((françois humbert) 23)
((yves clot) 23)
((michel floret) 24)
((gérard flandrin) 22)

Nombre de gardes au deuxième semestre 2004 :
((pierre dupont) 23)
((paul martin) 22)
((marcel dubois) 24)
((jacques stahl) 23)
((françois humbert) 22)
((yves clot) 24)
((michel floret) 23)
((gérard flandrin) 23)
 

Le tirage étant réalisé sans remise, le nombre des jours de garde dans un semestre est à peu près le même pour chaque partenaire, les écarts étant dus à un effet d'arrondi.

Chaque exécution du programme fournit une liste différente. Si nécessaire, on peut ainsi choisir entre plusieurs listes.

*  *

La première partie du programme concerne le traitement du calendrier : elle distingue les années bissextiles et attribue un jour de semaine à chaque date. Excel fait cela automatiquement ... programmer soi-même ce que sait déjà faire un progiciel, c'est un bon exercice.

Pour réaliser le tirage sans remise, j'ai dû écrire ma première fonction "tail-recursive" : cela m'a donné pas mal de tintouin, mais j'y ai beaucoup appris. La fonction tirage n'est en effet pas des plus simples :

(define tirage
 (lambda (nombre-à-tirer sac cumul sac-)
  (cond ((= nombre-à-tirer 0) cumul)
        ((= (length sac-) 0) (tirage (length dates) sac-1er-semestre '() sac-1er-semestre))
        (else (let* ( (numero (random (length sac-)))
                      (individu (cond ((and (< nombre-à-tirer (length dates))(eq? (joursemaine nombre-à-tirer) 'samedi)) (car cumul))
                                (else (list-ref sac- numero))))
                      (newsac (cond ((= nombre-à-tirer (- semestre1 1)) (append sac-2nd-semestre (remove individu sac)))
                              (else (remove individu sac))))
                      (newsac- (cond ((> (length cumul) 7) (removeall (caddr (cdddr cumul)) (removeall individu newsac)))
                               (else (removeall individu newsac)))) )
      (tirage (- nombre-à-tirer 1) newsac (cons individu cumul) newsac-))))))

Voici le commentaire détaillé de cette fonction :

(define tirage
    (lambda (n sac cumul sac-)

1) nombre-à-tirer est le nombre de tirages à effectuer, soit ici le nombre de jours de l'année (length dates). Après un premier tirage, on itèrera sur (- nombre-à-tirer 1).

2) sac est le "sac" dans lequel on fait le tirage sans remise : après chaque tirage, l'individu tiré est ôté du sac. Cela donne newsac, sur lequel on itérera.

3) cumul est l'empilage "tail-récursif" des résultats des tirages. Au début il est vide et il se remplit progressivement. On va donc commencer par '(), puis itérer par (cons individu cumul).

4) sac- est le sac dans lequel on tire effectivement : c'est newsac dont on a ôté les individus qui, pour respecter les contraintes ci-dessus, ne doivent pas être tirés.

(cond ((= nombre-à-tirer 0) cumul)

Lorsque l'on a tiré n fois, cumul est complet. C'est lui qui sera le résultat de la fonction.

((= (length sac-) 0) (tirage (length dates) sac-1er-semestre '() sac-1er-semestre))

Il se peut que (= (length sac-) 0) avant que (= nombre-à-tirer 0), c'est-à-dire avant que le tirage ne soit fini : l'empilage des conditions n'est pas toujours tenable ! Cette instruction relance le tirage jusqu'à ce que l'on ait une solution.

(else (let* ( (numero (random (length sac-)))

On tire au sort un rang dans le sac où doit se faire le tirage

(individu (cond ((and (< nombre-à-tirer (length dates))(eq? (joursemaine nombre-à-tirer) 'samedi)) (car cumul))

Si le jour de semaine est un samedi, il faut que l'on tire le même individu que le jour précédent (qui était un dimanche, l'empilage se faisant selon l'ordre inverse de la chronologie).

(else (list-ref z- x))))

Si le jour de semaine n'est pas un samedi, on tire l'individu dont le rang a été au sort précédemment.

(newsac (cond ((= nombre-à-tirer (- semestre1 1)) (append sac-2nd-semestre (remove individu sac)))

A la fin du premier semestre, ou ajoute le sac du second semestre au reste du sac du premier semestre.

(else (remove individu sac))))

On ôte du sac le dernier individu tiré.

(newsac- (cond ((> (length cumul) 7) (removeall (caddr (cdddr cumul)) (removeall individu newsac)))
               (else (removeall individu newsac)))) )

On ôte de newsac tous les individus qui, en raison des contraintes, ne doivent pas être tirés. Il faut tenir compte du fait que l'on ne peut ôter l'individu tiré sept jours avant que si l'on a déjà parcouru une semaine !

(tirage (- nombre-à-tirer 1) newsac (cons individu cumul) newsac-))))))

On itère la fonction : il reste à tirer (- n 1) fois ; le nouveau sac est newsac, dont les individus tirés ont été ôtés ; le résultat du tirage précédent s'empile par (cons y c) ; enfin, ôter de newsac les individus à éviter donne newsac- dans lequel est réalisé le tirage effectif.