1. #1
    Membre régulier
    Profil pro
    Inscrit en
    décembre 2003
    Messages
    352
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : décembre 2003
    Messages : 352
    Points : 73
    Points
    73

    Par défaut Aucune combinaison possible ? Ça paraît dingue

    Salut !

    Contexte du problème :

    Dans ma famille, à Noël, nous (13 personnes) faisons chacun des listes de cadeaux qui nous feraient plaisir, puis nous échangeons nos listes au hasard. Chacun a donc la liste de quelqu'un d'autre (hormis son conjoint).
    Pour cette année, j'ai décidé que l'on changerait un peu le système. En effet, plutôt que de tirer la liste complète de quelqu'un, chacun obtiendrait une liste avec des cadeaux venant de listes différentes. Jusque là, tout va bien.

    J'ai donc conçu un programme qui se charge de cela. Mais voilà, mon programme ne trouve aucune combinaison possible... Je l'ai laissé tourner pendant des heures, il a effectué plus de 116 millions de tirages sans en trouver un seul qui satisfasse aux conditions requises. Ca paraît incroyable...

    Donc, entre autres conditions, il faut que les listes que l'on tire fassent entre 22 et 28€. Et de même, le montant des cadeaux que l'on reçoit doit également faire entre 22 et 28€. Et c'est avec cette dernière condition que ça coince ! Comment est-ce possible qu'il n'y parvienne pas ? J'ai vérifié l'algorithme je ne sais pas combien de fois et tout semble correct...

    Ce que je voudrais savoir, c'est si, mathématiquement parlant, c'est un problème impossible à résoudre ?

    Merci pour vos lumières !

  2. #2
    Membre régulier
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    67
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 67
    Points : 71
    Points
    71

    Par défaut

    Le problème c'est les conditions (s'il n'y a pas de bug dans "<"; ">")
    Elargis les fourchettes jusqu'à ce que ça passe; ou fais à l'envers en partant de fourchettes larges et en réduisant.
    Tu peux vérifier en by-passant les conditions.

  3. #3
    Membre régulier
    Profil pro
    Inscrit en
    décembre 2003
    Messages
    352
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : décembre 2003
    Messages : 352
    Points : 73
    Points
    73

    Par défaut

    J'ai oublié de mentionner qu'il y avait 70 articles (cadeaux) au total.
    D'autre part, au plus j'augmente la fourchette correspondant au montant des cadeaux reçus, au plus vite le programme trouve une combinaison (ce qui est normal). Mais quand je spécifie 22 et 28 comme limites, là, il ne semble rien trouver... Est-ce normal ?

  4. #4
    Membre régulier
    Profil pro
    Inscrit en
    décembre 2003
    Messages
    352
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : décembre 2003
    Messages : 352
    Points : 73
    Points
    73

    Par défaut

    Valentin, tu as répondu pendant que je postais moi-même

  5. #5
    Membre régulier
    Profil pro
    Inscrit en
    décembre 2003
    Messages
    352
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : décembre 2003
    Messages : 352
    Points : 73
    Points
    73

    Par défaut

    J'ai testé entre temps, avec 15 (au lieu de 22) et 35 (au lieu de 28) et le prog a trouvé un bon tirage au bout de 280000 essais ! Y'a de l'espoir !

  6. #6
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Aucune combinaison possible ?

    Bonjour

    Il manque des données dans ton énoncé:
    Dans ma famille, à Noël, nous (13 personnes) ... Chacun a donc la liste de quelqu'un d'autre (hormis son conjoint).
    Combien y a-t-il de couples ? Et de personnes seules ?

    ... chacun obtiendrait une liste avec des cadeaux venant de listes différentes ...
    Combien de cadeaux
    a) figurent-ils sur une liste ?
    b) chaque personne offre-t-elle en tout, aux autres membres du groupe ?


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  7. #7
    Membre régulier
    Profil pro
    Inscrit en
    décembre 2003
    Messages
    352
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : décembre 2003
    Messages : 352
    Points : 73
    Points
    73

    Par défaut

    Il y a 5 couples et 3 célibataires.
    Il y a 70 cadeaux encodés au total.
    Une personne offre au maximum 5 articles.

    Merci pour ton intérêt !

  8. #8
    Membre régulier
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    67
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 67
    Points : 71
    Points
    71

    Par défaut

    Comme ton algo a l'air de fonctionner, tu pourrais le poster, ça pourrait servir à d'autres.

  9. #9
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Aucune combinaison possible ?

    Je comprends vite, mais il faut bien m'expliquer .

    Donc ... il faut que les listes que l'on tire fassent entre 22 et 28€. Et de même, le montant des cadeaux que l'on reçoit doit également faire entre 22 et 28€
    Donc:
    a) le prix total des listes, comme celui des cadeaux, est compris entre 22 et 28 €;
    b) le prix de chaque cadeau est obligatoirement compris entre 22/5 = 4.4 = 5 € (en arrondissant à l'entier supérieur) et 28 €;
    c) un cadeau donné ne peut être offert plusieurs fois.

    L'ensemble des cadeaux, comme celui des donneurs, peut être représenté par une matrice d'entiers au format byte:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    CONST NtotC = 70; NtotP = 13;
    
    TYPE Tab_70 = ARRAY[1..NtotC, 0..2] OF Byte;
    TYPE Tab_13 = ARRAY[1..NtotP, 0..1] OF Byte;
    
    VAR ListeC: Tab_70;
        ListeP: Tab_13;
    étant admises les conventions suivantes:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    ListeC[i, 0]: Prix du cadeau ;  ListeC[i, 1]: Donateur ; ListeC[i, 2]: Bénéficiaire ;
    ListeP[i, 0]: Prix total payé ; ListeC[i, 1]: Nombre de cadeaux offerts ;
    1°) Un premier tirage aléatoire (ou l'introduction d'une liste constante), accompagné de la mise à zéro des autres termes, permet l'initialisation de la première matrice:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    PROCEDURE Init_LC(VAR L_: Tab_70);
      VAR i, m: Byte; Lc: Tab_70;
      BEGIN
        Randomize;
        FOR i:= 1 TO NtotC DO BEGIN
                                m:= Random(24); Lc[i, 0]:= m + 5;          // 5 <= Prix <= 5 +23 = 28
                                Lc[i, 1]:= 0; Lc[i, 2]:= 0;                   
                              END;
        L_:= Lc
      END;
    2°) Un second tirage simule les choix de toutes les personnes, qui sélectionnent un nouveau cadeau jusqu'à la vérifcation des conditions: ((22 <= Prix total <= 28) et (Ncad <= 5)), et en évitant de prendre un objet déjà réservé.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    PROCEDURE ChoixC(VAR L_p: Tab_13; VAR L_c: Tab_70);
      VAR i, j, k, Ncad, PrixT: Byte;
      BEGIN
        FOR i:= 1 TO NtotP DO
          FOR j:= 0 TO 1 DO L_p[i, j]:= 0;           // Mise à zéro de tous les termes
        FOR i:= 1 TO NtotP DO
          BEGIN
            Ncad:= 0; PrixT:= 0;
            REPEAT
              REPEAT
                k:= Random[NtotC); Inc(k);
              UNTIL (L_c[k, 2]=0);                   // Tirage d'un objet non réservé
              Inc(Ncad); Inc(PrixT, L_c[k]
            UNTIL ((22<=PrixT) AND (PrixT<=28)) OR (Ncad=5);
            L_c[k, 2]:= i;                           // Réservation du cadeau par le bénéficiaire potentiel (i)  
            L_P[i, 1]:= PrixT; L_P[i, 2]:= Ncad      // Mémorisation du prix payé et du nombre de cadeaux
          END;
      END;
    L'appel des deux procédures sera fait par les instructions:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    Init_LC(ListeC);
    ChoixC(ListeP, ListeC);
    Il vaut mieux que je m'arrête à ce stade, des bourdes ayant pu s'accumuler en l'absence de compilation.

    Reste à coder la répartition aléatoire des donneurs sur les cadeaux sélectionnés, en attribuant une valeur positive aux éléments ListeC[i, 1] de la première matrice, sous réserve des restrictions:
    a) ListeC[k, 1] <> ListeC[p, 2] : pas de cadeau à soi-même, cela nuit à l'amblaince;
    b) ListeC[p, 1]2 + ListeC[p, 1]2 <> 5, 25, 61, 113 et 181 : pas de cadeaux entre conjoints ((1, 2) ; (3, 4) ; (5, 6) ; (7, 8) ; (9, 10)); vérifier l'exclusivité de cette condition écrite à l'improviste.

    Vous n'allez pas vous ennuyer, à Noël


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  10. #10
    Membre régulier
    Profil pro
    Inscrit en
    décembre 2003
    Messages
    352
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : décembre 2003
    Messages : 352
    Points : 73
    Points
    73

    Par défaut

    Oulalalah...
    Je ne saisis pas trop bien tout ce que tu as écrit ci-dessus...

    En fait, je voulais juste savoir si c'était possible qu'aucun tirage validant les conditions ne sorte... même après un nombre incroyable d'essais !

    Ah oui, le montant d'un article va de 1€ à 28€.
    Et pour rappel, le montant d'une liste tirée par le programme et attribuée à une personne va de 22€ à 28€.
    Le montant total des cadeaux qu'on reçoit va de 22€ à 28€.
    Le nombre maximum de cadeaux qu'on a sur la liste que l'on reçoit par le programme est de 5 (au minimum, il y a en 1).
    Une personne ne peut avoir de cadeaux de son conjoint ou de soi-même sur la liste qu'elle reçoit.
    Un cadeau ne peut être tiré plus d'une fois.
    Tous les cadeaux ne sont pas nécessairement tirés.

    Dans mon cas, il y a 70 articles encodés par les personnes. Il y a 13 personnes, dont 5 couples.

    Voici mon code (écrit en C#) :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
                int cptgeneral = 0;
                label1.Visible = true;
                checkBox1.Enabled = false;
                Random rand = new Random();
                Double montantliste = 0;
                Double checkmontantliste = 0;
                int cstmontantinfliste = 22;
                int cstmontantsupliste = 28;
                int cstmontantrecuinf = 22;
                int cstmontantrecusup = 28;
                int nbmaxarticlesparlistetiree = 5;
                Boolean test = false;
                Boolean resetboucle = false;
                int j = 0;
                int k = 0;
                int cptnbarticles = 0;
                int cptnbarticlesparliste = 0;
                int cptpersonnes = 0;
                int nbarticletotal = 0;
                int checkcptnbarticlesparliste = 0;
                int nbtotalpersonnes = BL.PersonneBL.CombienPersonnes();
                List<BO.PersonneBO> Lalistepersonnes;
                PersonneBO objpersonne;
                Lalistepersonnes = BL.PersonneBL.SelectAllListPersonne();
                Lalistepersonnes.Sort();
                List<ArticleBO> Lalistearticles;
                Lalistearticles = BL.ArticleBL.SelectAllListArticle();
                List<ArticleBO>[] Tablist = new List<ArticleBO>[nbtotalpersonnes];
                for (int i = 0; i < Tablist.Length; i++) Tablist[i] = new List<ArticleBO>();
                nbarticletotal = Lalistearticles.Count();
                int[] Tabdejapris = new int[nbarticletotal];
                do
                {
                    for (int i = 0; i < nbarticletotal; i++) Tabdejapris[i] = 0;
                    resetboucle = false;
                    cptnbarticles = 0;
                    cptpersonnes = 0;
                    do
                    {
                        cptnbarticlesparliste = 0;
                        montantliste = 0;
                        do
                        {
                            k = 0;
                            test = false;
                            do
                            {
                                if (Lalistearticles[k].Prix <= (cstmontantsupliste - montantliste) && Tabdejapris[k] == 0) test = true;
                                k++;
                            }
                            while (k < nbarticletotal && test == false);
                            if (test == true)
                            {
                                j = rand.Next(nbarticletotal);
                                if (Tabdejapris[j] == 0)
                                {
                                    if (montantliste + Lalistearticles[j].Prix <= cstmontantsupliste)
                                    {
                                        objpersonne = BL.PersonneBL.QuellePersonne(Lalistearticles[j].IdArticle);
                                        if (objpersonne.IdPersonne != Lalistepersonnes[cptpersonnes].IdPersonne)
                                        {
                                            if (checkBox1.Checked == true)
                                            {
                                                if (objpersonne.IdConjoint != Lalistepersonnes[cptpersonnes].IdPersonne)
                                                {
                                                    Tabdejapris[j] = 1;
                                                    montantliste += Lalistearticles[j].Prix;
                                                    Tablist[cptpersonnes].Insert(cptnbarticlesparliste, Lalistearticles[j]);
                                                    cptnbarticlesparliste++;
                                                    cptnbarticles++;
                                                }
                                                else test = false;
                                            }
                                            else
                                            {
                                                Tabdejapris[j] = 1;
                                                montantliste += Lalistearticles[j].Prix;
                                                Tablist[cptpersonnes].Insert(cptnbarticlesparliste, Lalistearticles[j]);
                                                cptnbarticlesparliste++;
                                                cptnbarticles++;
                                            }
                                        }
                                        else test = false;
                                    }
                                }
                            }
                        }
                        while (montantliste <= cstmontantinfliste && cptnbarticles < nbarticletotal && test == true);
                        cptpersonnes++;
                        if (test == false || cptnbarticles >= nbarticletotal) resetboucle = true;
                    }
                    while (cptpersonnes < nbtotalpersonnes && resetboucle == false);
                    if (resetboucle == false)
                    {
                        for (int i = 0; i < nbtotalpersonnes; i++)
                        {
                            checkcptnbarticlesparliste = 0;
                            checkmontantliste = 0;
                            foreach (ArticleBO obja in Tablist[i])
                            {
                                checkcptnbarticlesparliste++;
                                checkmontantliste += obja.Prix;
                            }
                            if (checkcptnbarticlesparliste > nbmaxarticlesparlistetiree || checkmontantliste <= cstmontantinfliste)
                            {
                                resetboucle = true;                            
                            }
                        }
                    }
                    if (resetboucle == false)
                    {
                        for (int i = 0; i < nbtotalpersonnes; i++)
                        {
                            foreach (ArticleBO objar in Tablist[i])
                            {
                                PersonneBO objpe = BL.PersonneBL.QuellePersonne(objar.IdArticle);                                                                                                               
                                for (int l = 0; l < nbtotalpersonnes; l++)
                                {
                                    if (objpe.IdPersonne == Lalistepersonnes[l].IdPersonne)
                                    {
                                        Lalistepersonnes[l].Montant_recu += objar.Prix;                                    
                                    }
                                }                            
                            }
                        }
                        for (int i = 0; i < nbtotalpersonnes; i++)
                        {
                            if (Lalistepersonnes[i].Montant_recu < cstmontantrecuinf || Lalistepersonnes[i].Montant_recu > cstmontantrecusup)
                            {
                                resetboucle = true;                            
                            }                        
                        }
                    }
                    if (resetboucle == true)
                    {
                        for (int i = 0; i < nbtotalpersonnes; i++)
                        {
                            Tablist[i].Clear();
                            Lalistepersonnes[i].Montant_recu = 0;
                        }
                        cptgeneral++;                    
                    }
                }
                while (resetboucle == true);

    Voilà, ce sera certainement très obscur et compliqué à décortiquer pour celui qui veut lire; d'autre part, il y a surement de gros défauts dans l'écriture, je le conçois sans problèmes !

  11. #11
    Membre régulier
    Profil pro
    Inscrit en
    décembre 2003
    Messages
    352
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : décembre 2003
    Messages : 352
    Points : 73
    Points
    73

    Par défaut

    Donc, en gros, ce que fait ce morceau de code, c'est de créer 13 listes de cadeaux parallèlement à une liste de 13 personnes; un peu plus loin dans le code (non publié ci-dessus), on attribue une liste de cadeaux à chaque personne !

    La 1ère partie du code (jusqu'à la ligne 92) crée 13 listes de cadeaux; les deux blocs de code suivants vérifient qu'une liste contient 5 cadeaux max, que le montant de chaque liste générée ne dépasse pas 28€ et que le montant de cadeaux reçus soit entre 22 et 28€.

    Si la variable "test" vaut à un moment donné "false" et/ou "resetboucle" vaut "true", le tirage est considéré comme mauvais et on recommence !

    Voilà !

  12. #12
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Aucune combinaison possible ?

    J'ai codé l'étalement des prix de 5 à 28 € pour éviter un coût total sur 5 tirages inférieur à 22 € (5 * 4 = 20 €).
    Ah oui, le montant d'un article va de 1€ à 28€.
    Le programme doit normalement conduire à une solution conforme. Il se lit pratiquement comme du pseudo-code.

    Pour n'avoir quasiment rien obtenu,
    ... il a effectué plus de 116 millions de tirages sans en trouver un seul ...
    tu as sûrement mis quelque part des conditions incompatibles.
    Regarde celles qui concernent les prix.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  13. #13
    Membre régulier
    Profil pro
    Inscrit en
    décembre 2003
    Messages
    352
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : décembre 2003
    Messages : 352
    Points : 73
    Points
    73

    Par défaut

    Citation Envoyé par wiwaxia Voir le message
    J'ai codé l'étalement des prix de 5 à 28 € pour éviter un coût total sur 5 tirages inférieur à 22 € (5 * 4 = 20 €).


    Le programme doit normalement conduire à une solution conforme. Il se lit pratiquement comme du pseudo-code.

    Pour n'avoir quasiment rien obtenu,

    tu as sûrement mis quelque part des conditions incompatibles.
    Regarde celles qui concernent les prix.
    Mais comment comprendre qu'avec par exemple une fourchette de 16/34 (au lieu de 22/28), ça fonctionne alors ?

  14. #14
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Aucune combinaison possible ?

    ... ce que fait ce morceau de code, c'est de créer 13 listes de cadeaux parallèlement à une liste de 13 personnes ...
    Pourquoi 13 listes ? Elles n'ont aucun élément commun, du fait de l'attribution des cadeaux à un destinataire unique; il est beaucoup plus simple de consigner ce dernier dans la "liste" des cadeaux (qui sera une matrice - solution adoptée - ou une liste d'enregistrements).
    Ton code doit être épouvantablement compliqué.

    # PS:
    J'ai testé entre temps, avec 15 (au lieu de 22) et 35 (au lieu de 28) et le prog a trouvé un bon tirage au bout de 280000 essais
    Avec un semblable rendement (1 / 280000) les conditions de sélection sont vraiment trop sévères !


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  15. #15
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Aucune combinaison possible ?

    Si tu procèdes en gros à 5*13 = 65 tirages indépendants sur les 70 cadeaux disponibles, tu as toutes chances de tirer au moins 2 fois le même, sans même parler des conditions sur les coûts ... Il n'est pas étonnant, dans ces conditions, que cela ne donne rien.
    La probabilité de tirer 65 cadeaux différents est
    p = (70/70)*(69/70)*(68/70)*(67/70)* ... *(6/70) = (70!)/(5!*7065) = 1.197857E100/(1.2E2*1.435036E129) = 0.695602E-31 (d'après ma calculette).
    Autant dire que c'est perdu d'avance ... même si ton code est par ailleurs correct.

    Mon programme, qui n'a rien d'extraordinaire, fonctionne (enfin, j'espère ...) parce que les conditions de sélection interviennent à chaque tirage.

    #
    Citation Envoyé par Mike888 Voir le message
    Mais comment comprendre qu'avec par exemple une fourchette de 16/34 (au lieu de 22/28), ça fonctionne alors ?
    Parce que le prix total pouvant descendre à 5*1 = 5 € , la probabilité d'un tirage acceptable est fortement augmentée si tu abaisses le seuil inférieur de 22 à 16 €.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  16. #16
    Membre régulier
    Profil pro
    Inscrit en
    décembre 2003
    Messages
    352
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : décembre 2003
    Messages : 352
    Points : 73
    Points
    73

    Par défaut

    D'accord, mais il y a des tests que je ne peux faire qu'en fin de tirage et pas à chaque sélection de cadeaux...

  17. #17
    Membre régulier
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    67
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 67
    Points : 71
    Points
    71

    Par défaut

    Tel quel l'algo tourne tant qu'il n'y a pas de solution.
    Pour être sûr qu'il n'y en a pas il faut lui faire explorer toutes les combinaisons, mettre un renvoi d'info en fin d'exploration et attendre la fin.
    Mais il faudrait calculer le nombre de combinaisons pour savoir à quoi s'attendre en temps de calcul.

  18. #18
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Aucune combinaison possible ?

    Il y a pour l'essentiel deux sortes de tirages sous condition:
    a) le choix des cadeaux par les bénéficiaires, qui doit s'accompagner d'une marque de réservation afin que les objets ne soient pas demandés plusieurs fois - j'ai tenté de montrer à quelle impasse pouvait conduire une série de tirages indépendants; d'où la nécessité d'attribuer à chaque cadeau au moins deux paramètres: le prix, plus une autre grandeur permettant de savoir s'il a déjà été choisi.
    b) la répartition aléatoire des cadeaux sélectionnés sur les donneurs, que je n'ai pas codée, mais dont les contraintes sont beaucoup moins sélectives (il s'agit des incompatibilités de personnes, qui ont été sommairement évoquées).

    La procédure ChoixC(ListeP, ListeC) a été écrite et sommairement commentée; si la personne de rang (11) porte son choix sur le 51ème objet valant 25 €, la ligne correspondante passe de
    < ListeC[51, 0] = 25 , ListeC[51, 1] = 0 , ListeC[51, 2] = 0 > à
    < ListeC[51, 0] = 25 , ListeC[51, 1] = 0 , ListeC[51, 2] = 11 > ;
    le 3me élément devient positif, marquant ainsi la réservation du cadeau.
    Cette condition d'attribution unique se retrouve dans la même procédure:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
              REPEAT
                k:= Random[NtotC); Inc(k);
              UNTIL (L_c[k, 2]=0);
    Il y a un ordre de priorité implicite que j'ai allègrement négligé: les cadeaux sont successivement réservés par les personnes de rang ( 1 > 2 > 3 > ... > 13 ) ; rien n'interdit d'employer une liste constante I1[i], pour insérer une permutation appropriée des 13 premiers entiers et définir un nouvel ordre de priorité décroissante:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    CONST I1: Tab_13 = (5, 8, 11, 12, 1, 3, 4, 9, 13, 2, 6, 7, 10);
    La procédure décrite deviendrait:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    PROCEDURE ChoixC(VAR L_p: Tab_13; VAR L_c: Tab_70);
      CONST I1: Tab_13 = (5, 8, 11, 12, 1, 3, 4, 9, 13, 2, 6, 7, 10);
      VAR i, j, k, Ncad, PrixT: Byte;
      BEGIN
        FOR i:= 1 TO NtotP DO
          FOR j:= 0 TO 1 DO L_p[i, j]:= 0;           // Mise à zéro de tous les termes
        FOR i:= 1 TO NtotP DO
          BEGIN
            Ncad:= 0; PrixT:= 0;
            REPEAT
              REPEAT
                k:= Random[NtotC); Inc(k);
              UNTIL (L_c[k, 2]=0);                   // Tirage d'un objet non réservé
              Inc(Ncad); Inc(PrixT, L_c[k]
            UNTIL ((22<=PrixT) AND (PrixT<=28)) OR (Ncad=5);
            L_c[k, 2]:= I1[i];                               // Réservation du cadeau par le bénéficiaire potentiel (i)  
            L_P[I1[i], 1]:= PrixT; L_P[I1[i], 2]:= Ncad      // Mémorisation du prix payé et du nombre de cadeaux
          END;
      END;


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  19. #19
    Membre régulier
    Profil pro
    Inscrit en
    décembre 2003
    Messages
    352
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : décembre 2003
    Messages : 352
    Points : 73
    Points
    73

    Par défaut

    Wiwaxia, tu as une capacité d'abstraction très étonnante !...
    Je vais être sincère et d'ailleurs, ça me peine franchement, mais je ne comprends pas la moitié de ce que tu racontes !

  20. #20
    Membre éclairé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    449
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 449
    Points : 883
    Points
    883
    Billets dans le blog
    5

    Par défaut Aucune combinaison possible ?

    J'en suis sincèrement désolé, moi aussi ... Faute de temps, la rédaction du dernier message (que je viens de compléter) était en effet menée au pas de charge.

    Je me doute que le déchiffrement d'un programme peut se révéler éreintant. Peux-tu au moins saisir le plan de ce qui est proposé ? Je pourrais toujours rajouter des précisions, là où cela pourrait être nécessaire.

    D'autant que le programme que tu as toi-même mis au point semble fonctionner; la faiblesse rédhibitoire de son rendement vient sans doute de l'ordre défectueux dans lequel interviennent les restrictions.
    Mais cela te demandera un sacré travail, parce qu'il te faudra reprendre toute la structure de l'ensemble.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

Discussions similaires

  1. Combien de combinaison possible pour uniqueidentifier
    Par NicoNGRI dans le forum MS SQL-Server
    Réponses: 1
    Dernier message: 26/10/2006, 16h49
  2. Réponses: 16
    Dernier message: 20/10/2006, 17h31
  3. trouver les combinaisons possibles d'un tableau ?
    Par titoumimi dans le forum Général Algorithmique
    Réponses: 12
    Dernier message: 20/09/2006, 21h29
  4. toutes les combinaisons possibles
    Par marocleverness dans le forum Général Algorithmique
    Réponses: 6
    Dernier message: 29/05/2006, 01h11
  5. Sortir d'un tableau les combinaisons possibles
    Par juelo dans le forum Général Algorithmique
    Réponses: 33
    Dernier message: 26/03/2006, 18h11

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