Autre > nimportnawac

math et molkky

(1/1)

varzil:
Parce que je ne vais pas répondre par SMS à la question que Didier m'a posé, je vais poster ici.
La question est de savoir combien il y a de combinaisons au molkky pour atteindre 50 sachant que 12+12+12+12+2 est différent de 12+2+12+12+12

Pour répondre rapidement à Didier, j'ai déjà un algorithme de début 2020 puisque qqn m'avait demandé (suite à un entretien d'embauche), le nombre de façons d'obtenir 14 en faisant des sommes de 1,2 et 3. C'est pareil en remplacant 14 par 50 et 3 par 12
Le problème se rapproche du nombre de compositions d'un entier https://fr.wikipedia.org/wiki/Composition_(combinatoire) qui est très simple à dénombrer sauf qu'ici, on veut se limiter à des valeurs plus petites que 12.
Notons que les 2^49 compositions fournissent une borne supérieure au problème de environ 5,6*10^14 soit 560 mille milliards (c'est peu par rapport au nombre de parties d'échecs ;))

Mon algorithme c'est que je calcule toutes les compositions, parce que c'est facile, et ensuite je garde seulement celles qui utilisent les valeurs acceptables (ici entre 1 et 12). Sauf que le temps de calcul est doublé à chaque fois qu'on augmente de 1 et si je trouve environ 1 million de possibilités pour jouer au molkky en 21 points en 16 sec de calculs, pour avoir la réponse pour 50 il me faudrait environ 272 ans ( on peut sans doute diviser par 10-50 en réécrivant le code dans un autre langage plus rapide mais sans doute que la mémoire de l'ordi saturerait avant puisqu'il me faudrait environ 1 million de téra-octets...)
Bref, je n'ai pas la réponse pour des raisons pratiques mais on devrait se situer autour de 100 à 500 mille milliards je pense

Didshrek:
Je savais que je pouvais compter sur toi  :)

Navigation

[0] Index des messages