valentin03 C'est le même fonctionnement sauf erreur.
valentin03 C'est le même fonctionnement sauf erreur.
Ben non. Erreur. Au bingo, il y a forcément un gagnant. Pas au loto.
Au bingo, d'où le nom, le gagnant n'est pas celui qui a rempli sa grille, mais celui qui ayant rempli sa grille est le premier à s'écrier "BINGO !".
Les "doublons" évités ne sont pas des gagnants simultanés mais des grilles dont les enjeux ne peuvent être exactement les mêmes.
Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
Je crois que selon les régions, le jeu 'bingo' s'appelle 'bingo', ou bien 'loto'. Il y a beaucoup de mots comme ça, qui n'ont pas exactement le même sens selon les régions.
Le terme loto regroupe un peu tous les jeux à base de loterie.
illustration : Le jeu décrit est bien celui dont on parle, et il s'appelle 'loto'.
N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.
Les algos pour générer une grille de Bingo et une grille de Loto sont différents, ce sont donc deux jeux différents qui portent des noms différents
Savoir pour comprendre et vice versa.
Ca m'a amusé comme challenge, et voici un code :
Cette fonction génère une feuille de 6 grilles, conforme aux contraintes décrites. Il faut donc appeler cette fonction autant de fois que voulu.
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 PROCEDURE generer_une_feuille() // J'impose d'entrée à toutes mes grilles de respecter les contraintes : Au moins 1 nombre par colonne, et au max 2 // Je sais donc que sur ma feuille, pour la 1ère colonne, j'aurai 3 grilles qui ont 1 seul nombre, et 3 grilles qui ont 2 nombres (la 1ère colonne contient 9 nombres) // Pour les colonnes 2 à 8, j'aurai 2 grilles avec 1 seul nombre, et 4 grilles avec 2 nombres // et pour la colonne 9, j'aurai 1 grille avec 1 seul nombre, et 5 grilles avec 2 nombres, car cette colonnes doit contenir les 11 nombres de 80 à 90. // et bien entendu, d'entrée je sais que chaque grille doit avoir 6 colonnes doubles, et 3 colonnes simples, pour avoir 15 nombres. // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ tb_tay_gc est un tableau de 6 par 9 entiers // tb_tay_gc[Grill,Col] = 1 ou 2 : la grille g, dans la colonne col, aura 1 ou 2 nombres. tmp_nb_coldoubles_g est un tableau de 6 entiers // Nbre de colonnes dubles pour la grille g. Forcément égal à 6 à la fin de la boucle. tmp est un tableau de 0 entiers ch est une chaîne tb est un tableau de 90 entiers // donnera le n° de grille pour chacune des nombres de 1 à 90. deb_col, fin_col , numfeuille est un entier numero, i,n, col, g , ndoubles , tay, k , deja_faits est un entier POUR col = 1 A 9 POUR g = 1 A 6 tb_tay_gc[g,col]=1 // Par défaut, chaque grille, chaque colonne devra contenir 1 seul nombre. On remplacera ce 1 par 2 sur certaines grilles, certaines colonnes. FIN FIN POUR col = 1 A 9 // Pour chacune des 9 colonnes, quelles sont les grilles qui auront 2 éléments pour cette colonne ? ndoubles = 4 // En principe 10 nombres dans chaque colonne, donc 4 grilles ont 2 nombres et 2 grilles ont 1 seul nombre. SI col = 1 ALORS ndoubles = 3 // Exception, la 1ère colonne n'a que 9 nombres, donc seulement 3 grilles ont 2 nombres en colonne 1 SI col = 9 ALORS ndoubles = 5 // Et Exception aussi en colonne 9, il y a 11 nombres entre 80 et 90, donc il faut 5 grilles avec 2 nombres. deja_faits=0 POUR g = 1 A 6 SI tmp_nb_coldoubles_g[g] < 6 ALORS // Si la grille g n'a pas encore 6 colonnes avec 2 nombres SI tmp_nb_coldoubles_g[g] - col = -4 ALORS // Soit la grille doit absolument avoir 2 nombres sur toutes les colonnes restant... et donc on ne se pose pas de question tb_tay_gc[g, col] = 2 tmp_nb_coldoubles_g[g]++ deja_faits ++ SINON // Soit on a le choix, avoir 1 nombre ou bien 2 pour cette grille, cette colonne. TableauAjouteLigne(tmp, g) // Je mets une enveloppe contenant le n°g dans une urne. FIN FIN FIN tay = TableauOccurrence(tmp) // Combien y a-t-il d'enveloppes dans l'urne. POUR i = deja_faits+1 A ndoubles // On a besoin de choisir x grilles qui auront 2 nombres dans cette colonne. k = Hasard(tay) // Je prends une enveloppe au hasard parmi les TAY enveloppes de l'urne. g = tmp[k] // Cette enveloppe contient le n°g tb_tay_gc[g, col] = 2 // La grille g aura 2 nombres dans cette colonne col. tmp_nb_coldoubles_g[g]++ // Et donc, on incrémente ce compteur TableauSupprimeLigne(tmp,k) // Je retire l'enveloppe contenant le n°g de cette urne. tay-- // Il reste donc TAY enveloppes dans l'urne. FIN TableauSupprimeTout(tmp) // Je vide complétement l'urne, pour repartir à 0 pour avoir une situation vierge pour la colonne suivante. FIN // A ce niveau, je sais quelles colonnes de quelles grilles auront 2 éléments, et donc lesquelles auront 1 seul élément. POUR col = 1 A 9 // Je traite les colonnes les unes après les autres. deb_col = 10*col-10 fin_col = 10*col-1 SI col=1 ALORS deb_col = 1 SI col=9 ALORS fin_col = 90 // La colonne en cours devra contenir tous les nombres entre deb_col et fin_col POUR i = deb_col A fin_col TableauAjouteLigne(tmp,i) // Je mets 10 (ou 9 ou 11) enveloppes dans une urne, chaque enveloppe contient un n° entre deb_col et fin_col FIN tay = fin_col-deb_col+1 // TAY est le nombre d'enveloppes dans l'urne POUR g = 1 A 6 // Pour chacune des 6 grilles POUR i = 1 _A_ tb_tay_gc[g, col] // Cette grille g devra contenir soit 1 soit 2 nombres dans cette colonne, ça a été défini au début est stock& dans tb_tay_gc[] k = Hasard(tay) // Je prends une enveloppe au hasard numero = tmp[k] // Cette enveloppe contient le n° Numero tb[numero] = g // Je dis donc que le n° Numero sera dans la grille g TableauSupprime(tmp,k) // Et je retire cette enveloppe de l'urne. tay -- FIN FIN FIN SI ok_verif_doublon = Vrai ALORS // Avant d'écrire cette feuille de 6 grilles dans mon fichier, je vérifie d'abord qu'aucune des 6 grilles n'apparait déjà dans le fichier. POUR gril = 1 A 6 ch = "" POUR i = 1 A 90 SI tb[i]= gril ALORS ch = ch+"1" SINON ch = ch + "0" // Une grille est une chaine de 90 bits 0 ou 1, avec 15 bits à 1 FIN HLitRecherche(liste_grilles,contenu_grille,ch) // Je vérifie si cette chaine de 90 bits n'a pas déjà été écrite dans mon fichier. SI HTrouve ALORS // Si Oui, je quitte, on jette cette feuille de 6 grilles à la poubelle. n_refuses_doublons++ RENVOYER Faux FIN FIN FIN HLitDernier(liste_grilles,k_feuille_grille) // Quel est le dernier n° de feuille existant dans ma base de données. SI HEnDehors(liste_grilles) ALORS numfeuille = 101 SINON numfeuille = liste_grilles.num_feuille+1 // Cette nouvelle feuille sera donc écrite avec le n° numfeuille. FIN // et j'écris dans le fichier POUR gril = 1 A 6 // Pour chacune des 6 grilles de cette feuille ch = "" POUR i = 1 A 90 SI tb[i]= gril ALORS ch = ch+"1" SINON ch = ch + "0" FIN liste_grilles.num_feuille = numfeuille liste_grilles.num_grille = gril liste_grilles.contenu_grille = ch HAjoute(liste_grilles) // Ajout d'une ligne dans le fichier résultat. FIN RENVOYER Vrai
Ensuite, je teste si chacune des 6 grilles de cette feuille est bien nouvelle (pas encore de grille similaire dans ma base de données).
Et si c'est ok, j'écris les 6 grilles dans ma base de données.
En générant 200000 feuilles (et donc 1200000 grilles), je n'ai eu aucun doublon. Il y a en tout environ 100 Milliards de grilles possibles, donc le fait de n'avoir aucun doublon en 1200000 grilles est totalement conforme aux statistiques.
Toute la fin du code (vérification de doublon et écriture dans la base de données) est assez spécifique au langage utilisé... le début est plus intéressant.
N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.
top, merci tbc92.
Je vais étudier tout ça et voir comment adapter en javascript.
Je me suis amusé à faire ça en python.
Code python : 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 import random def generer_schema_grille() : ''' Retourne une grille de 9 * 3 remplie de booléens dont 15 valeurs à True. 3 lignes de 5 valeurs à True avec au min 1 True et max 2 True par colonne. ''' grille = [[False] * 9 for _ in range(3)] # ---- LIGNE 1 : # Choix de 5 index de colonnes au hasard cols_l1 = random.sample(range(9), 5) for col in cols_l1 : grille[0][col] = True # ---- LIGNE 2 # Choix d'index communs de colonnes avec la ligne 1 nb_communs = random.randint(1, 3) cols_communes = random.sample(cols_l1, nb_communs) # Index des colonnes excluant ceux de la ligne 1 cols_l2_restantes = tuple(i for i in range(9) if i not in cols_l1) cols_l2 = cols_communes + random.sample(cols_l2_restantes, 5 - nb_communs) for col in cols_l2 : grille[1][col] = True # ---- LIGNE 3 # Index des colonnes non communes aux deux premières lignes cols_possibles = [i for i in range(9) if i not in cols_communes] # Mise à True des colonnes n'ayant aucune valeur nb_cols = 5 for col in range(9) : if not any(grille[i][col] for i in range(3)) : grille[2][col] = True nb_cols -= 1 cols_possibles.remove(col) # Reste de colonnes à compléter cols_l3 = random.sample(cols_possibles, nb_cols) for col in cols_l3 : grille[2][col] = True return grille def remplir_grille(grille) : ''' Remplit une grille (inplace) de numéros en changeant les valeurs à True. S'appuie sur les index colonne pour choisir les numéros au hasard. ''' for col in range(0, 9) : index_numeros = tuple(i for i in range(3) if grille[i][col]) nb_numeros = len(index_numeros) population = range(col * 10, (col + 1) * 10) numeros = random.sample(population, nb_numeros) for i, n in zip(index_numeros, numeros) : grille[i][col] = n def numeros_grille(grille) : ''' Génère un tuple croissant des numéros de la grille ''' return tuple(sorted(n for l in grille for n in l if n is not False)) def afficher_grille(grille) : ''' Affiche une grille dans le terminal ''' for l in grille : s = ('{:2s}'.format(str(n) if n is not False else ' ') for n in l) print(' '.join(s)) # Génère et affiche de simples grilles while True : grille = generer_schema_grille() remplir_grille(grille) afficher_grille(grille) r = input('Press q to stop ') if r in ('q', 'Q') : break # Test de doublons sur N générations de grilles # Je conseille de ne pas trop aller au delà du million (~350/400mo en mémoire) # 10^7 se comptera en GO en mémoire i = 0 # nb_grilles = 10**6 nb_grilles = 10**4 print('Génération de {:_d} grilles'.format(nb_grilles)) grilles = {} while i < nb_grilles : grille = generer_schema_grille() remplir_grille(grille) numeros = numeros_grille(grille) try : grilles[numeros] except KeyError : # Ok grilles[numeros] = grille i += 1 else : # On est verni (ou pas) print('Doublon !')
En fait la probabilité d'avoir un doublon est tellement faible (j'ai fait un test sur 10 millions (je déconseille)), et pas un doublon), que je me demande à partir de combien de grilles générées il faudrait pour avoir par exemple une chance sur 100 d'avoir un doublon.
Je parle en terme de numéros (sans tenir compte de l'agencement dans la grille).
Le temps ronge l'amour comme l'acide.
Salut bistouille.
Oui c'est clair le risque de doublons de carton plein est trés faible.
Maintenant, idéalement il faudrait aussi qu'il n'y ait aucun doublon de ligne.
Mais là aussi je pense que c'est peu probable.
Une fois que la grille est générée, on n'a fait que la moitié du travail. On a choisi les 15 n°s qui vont figurer sur la grille.
Dans mon cas, je m'assurais qu'il y avait entre 1 et 2 numéros par dizaines.
Reste à disposer ces numéros sur la grille. Et s'il y a des contraintes : ne pas avoir 2 grilles avec des lignes identiques, on a une certaine marge de manoeuvre.
Si on a 5 et 9 à écrire dans la 1ère colonne, on a 6 façons de les disposer. Pour une liste de 15 numéros , on doit avoir à peu près 200000 façons de disposer nos 15 numérons en respectant les contraintes :
- chaque numero est dans le colonne qui lui correspond ( 1 à 9 dans la 1ère colonne, 10 à 19 dans la 2ème colonne ...)
- 5 numéros dans chaque ligne
Donc normalement, on devrait trouver des dispositions qui évitent les doublons de lignes.
Mais ceci n'a pas été implémenté dans les propositions actuelles.
Et comme tu dis, en répartissant les 15 numéros sur la grille au hasard, on a 99.999% de chance de ne pas avoir de doublon de ligne.
N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.
C'est bien plus probable en fait, un simple test le prouve.
Dans mon code, redéfinir la fonction numeros_grille pour qu'elle retourne un ensemble d'ensembles.
Code python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 def numeros_grille(grille) : ''' Génère un set de set de la grille ''' return frozenset(frozenset(n for n in l if n is not False) for l in grille)
Puis modifier la partie du test.
Code python : 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 i = 0 nb_grilles = 10**4 print('Génération de {:_d} grilles'.format(nb_grilles)) grilles = {} nb_doublons = 0 while i < nb_grilles : grille = generer_schema_grille() remplir_grille(grille) numeros = numeros_grille(grille) for cle in grilles : if cle & numeros : nb_doublons += 1 break else : grilles[numeros] = grille i += 1 print(nb_doublons, 'lignes en double capturées')
Bon là, vaut mieux pas s'amuser à faire ce test sur 1 million de grilles, sinon, ça risque de mouliner longtemps
Pour 10 000, ça va encore, c'est quelques secondes et ça peut suffire.
Le temps ronge l'amour comme l'acide.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager