Inscription / Connexion Nouveau Sujet
Optimisation d'un dé à 6 faces
Bonsoir,
Je vous propose un petit problème d'optimisation d'un dé à 6 faces. Les faces seront numérotées avec des entiers strictement positifs.
On considère un entier P strictement positif.
Définitions
* On dit que P est atteignable en moins de N coups lorsqu'il est possible d'atteindre P en maximum N lancers de dés (en additionnant les valeurs obtenues successivement).
* On dit que P est "totalement atteignable" en moins de N coups lorsque P est atteignable en moins de N coups, et que tous les entiers compris entre 1 et P sont également atteignables en moins de N coups.
La question : quel est le plus grand entier totalement atteignable en moins de 4 coups ? Pour quelle(s) numérotation(s) des faces du dé ?
Pour vous aider, je propose ci-dessous une fonction python qui permet de calculer la "performance" d'une numérotation donnée :
Cliquez pour afficherAmusez-vous bien
Salut,
Une version un peu different de ton code:
Cliquez pour afficherEn utilisant ce code, j'obtiens que le mieux est le dé (1, 3, 10, 15, 37, 48) qui permet d'obtenir tous les nombres de 0 à 107 en 4 lancés ou moins.
Ça reste de la force brute et je n'ai pas réussi à déterminer un schéma. Pour l'instant
salut
LittleFox : excuse moi de t'embêter à nouveau avec python mais j'ai une question et je ne trouve pas la réponse !!
tu écris dans la ligne def et juste avant les deux points -> int
est-ce obligatoire ? ou plutôt cela impose-t-il quelque chose que d'écrire cela ?
merci par avance 
@carpediem
Pas de soucis, ça me fait plaisir
C'est une notation optionnelle: Le typing 
.
Je déclare que ma fonction retourne un int. Cela n'a aucune impact lors du runtime mais permet comme les commentaires d'être plus lisible.
Aujourd'hui, de nombreux outils s'aident de ces annotations pour vérifier la cohérence du code avant même de le faire tourner.
Mais rien n'est obligatoire.
De la même façon, je déclare que j'attends un tuple de int et un int en entrée (d'ailleurs ça devrait être tuple[int,...] 
J'espère que c'est plus clair
ha merci très beaucoup !!
j'avais cherché sur ce même site mais je ne savais pas que ça s'appelait du "typing" et je regardais dans les fonctions ... j'aurions pu cherché longtemps !!
merci !! 
Bonsoir à tous,
@LittleFox
J'arrive à faire (un tout petit peu) mieux
Et tout comme toi je ne connais pas de méthode qui n'utilise pas du calcul "intensif".
En modifiant un tout petit peu mon code, j'arrive à aller bien plus vite mais ça reste de la force brute.
Cliquez pour afficherJ'obtiens deux dés qui couvrent tous les nombres de 1 à 108:
Cliquez pour afficherCelà correspond à l'oeis
Toujours pas trouvé de méthode plus efficace. Le problème vient de solutions comme celle-ci pour 3 faces et 2 lancés.
On couvre de 0 à 8 avec (1,3,4).
Le 6 est couvert par 3+3 qui tombe juste pile mais n'utilise pas le 4.
Bonsoir,
Bravo ! Et j'ajoute que j'admire la brièveté du code
Je n'obtiens que ces deux-là également avec un algo génétique.
Par contre, comment arrives-tu à trouver 2 configurations distinctes avec un code (a priori) déterministe et qui ne renvoie qu'une solution ?
Bonne soirée
Merci 😁
J'ai retravaillé le code plusieurs fois 😅
Tu peux passer un prefix à solve pour obtenir des solutions avec un préfixe différent.
Il y a eu une version avec des prints intermédiaires à un moment 😉
Bonjour,
J'ai essayé à la main et je suis retombé sur 1,4,9,16,38,49 mais
comment trouver 72 en 4 coups?
Bonjour,
Bonjour,
J'ai essayé à la main et je suis retombé sur 1,4,9,16,38,49 mais
comment trouver 72 en 4 coups?
72 = 38 + 16 + 9 + 9
Voici une fonction python permettant de tester un nombre étant donné des faces de dé (la décomposition n'est pas forcément la meilleure mais elle est compatible avec la contrainte du nombre de lancers autorisés):
def decompose(n, n_list, len_max, accu=[]):
if n == 0:
return accu # success
tmp = [x for x in n_list if (len_max-len(accu))*x >= n and x <= n]
if not tmp: # failure
return None
for elt in tmp:
l=decompose(n-elt, n_list, len_max, accu + [elt])
if l is not None:
return l
Utilisation:
decompose(72, [1,4,9,16,38,49], 4)Une version nettoyée en utilisant les générateur
def decompose(n, n_list, len_max, accu=()):
if n == 0:
yield accu
return
for i, x in enumerate(n_list):
if x <= n <= len_max * x:
yield from decompose(n - x, n_list[:i+1], len_max - 1, accu + (x,))Au passage, je génère toutes les solutions et j'évite de passer deux fois par la même solution. Par exemple pour decompose(7, [3,4], 2).
Utilisation:
print(*decompose(72, [1, 4, 9, 16, 38, 49], 4), sep='\n')Ou, si on ne veut avoir que la première solution:
next(decompose(72, [1, 4, 9, 16, 38, 49], 4), None)
Hmm, il y a des erreurs dans la liste. D'où vient le 7 dans 11 = 4+7?
Voici ma liste:
Cliquez pour afficherOn voit qu'il n'y a pas plus de 3 représentations possible pour chaque nombre.
Les premiers nombres nécessitant une nouvelle face sont:
1 = 1
5 = 4 + 1
11 = 9 + 1 + 1
24 = 16 + 4 + 4
39 = 38 + 1
53 = 49 + 4
On peut aller assez loin sans le 16
Annuler
connectez vous