Dans la série: Toi t'y arrives? (proba et logique)
Alors voilà, je suis étudiant en Ingénierie logicielle en Australie. Je commence un entrainement de résolution de problème par programmation afin de pouvoir participer au championnat Nationale de Programmation.
Dans un des exos que je suis en train de faire, je me trouve avec un probleme de probabilité que je n'arrive pas à résoudre après une ou deux heures de recherches, quelqu'un bon en probabilité pourra surement m'aider.
Voici le problème:
Comporte de droits d'auteurs, donc:
Auteur: LunaticFringe - 2003 // Traduit par nicom974 (Anglais vers Français) - 2010
Dans la majorité des Etats, les joueurs de lotterie peuvent choisir parmis une assez large variété de tickets différents. Les règles d'un jeu de loterie sont définies par deux entiers (choices et blanks) et deux variables booléennes (sorted et unique). choices représente le plus grand numéro du ticket de loterie. (Tous les entiers sont entre 1 et la variable choices, inclus, sont valides et peuvent apparaitre sur votre ticket). La variable blanks représente le nombre de case que vous pouvez cocher sur votre ticket.
Les variables sorted et unique indiquent des contraintes. Si sorted et Vraie (True), alors les numéros sur votre ticket doivent être écrit en ordre croissant. Si sorted est Faux (False), alors les numéro peuvent être écrit dans n'importe quel ordre. De même, si unique est Vraie (True), alors chaque numéro que vous écrivez sur votre ticket doit être distinct des autres (Donc il ne peux pas y avoir plus d'une fois ce numéro sur votre ticket) et si unique est Faux (False), alors les répétitions sont autorisées.
Voici quelques exemples de tickets de loterie où choices = 14 et blanks=4:
{3, 7, 12, 14} - Ce ticket est totalement valide
{13, 4, 1, 9} - Ticket valide si sorted = False
{8, 8, 8, 15} - Ticket valide si unique = False
{11, 6, 2, 6} - Ticket valide si sorted = False et unique = False
Si il est donné une liste de jeux et leur règles, retournez une liste de noms de jeux triée en fonction du nombre de chance de gagner (Le plus de chance en haut, moins de chance à la fin). La probabilité que vous gagnerai à la loterie est égale ) 1/(nombre de tickets valides pour le jeu). Le jeux offrant le plus de chances de gagner devrait apparaître au début de la liste. Si plusieurs jeux ont les même chances de réussite, ils doivent être triée par ordre alphabétique.
soted et unique = T pour 'Vraie' F pour 'Faux'
Une règle est composée des éléments suivants:
"<NOM DU JEU>: <CHOICES> <BLANKS> <SORTED> <UNIQUE>"
Exemples 1:
{"PICK ANY TWO: 10 2 F F",
"PICK TWO IN ORDER : 10 2 T F",
"PICK TWO DIFFERENT: 10 2 F T",
"PICK TWO LIMITED: 10 2 T T"}
Retourne:
{ "PICK TWO LIMITED",
"PICK TWO IN ORDER",
"PICK TWO DIFFERENT",
"PICK ANY TWO" }
Explications:
Le jeux "PICK ANY TWO" offre à la variable blanks a possibilité d'être un nombre entre 1 et 10. Donc il y a 10*10= 100 tickets possibles, et les chances de gagner sont donc de 1/100.
Le jeux "PICK IN ORDER" signifie que le premier numéro ne peut pas être plus grand que le second. Ce qui élimine 45 tickets possibles, nous laissant 55 tickets valides.
Le jeux "PICK TWO DIFFERENT" interdit uniquement les tickets où le premier et deuxième numéros sont les mêmes.
Le jeux "PICK TWO LIMITED" interdit l'ajout de 10 tickets des 45 interdits du jeux "PICK TWO IN ORDER". Les chances de gagner sont de 1/45.
Exemple 2:
{"INDIGO: 93 8 T F",
"ORANGE: 29 8 F T",
"VIOLET: 76 6 F F",
"BLUE: 100 8 T T",
"RED: 99 8 T T",
"GREEN: 78 6 F T",
"YELLOW: 75 6 F F"}
Retourne: { "RED", "ORANGE", "YELLOW", "GREEN", "BLUE", "INDIGO", "VIOLET" }
Vous remarquerez que BLUE et et INDIGO ont tous deux le même nombre de chance de gagner (1/186087894300). BLUE est en lister avant INDIGO car il arrive en premier dans l'alphabet.
---FIN DU PROBLEME---
Il y a ici 4 différentes formules que je peux utiliser en fonctions des variables sorted et uniques. J'ai mis à coté ce que je pense que le résultat est, mais merci de vérifier
sorted = True et unique = True -> nCr (n=choices, r=blanks)
sorted = True et unique = False -> ...
sorted = False et unique = True -> nPr (n=choices, r=blanks)
sorted = False et unique = False -> ...
Merci pour votre aide...
Nicolas
-----
