Répartition

[Elias]

Salut à tous,

J'ai une question dont la solution peut-être mathématique ou informatique (un programme).

On considère dans un lycée un ensemble de 13 classes. Chacune de ces classes doit faire un certain nombre d'heures de mathématiques par semaine. Par exemple, la classe de 2nde1 doit faire ses 5H de maths par semaine etc ...

classes :
2nde1 : 5H
2nde2 : 5H
2nde3 : 5H
2nde 4 : 5H
1ere1 : 4H
1ere2 : 4H
1ere3 : 4H
1ere 4 : 4H
Term1 : 6H
Term2 : 6H
Term3 : 6H
petit_groupe : 2H
Term4 : 7H

Au total, 63 heures de mathématiques par semaines doivent être données par 4 professeurs. Parmi ces professeurs, 4 doivent assurer exactement 15H par semaine et 1 doit assurer 18H par semaine.

4 professeurs :
Prof1 : 15H à assurer, Prof2 : 15H à assurer, Prof3 : 15H à assurer, Prof4 : 18H à assurer.

Ma question est comment trouver toutes les répartitions possibles ? (informatiquement éventuellement)

Exemple de répartition :
Prof1 : Term1+1ere1+2nde1 (6+4+5 = 15H)
Prof2 : 1ere2+1ere3+2nde2+petit_groupe (4+4+5+2=15H)
Prof3 : Term2+1ere4+2nde3 (6+4+5 = 15H)
Prof4 : Term4+Term3+2nde4 (7+6+5 = 18H)

[tournesol]

Doit pouvoir être fait à la main :
agrégés : 2445 , 447 , 456 , 555 .
certifié : 24444 , 2457 , 2556 , 4446 , 4455 , 567 , 666 .
1)Tu attribues une répartition au certifié , par exemple 44442
Tu ne peux plus rien attribuer au agrégés . donc tu élimines 44442
2)Tu attribues une répartition au certifié , par exemple 4446
te ne peux qu'attribuer 456 à un seul agrégé et rien pour les autres . Tu élimines donc 4446.
Amuses toi bien .

[lyceen95]

Informatiquement, ça se fait. On appelle ça la 'force brute', on essaie toutes les combinaisons, et dès qu'une solution convient, on affiche cette combinaison.
C'est bourrin, mais ce n'est pas si simple à programmer si on n'est pas un peu formé ...

Manuellement, on peut remarquer que la classe de Term4 a 7 heures.
Le prof qui a cette classe a donc déjà 7 heures de prises, il lui reste soit 8heures, soit 11 heures.
Soit ce prof là a (7+6+2) , (7+4+4) , (7+5+6), ou (7+5+4+2).
Etc etc ... mais il y a plein de combinaisons... quelques millions ?
Par exemple, en partant de ta solution ( Prof 1 = 6h+4h+5h) etc etc, et en se limitant à cette répartition :
Le prof 1 doit une voir une classe avec 6h : 3 choix possibles
Il doit avoir aussi une classe avec 4 heures :4 choix possibles
Et il doit avoir aussi une classe avec 5 heures : 4 choix possibles.
En se limitant aux cas où le prof1 a 6+5+4 heures, on en est donc à 3*4*4=48 choix.

Quand on a donné ses 3 classes au prof 1, on passe au prof 2 :
Il doit avoir la seule classe de 2h , plus une classe de 5 heures (3 choix possibles, vu que le prof1 a déjà pris une des classes) et 2 classes de 4 heures (6 choix possibles)
On en est déjà à 48*3*6=864 choix possibles.
Et ensuite, il faut passer au prof 3 : 4 choix possibles . Et le prof 4 prend les 4 classes restantes.
Donc 864*4=3456 choix possibles.
Ca, c'est en se limitant aux cas où le prof1 a 6+5+4, prof2 a 4+4+5+2, prof3 a 6+4+5 et prof4 a 7+6+5.

A la louche, environ un million de solutions.

[Elias]

Merci pour vos réponses mais je me rends compte que je n'ai pas été très clair. Je précise que je cherche une solution générale pour n'importe quelles classes et n'importe quels professeurs (avec des services éventuellement à 9H etc ..)
L'exemple donné n'est là que pour préciser ma question (je l'ai inventé complètement au hasard).

[lyceen95]

Tu dis que tu veux toutes les combinaisons.
Repartons de tes données, juste pour illustrer.
On sait déjà qu'il y a 3456 dispositions avec prof1=6+5+4 etc etc.
Avec beaucoup de méthode et beaucoup de patience, on peut lister ces 3456 dispositions à la main.
Et continuer avec les autres dispositions.
Avec des données différentes, pareil, c'est faisable manuellement, il faut juste être très patient et très méthodique.
Mais on parle de centaines de milliers de solutions !

L'autre solution, c'est bien sûr par programmation. Tu peux rechercher 'programmation parcours d'arbre' sur ton moteur de recherche préféré.

Tu parlais de solution mathématique ou informatique .... oublie le mot mathématique pour cette question.

[tournesol]

A la main , c'est immédiat :
2457 , 456 , 456 , 456 .
567 , 2445 , 456 , 456 .
2556 , 447 , 456 , 456 .

[lyceen95]

Et aussi : 666, 447, 555, 2445

Et sans garantie que ce soit tout.

[tournesol]

Bien vu lyceen95

[lyceen95]

Et aussi : 2466, 447, 555, 456

[tournesol]

En fait dans mon premier message , j'ai oublié la répartition 555 pour le service d'un agrégé .
Ce qui explique mes deux oublis
Merci donc .

[tournesol]

Il devrait rester 4446 , 267 , 456 , 555 .
J'ai combiné les répartitions suivantes :
certifié : 24444 , 2457 , 2466 , 2556 , 4446 , 4455 , 567 , 666 .
agrégé : 2445 , 267 , 447 , 456 , 555 .

[lyceen95]

Ici, on recense les 'formes' des solutions.
On dit par exemple qu'un prof qui doit avoir 15 heures peut avoir 6+5+4, ou encore 5+5+5.
Mais la question initiale allait plus loin. Quand on a décidé que le prof n°1 allait avoir 3 classes avec respectivement 6heures, 5heures et 4heures, il y a plein de façons de choisir ces classes.
Et il va falloir un programme pour lister tout ça.
Voici un programme qui a l'air de fonctionner, sauf que j'ai un léger doute. Je parlais d'environ 1 million de dispositions pour les données de l'exemple, et j'arrive à seulement 15408.

Code: Tout sélectionner

ch1, ch2 est une chaîne
i  est un entier
ch1 = "2,7,6,6,6,5,5,5,5,4,4,4,4"
ch2 = "15,15,15,18"
tprofs est un tableau de 0 entiers
tclasses est un tableau de 0 entiers 
tliens est un tableau de 0 entiers
POUR TOUTE CHAÎNE ch DE ch1 SEPAREE PAR ","
   TableauAjouteLigne( tclasses, Val(ch ) )
FIN
POUR TOUTE CHAÎNE ch DE ch2 SEPAREE PAR ","
   TableauAjouteLigne( tprofs , Val(ch ) )
FIN
ftraite( tprofs, tclasses, tliens )


Code: Tout sélectionner

PROCÉDURE ftraite(tprofs est un tableau d'entiers   ,tclasses est un tableau d'entiers  ,tliens est un tableau d'entiers   )
tprof2 est un tableau d'entiers
tclasse2 est un tableau d'entiers
tlien2 est un tableau d'entiers
ch est une chaîne
j, i est un entier 
POUR i = 1 _À_ TableauOccurrence(tprofs)
   TableauAjouteLigne(tprof2, tprofs[i])
FIN
POUR i = 2 _À_ TableauOccurrence(tclasses)
   TableauAjouteLigne(tclasse2, tclasses[i])
FIN
POUR i = 1 _À_ TableauOccurrence(tliens)
   TableauAjouteLigne(tlien2, tliens[i])
FIN
SI TableauOccurrence(tclasses) > 0 ALORS
   j = tclasses[1]
   POUR i = 1 _À_ TableauOccurrence(tprof2)
      SI tprof2[i] >= j ALORS
         tprof2[i] = tprof2[i] - j
         TableauAjouteLigne(tlien2,i)
         ftraite(tprof2,tclasse2, tlien2)
         tprof2[i] = tprof2[i] + j
         TableauSupprime(tlien2, TableauOccurrence(tlien2) )
      FIN
   FIN
SINON
   ch = ""
   POUR i = 1 _À_ TableauOccurrence( tlien2)
      ch += [ " "] + tlien2[i]   
   FIN
   Trace(ch)
   nsol++
FIN