+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Général (https://jeuweb.org/forumdisplay.php?fid=36)
+--- Forum : Blabla (https://jeuweb.org/forumdisplay.php?fid=42)
+--- Sujet : Un p'tit challenge de code (/showthread.php?tid=3714)
Pages :
1
2
RE: Un p'tit challenge de code - Xenos - 17-06-2018
On doit pouvoir trouver un nombre N de tirages de rand5, faire la somme de tous ces tirages, calculer la probabilité de chaque nombre de [0;5^N[ et faire en sorte de "tomber juste" pour avoir une correspondance type 0..17 => 0, 18..23 => 1; 24..26 => 2; 26..31 => 3 etc
bref, la somme des rand5() donne des nombres dont "le milieu" est le plus probable, et on doit pouvoir s'en servir pour faire le mapping avec rand7 (non-linéaire)
RE: Un p'tit challenge de code - Xenos - 17-06-2018
Bon, je n'y arrive pas :\
La seule preuve d'impossibilité de "tomber juste sans risque de tourner en rond à l'infini", c'est que si on chaine N tirages aléatoires de [0;5[, alors on a 5 puissance N résultats possibles. Or, 5^N ne pourra jamais être divisé en 7 parts égales, et donc, il y aura forcément des nombres de [0..7[ qui auront plus de chances de sortir que les autres.
(mais je trouve la "preuve" vraiment légère)
RE: Un p'tit challenge de code - Thêta Tau Tau - 18-06-2018
(17-06-2018, 08:49 PM)Xenos a écrit : mais je trouve la "preuve" vraiment légère
Pour moi, la preuve est suffisante.
Si on tire n dés, on a 5^n combinaisons possibles, comme 5^n n'est pas divisible par 7, on ne peux pas diviser les combinaisons possibles en 7 part égales, quelque soit les opérations qu'on applique au dés.
Le seul moyen d'y arriver c'est donc d'avoir n=infini.
RE: Un p'tit challenge de code - Xenos - 19-06-2018
Je ne la trouve pas trop formelle... Même si elle semble acceptable et que le problème a déjà été posé sur MathExchange: https://math.stackexchange.com/questions/185570/how-to-generate-equiprobable-numbers-with-a-random-generator#comment428252_185574 (d'une manière différente, mais cela revient au même).
Edit:
Je me noies peut-être, mais la convergence la plus rapide devrait donc être de faire 6 tirages dans l'algo de Meraxes et non 2...
Si on fait 2 tirages, on a 5^2 = 25 résultats différents possibles. Or 25 mod 7 = 4 donc on a 4 chances sur 25 de devoir refaire un tirage double. Et (4/25)² d'en faire 4. Donc, on a (4/25)^3 = 0.004096 chances de devoir faire plus que 6 tirages.
Si on fait 6 tirages, on a 5^6 = 15625 résultats différents possibles. Or 15625 mod 7 = 1, donc on a 1 chance sur 15625 = 0.000064 de devoir refaire un tirage de 6. Ce nombre étant plus petit que 0.004096, on a meilleur temps de faire des paquets de 6 tirages.
En revanche, en moyenne, faire des paquets de 6 tirages donnera une moyenne de 6*15625/(15625 - 1) = 6.000384 tirages avant d'avoir un résultat valide (de sortir de l'algo de Meraxes). Alors que faire des paquets de 2 tirages donnera une moyenne de 2*25/(25 - 4) = 2.381 tirages avant d'avoir un résultat valide.
Le plus fiable sera donc de faire 6 tirages, mais le plus économe en temps de calcul sera d'en faire 2
Amusant je trouve!