IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme Lotofoot


Sujet :

Algorithmes et structures de données

  1. #1
    Membre du Club
    Profil pro
    Inscrit en
    Janvier 2003
    Messages
    56
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2003
    Messages : 56
    Points : 45
    Points
    45
    Par défaut Algorithme Lotofoot
    Bonjour à tous,

    J'aimerais créer un logiciel sur le lotofoot.
    Mon problème est le calcul pour réduire les mises.
    Ex:
    lotofoot à 15 matches.
    Je veux jouer 3 doubles.
    Soit Match 1 : 1N
    Match 2 : N2
    Match 3 : 1N
    Match 4 : 1
    Match 5 : 1
    ...
    Match 15 : 1
    En jouant directement 3 doubles à la Française des jeux, je devrait jouer 8 grilles pour avoir 15 bons résultats sur 15 matchs. (2^3 = 8)
    Mais si je voulais un mimum de 14 matchs gagnants, il me faudrait moins de grille.Donc je fais appel aux différents matheux de ce forum pour m'aider à trouver une formule de réduction.

    Merci de votre attention.
    @++

  2. #2
    Invité(e)
    Invité(e)
    Par défaut
    Bonjour
    La question n'est pas très clairement posée...
    En jouant directement 3 doubles à la Française des jeux, je devrait jouer 8 grilles pour avoir 15 bons résultats sur 15 matchs.
    Pour moi, pour etre sur d'avior 15 bons matchs, il faut jouer TOUTES les possibilités, c'est à dire les 32768 gilles possibles (mais ca fait beaucoup non ?)
    Mais pour ce raisonnement, j'y mets de la mauvaise foi.

    Si en jouant 8 grilles, on est sur d'avoir 15 bons matchs, alors 4 grilles suffiront pour en avoir 14 de bons : on joue un des match sans espoir de le gagner (par ex : match 1 : 1 au lieu de 1N)

    Mais je n'ai peut être pas très bien compris le problème... Peux tu etre plus explicite ? Merci

  3. #3
    Membre du Club
    Profil pro
    Inscrit en
    Janvier 2003
    Messages
    56
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2003
    Messages : 56
    Points : 45
    Points
    45
    Par défaut
    Salut mabu,

    Nous avons 15 matchs =>
    01 - 1N
    02 - N2
    03 - 1N
    04 - 1
    05 - 1
    06 - 1
    07 - 1
    08 - 1
    09 - 1
    10 - 1
    11 - 1
    12 - 1
    13 - 1
    14 - 1
    15 - 1

    Les matchs 4 à 15 sont gagnats car 1 seule possibilité.
    Par contre les matchs 1 à 3 ont plusieurs combinaisons possibles.
    Nous pouvons avoir :
    1ere possibilité
    01 - 1
    02 - N
    03 - 1

    2eme possibilité
    01 - 1
    02 - N
    03 - N

    3eme possibilité
    01 - N
    02 - N
    03 - 1

    4eme possibilité
    01 - N
    02 - N
    03 - N

    5eme possibilité
    01 - 1
    02 - 2
    03 - 1

    6eme possibilité
    01 - 1
    02 - 2
    03 - N

    7eme possibilité
    01 - N
    02 - 2
    03 - 1

    8eme possibilité
    01 - N
    02 - 2
    03 - N

    En jouant 2 grilles nous pouvons avoir 14 resultats bons sur 15 à tous les coups

    4eme possibilité
    01 - N
    02 - N
    03 - N

    5eme possibilité
    01 - 1
    02 - 2
    03 - 1

    Ce logiciel permettrait de réduire mes grilles au lotofoot en ayant une garantie d'avoir 14 bons résultats sur 15 en jouant dans cet exemple 2 € au lieu de 8 €.

    Donc j'aimerais savoir quelle formule de calcul me permettrait d'obtenir ce résultat.

    Merci.

  4. #4
    Invité(e)
    Invité(e)
    Par défaut
    Okay, j'ai pigé le problème....
    En fiat, c'est côté cobinatoire qu'il faudra chercher je pense :
    les 3 premiers matchs peuvent etre soit gagnant soit perdant (vrai ou faux).
    Sur le papier, c'est facile de dire qu'il suffit de jouer deux fois pour avoir 14 bonne réponses (pareil pour en avoir 13), mais ca me parrait dur de déterminer une formule mathématique miracle...

    Une idée serait de générer tous les cas de figure possible et tester des ensembles de solutions pour savoir lesquels sont à coup sur gagnant : c'est facile à faire mais très très très couteux en temps de calcul...

    Pour une formule générale, je vais chercher dans mais souvenir d'automatisme...
    Peut être un réponse plus tard

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    Janvier 2003
    Messages
    56
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2003
    Messages : 56
    Points : 45
    Points
    45
    Par défaut
    Merci bien Mabu de m'avoir répondu

  6. #6
    Membre du Club
    Profil pro
    Inscrit en
    Avril 2005
    Messages
    58
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2005
    Messages : 58
    Points : 46
    Points
    46
    Par défaut
    je comprend en gros ce que tu veux faire mais je vois pas ou ca va te mener !
    tu crois que tu rentrera ds tes frait ?
    puis il y a plus de cas :
    1-1-1
    1-1-n
    1-1-2
    1-n-1
    1-n-n
    1-n-2
    1-2-1
    1-2-n
    1-2-2
    etc .....donc 9*3 possibilté

  7. #7
    Membre du Club
    Profil pro
    Inscrit en
    Janvier 2003
    Messages
    56
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2003
    Messages : 56
    Points : 45
    Points
    45
    Par défaut
    Citation Envoyé par schmur1
    je comprend en gros ce que tu veux faire mais je vois pas ou ca va te mener !
    tu crois que tu rentrera ds tes frait ?
    puis il y a plus de cas :
    1-1-1
    1-1-n
    1-1-2
    1-n-1
    1-n-n
    1-n-2
    1-2-1
    1-2-n
    1-2-2
    etc .....donc 9*3 possibilté
    Les cas que tu cites sont des triples et non des doubles
    On aurait eu dans ton cas :
    01 - 1N2 et non 1N
    02 - 1N2 et non N2
    03 - 1N2 et non 1N
    04 - 1
    05 - 1
    06 - 1
    07 - 1
    08 - 1
    09 - 1
    10 - 1
    11 - 1
    12 - 1
    13 - 1
    14 - 1
    15 - 1

  8. #8
    Membre éprouvé
    Avatar de c-top
    Profil pro
    Turu
    Inscrit en
    Septembre 2003
    Messages
    972
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Turu

    Informations forums :
    Inscription : Septembre 2003
    Messages : 972
    Points : 1 246
    Points
    1 246
    Par défaut
    Je crois que vous êtes en train de vous faire des films, s'il était possible d'avoir les bons résultats avec 8 grilles seulement, ça fait longtemps que la francaise des jeux aurait abandonnée le lotofoot.

  9. #9
    Membre actif
    Profil pro
    Inscrit en
    Juin 2002
    Messages
    646
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2002
    Messages : 646
    Points : 240
    Points
    240
    Par défaut
    Je suis daccord avec c-top

    Ou alors je ne comprend pas ou vous voulez en venir

  10. #10
    Expert éminent

    Profil pro
    Fabricant et casseur d'avions
    Inscrit en
    Avril 2004
    Messages
    3 807
    Détails du profil
    Informations personnelles :
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Fabricant et casseur d'avions
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2004
    Messages : 3 807
    Points : 7 613
    Points
    7 613
    Par défaut
    Salut,

    Citation Envoyé par c-top
    Je crois que vous êtes en train de vous faire des films, s'il était possible d'avoir les bons résultats avec 8 grilles seulement, ça fait longtemps que la francaise des jeux aurait abandonnée le lotofoot.
    Citation Envoyé par kacedda
    Je suis daccord avec c-top

    Ou alors je ne comprend pas ou vous voulez en venir
    D'après ce que je comprend, le but du jeu n'est pas d'avoir les 15 résultats bons (enfin... si on les a, tant mieux ), mais d'en avoir 14. Et sur ces 14, d'optimiser le nombres de grilles à jouer.

    Là, c'est sur les 3 premiers matches que yoyo44 veut optimiser.

    Je vais prendre un exemple plus causant... en supposant que le résultat du match soit soit une bille bleue, soit une bille rouge. Vu que les 13 autres matches n'entrent pas dans l'optimisation (on suppose qu'on est suffisament chanceux pour trouver le bon résultat), on parie sur le résultat des 3 autres. MAIS, on ne veut que 2 résultats de bons minimum sur les 3 (c'est là qu'intervient le critère 14 de bons sur 15). Donc au choix, chaque match se voit associer soit une bille bleue B, soit une rouge R. On va donc avoir les possibilités suivantes:

    a - BBB
    b - BBR
    c - BRB
    d - RBB
    e - RRR
    f - RRB
    g - RBR
    h - BRR

    Dans ces combinaisons, on voit que l'on peut ne jouer que les combinaisons (a) et (e). Pourquoi? Parce que le résultat final sera soit trois billes de la même couleur, soit deux billes d'une couleur et la troisième de l'autre. Donc si on joue les combinaisons BBB et RRR, on est sûr d'avoir 2 bonnes couleurs quelque soit le résultat final.
    Et au lieu de jouer 8 grilles, on n'en joue que 2.

    Mais ça ne veut pas dire qu'on est sûr de gagner, vu qu'il y a douze matches pour lesquels on ne gère pas les multiples résultats! C'est seulement une optimisation des combinaisons afin de réduire la mise.

    Par contre, à appliquer au LotoFoot, je sèche un peu...

    Ou alors il faut tester en prenant comme résultat final l'une des grilles possibles. On regarde combien cette grille "couvre" d'autres grilles (en prenant les résultats ordonnés), et on ne conserve que les grilles qui en couvrent le plus.

    Par exemple, si on prend la grille (a) comme masque, on obtient:

    a- 3 bons résultats (BBB)
    b- 2 bons résultats (BBx)
    c- 2 bons résultats (BxB)
    d- 2 bons résultats (xBB)
    etc etc... résultat: 4 grilles couvertes

    si on prend la grille (b):

    a- 2 bons résultats (BBx)
    b- 3 bons résultats (BBR)
    c- 1 bon résultats (Bxx) => pas couvert
    d- 1 bon résultat (xBx) => pas couvert
    etc etc... résultat: 3 grilles couvertes

    pareil pour les autres. Dans ce cas, on garde la (a), on supprime toutes les grilles couvertes par cette combinaison, et on recommence avec les grilles restantes (ce qui fait ressortir la combinaison (e) parmi les combinaisons (e), (f), (g) et (h)).
    "Errare humanum est, sed perseverare diabolicum"

    Ma page sur DVP.com

  11. #11
    Membre du Club
    Profil pro
    Inscrit en
    Janvier 2003
    Messages
    56
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2003
    Messages : 56
    Points : 45
    Points
    45
    Par défaut
    Salut plegat,

    Tu as tout compris , ça fait plaisir je croyais que je m'étais mal exprimé

  12. #12
    Membre averti
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    488
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 488
    Points : 397
    Points
    397
    Par défaut
    Je ne sais pas s'il n'est pas inutile de rappeler que pour avoir 14 bons résultats il faut jouer 3^14 = 4 782 969 combinaisons. Sachant qu'une grille avec 3 doubles permet de jouer 8 combinaisons il faut donc un minimum de 597 872 grilles. Après ça il faut savoir les combiner, et après ces chiffres je ne suis pas sûr que ce soit utile d'y réfléchir.

  13. #13
    Membre confirmé
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Points : 554
    Points
    554
    Par défaut
    Si on a une incertitude sur 3 doubles, il faut comme cela a été dit, 2 grilles pour être sûr d'avoir 14 bons résultats. Cela se démontre simplement en énumérant les 8 cas possibles. (S'il n'y a qu'un double, il faut un une seule grille. S'il y a 2 doubles, il faut 2 grilles).

    En revanche, s'il y a une incertitude sur k>2 doubles, il faut 2^(k-2) grilles. Pour le démontrer, j'ai modélisé chaque grille par un chemin dans un graphe et dénombré le nombre de chemins qu'il fallait. C'est un peu long à écrire mais je peux m'y atteler ce soir ou demain si cela intéresse quelqu'un (et pour vraiment valider la démonstration )

    Erratum: Voir correctif à ce message un peu plus loin dans le fil de la discussion...

  14. #14
    Membre du Club
    Profil pro
    Inscrit en
    Janvier 2003
    Messages
    56
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2003
    Messages : 56
    Points : 45
    Points
    45
    Par défaut
    Citation Envoyé par FrancisSourd
    Si on a une incertitude sur 3 doubles, il faut comme cela a été dit, 2 grilles pour être sûr d'avoir 14 bons résultats. Cela se démontre simplement en énumérant les 8 cas possibles. (S'il n'y a qu'un double, il faut un une seule grille. S'il y a 2 doubles, il faut 2 grilles).

    En revanche, s'il y a une incertitude sur k>2 doubles, il faut 2^(k-2) grilles. Pour le démontrer, j'ai modélisé chaque grille par un chemin dans un graphe et dénombré le nombre de chemins qu'il fallait. C'est un peu long à écrire mais je peux m'y atteler ce soir ou demain si cela intéresse quelqu'un (et pour vraiment valider la démonstration )
    Salut FrancisSourd,

    Ca m'intéresse bien
    Merci @++

  15. #15
    Membre averti
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    488
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 488
    Points : 397
    Points
    397
    Par défaut
    Citation Envoyé par FrancisSourd
    En revanche, s'il y a une incertitude sur k>2 doubles, il faut 2^(k-2) grilles. Pour le démontrer, j'ai modélisé chaque grille par un chemin dans un graphe et dénombré le nombre de chemins qu'il fallait. C'est un peu long à écrire mais je peux m'y atteler ce soir ou demain si cela intéresse quelqu'un (et pour vraiment valider la démonstration )
    Je suis curieux de voir cette démonstration, ou même simplement un exemple de 8 grilles pour le cas k=5.

  16. #16
    Membre confirmé
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Points : 554
    Points
    554
    Par défaut
    En réfléchissant cette nuit, je me suis aperçu qu'il y avait un problème dans la démo.... Voilà donc où j'en suis:
    • - Il y a une solution avec 2^(k-2) grilles
      - Il faut au moins 2^k/(k+1) grilles


    Pour construire une solution avec 2^(k-2) grilles, je me suis basé sur ta solution à k=3. Par exemple, pour le problème (k=7)
    1N
    N2
    N2
    1N
    1N
    12
    1N
    on doit générer les deux familles de grilles (notations type expressions régulières):
    1NN[1N][1N][12][1N] et N22[1N][1N][12][1N]
    Cela fait donc 2 fois 2^(k-3) grilles soit 2^(k-2) grilles.

    Pour la borne inférieure: soit S l'ensemble des grilles jouées.
    Pour une grille x de S, soit S(x) l'ensemble des grilles qui diffèrent d'un résultat par rapport à x. Par exemple avec le problème précédent
    S(1NN1111)={NNN1111, 12N1111, 1N21111, 1NNN111, 1NN1N11, 1NN1121, 1NN111N}
    Clairement |S(x)| = k.
    Pour être sûr d'avoir au plus un résultat faux, il faut que tous les résultats possibles soient dans l'union de S et de tous les S(x) (pour x variant dans S). Comme il y a 2^k résultats possibles, il faut que
    2^k <= |S union U_x S(x) | <= |S| + sum_x |S(x)|
    Or, pour tout x, |S(x)| = k donc
    sum_{x in S} |S(x)| = sum_{x in S} k = k|S|
    Donc l'inégalité s'écrit
    2^k <= (k+1)|S| et donc |S| >= 2^k/(k+1)

    Le nombre minimal de grilles à remplir est donc compris entre (2^k)/(k+1) et 2^(k-2).
    Lorsque k=3, ces deux valeurs valent 2. Pour k>3, le problème reste ouvert.

  17. #17
    Membre confirmé
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Points : 554
    Points
    554
    Par défaut
    J'ai modélisé le problème comme un programme linéaire en nombres entiers pour trouver les solutions optimales pour les petites valeurs de k. Pour représenter les solutions, j'ai codé les grilles par k valeurs 0/1. Un 0 signifie qu'il faut sélectionner le premier choix et 1 le second choix.

    Par exemple, pour le problème avec k = 4:
    1N
    N2
    N2
    1N

    Les 4 solutions sont 1000 1110 0101 et 0011, ce qui veut dire qu'il faut cocher les cases NNN1 N221 12NN et 1N2N.

    Je me suis arrêté à k=9 car ce problème demande presque trois heures de calcul. Voici donc les résultats (ils sont compatibles avec les bornes trouvées dans le mail précédent ):
    k = 3 Optimal Value = 2 grilles
    110 001

    k = 4 Optimal Value = 4 grilles
    1000 1110 0101 0011

    k = 5 Optimal Value = 7 grilles
    00100 10010 01110 01001
    11001 11101 00111

    k = 6 Optimal Value = 12 grilles
    001000 010100 110100 100010 111010 101110
    001001 101001 110101 010011 000111 011111

    k = 7 Optimal Value = 16 grilles
    1100000 0011000 1010100 0101100 0110010 1001010
    0000110 1111110 0000001 1111001 0110101 1001101
    1010011 0101011 1100111 0011111

    k = 8 Optimal Value = 32 grilles
    10100000 01010000 10001000 01111000 00000100 01100100
    11011100 10111100 11000010 11110010 00101010 00011010
    10010110 00110110 01001110 11101110 10010001 00110001
    01001001 11101001 11000101 11110101 00101101 00011101
    00000011 01100011 11011011 10111011 10100111 01010111
    10001111 01111111
    Je suis de moins en moins convaincu sur le fait qu'on puisse trouver une formule générale pour tout k.

  18. #18
    Membre confirmé
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Points : 554
    Points
    554
    Par défaut
    J'ai soumis en termes mathématiques le problème à un forum de recherche et j'ai reçu en réponse ce lien très intéressant qui donne plusieurs références sur ce problème. En particulier, il n'y a pas de formule "magique" pour générer la suite (pour k=9, il faut 62 grilles mais ensuite le problème est ouvert...)

    http://www.research.att.com/projects/OEIS?Anum=A000983

    Commentaire: Ce site est rigolo: on rentre les premiers termes d'une suite et le moteur de recherche renvoie ce qui est connu sur la suite (problèmes où elle apparaît, formule de récurrence, termes connus...)

  19. #19
    Membre du Club
    Profil pro
    Inscrit en
    Janvier 2003
    Messages
    56
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2003
    Messages : 56
    Points : 45
    Points
    45
    Par défaut
    Merci FrancisSourd pour toutes ces réponses

    tous tes résultats sont bons et comme tu dis :
    Je suis de moins en moins convaincu sur le fait qu'on puisse trouver une formule générale pour tout k
    On ne sait jamais ...

  20. #20
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Février 2006
    Messages
    1
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2006
    Messages : 1
    Points : 0
    Points
    0
    Par défaut
    Bonjour à tous

    Je tombe par hasard sur ce (vieux) sujet et j'avoue que je suis surpris : tous ces problèmes ont été traités depuis fort longtemps et la consultation des sites de LOTOFOOT vous en apprendra beaucoup. C'est même un élément essentiel des logiciels consacrés au LF.

    Juste pour information (même si c'est très tardif) pour réduire 4T en N-1 (c'est à dire 3 bons résultats garantis) il suffit de jouer 9 grilles.


    A titre d'exemple, la formule donnant pour N triples donnés, le nombre de grilles minimal pour une réduction au rang inférieur étant : 2*N+1.

    Le seul problème est que pour certaines combinaisons de triples et de doubles, la meilleure réduction obtenue par les logiciels actuels est loin du théorique. Par exemple, pour un 7 triples, l'idéal serait d'obtenir 146 grilles alors que la meilleure réduction actuelle est de 186...


    J'espère vous avoir un peu aidé.

Discussions similaires

  1. Formalisation graphique des algorithmes
    Par David R. dans le forum Algorithmes et structures de données
    Réponses: 14
    Dernier message: 08/12/2012, 11h21
  2. Algorithme de randomisation ... ( Hasard ...? )
    Par Anonymous dans le forum Assembleur
    Réponses: 8
    Dernier message: 06/09/2002, 15h25
  3. recherches des cours ou des explications sur les algorithmes
    Par Marcus2211 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 19/05/2002, 23h18
  4. Recherche de documentation complète en algorithmes
    Par Anonymous dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 29/03/2002, 13h09
  5. Algorithme génétique
    Par Stephane.P_(dis Postef) dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 15/03/2002, 18h14

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo