Forum de mathématiques - Bibm@th.net

Apericube34

Invité

Problème 193 des défis Turing

Salut,
Je suis en école d'info et j'ai un problème analogue à celui qu'on peut trouver sur le site apprendre-en-ligne.net, le problème 193 des défis Turing. J'ai exactement le même exercice mais avec le traîneau mesurant 64 unités et je n'arrive pas à trouver une bonne implémentation pour résoudre ce problème. Les IA sont perdues car les chiffres trop grands, même ChatGPT o1 me trouve des résultats différents à chaque fois.

Si quelqu'un saurait trouver une bonne implémentation, je vous en serais très reconnaissant merci !

Apericube34

Invité

Re : Problème 193 des défis Turing

J'ai fini par trouver la solution. En python ça donne :

def ways_dp(m, n):
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        dp[i] = dp[i - 1]
        for length in range(m, i + 1):
            if i - length - 1 >= 0:
                dp[i] += dp[i - length - 1]
            else:
                dp[i] += 1
    return dp[n]

print(ways_dp(4, 64))

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Problème 193 des défis Turing

Bonsoir,

Ah oui, très joli !

Perso j'avais pensé à la récursivité, une fonction qui plaçait un colis puis qui s'appelait pour placer le colis suivant ainsi de suite jusqu'à un blocage, puis qui revenait en arrière pour placer plus loin, et quand tout était épuisé pour ce colis on recommençait avec plus grand, ça marchait plutôt bien pour les petits traîneaux (j'obtiens les mêmes valeurs que ton programme pour des traîneaux plus courts) mais au-delà de la quarantaine les temps devenaient franchement dissuasifs et il m'était impossible de résoudre le problème. Et pas de quoi être fier, mon code faisait un nombre de lignes monstrueux, donc un bravo sincère.