Un p'tit challenge de code
#11
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)
Répondre
#12
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)
Répondre
#13
(06-17-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.
Répondre
#14
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...252_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 2 Amusant je trouve!
Répondre


Sujets apparemment similaires...
Sujet Auteur Réponses Affichages Dernier message
  Security Web [une exo sous forme de challenge a l'ecol] X-ZoD 17 5 686 01-29-2007, 03:59 PM
Dernier message: X-ZoD



Utilisateur(s) parcourant ce sujet : 1 visiteur(s)