def max_trail( pyramid ):
  if len(pyramid) == 1:
    return pyramid[0][0]
  else:
      for i in range(len(pyramid[1])):
          pyramid[1][i]=max(pyramid[0][i]+pyramid[1][i], pyramid[0][i+1]+pyramid[1][i])
      upper=pyramid[1:]
  return max_trail(upper)
max_trail([[8,6,3,1],[3,4,2],[5,7],[4]])

Return Value 21

-
Edité par Ilan00 19 décembre 2016 à 16:44:12

Bravo

ça m'a l'air pas mal en effet

Je te propose ma solution pour comparer :

def max_trail( pyramid ):
  if len(pyramid) == 1:
    return pyramid[0][0]
  else:
    last, upper = pyramid[0], pyramid[1:]
    for i in range(len(upper[0])):
      upper[0][i] = max( upper[0][i]+last[i], upper[0][i]+last[i+1] )
    return max_trail(upper)

Elle est identique au moment de séparation près.
Comme pour ta version il s'agit d'une fonction récursive terminale, cela signifie que si un appel récursif est fait alors c'est la dernière chose qui est faite. Ce genre de fonction récursive est facilement transformable en version itérative en utilisant une simple boucle.

La version itérative donnerait :

def max_trail_iter( pyramid ):
  while len(pyramid) != 1:
    last, upper = pyramid[0], pyramid[1:]
    for i in range(len(upper[0])):
      upper[0][i] = max( upper[0][i]+last[i], upper[0][i]+last[i+1] )
    pyramid = upper
  return pyramid[0][0]

Merci Beaucoup~!!

Petite question, est ce qu'on pourrai également appliquer la memoization pour éviter que la récursivité ne calcul pas des calculs déjà effectués ?

Alors si on rentre un peu dans les détails, ce que tu as fait s'appelle de la programmation dynamique. Cela ressemble à la technique «diviser pour régner». Dans les deux cas on résout un problème en résolvant des problèmes plus petits et a priori plus simples. La différence essentielle est que dans le cas «diviser pour régner» les sous-problèmes doivent être indépendants, ne pas se recouvrir alors que dans le cas programmation dynamique c'est justement une propriété qu'on recherche.

Une version diviser pour régner de ton problème consisterait en

// ici on considère qu'on a comme paramètre la pyramide
// listée à partir du sommet
// par exemple : [ [4], [5,7], [3,4,2], [8,6,3,1] ]
fonction max_trail(pyramid)
  si longueur(pyramide) = 1 alors
    renvoyer valeur du sommet
  sinon
    sous_pyramide_gauche = gauche(pyramide)
    sous_pyramide_droite = droite(pyramide)
    renvoyer max(
         sommet(pyramide)+max_trail(sous_pyramide_gauche),
         sommet(pyramide)+max_trail(sous_pyramide_droite)
                )

Le problème dans la version diviser pour régner est qu'on effectue plusieurs fois le calcul sur la sous pyramide [ [6,3], [4] ]. Alors un moyen est effectivement de mémoiser les résultats, on pourrait utiliser un dictionnaire → si la pyramide est une clé du dico alors tu as déjà calculé le résultat et tu peux directement le renvoyer, sinon tu calcules le résultat et tu ajoutes ça dans le dico. En gros :

fonction max_trail(pyramid)
  si pyramid dans dico alors
    renvoyer dico[pyramid]
  sinon si longueur(pyramide) = 1 alors
    resultat = valeur du sommet
  sinon
    ...
    resultat = max( ... )
  dico[pyramid] = resultat
  renvoyer resultat

Tu vois que la version diviser pour régner semble plus complexe et nécessite une mémoisation pour éviter plsuieurs calculs identiques alors que la version programmation dynamique est plus simple et ne nécessite aucun mémoisation car aucun calcul n'est dupliqué.

Edit: petite clarification, oui on pourrait utiliser la mémoisation y compris dans le cas programmation dynamique mais pas sur la fonction elle-même mais sur la partie «calcul». Par exemple tu pourrais mémoiser la fonction max pour améliorer ses perfs, mais tu ne mémoiserais plus la fonction elle-même comme dans le cas diviser pour régner.

-
Edité par PicoDev 19 décembre 2016 à 18:11:45

def max_trail_memo( pyramid,memo=None ):
        if memo==None:
                memo={}
        if pyramid in memo:
                return memo[pyramid] #erreur ici
        if len(pyramid) == 1:
                return pyramid[0][0]
        else:
                last, upper = pyramid[0], pyramid[1:]
                for i in range(len(upper[0])):
                        upper[0][i] = max( upper[0][i]+last[i], upper[0][i]+last[i+1] )
                        memo[pyramid]=upper[0][i]
                print memo #pour verifier le dico
                return max_trail(upper)

Mise à part l'erreur, comprends-tu que ça ne sert à rien ?  Il n'y a qu'un et un seul appel récursif vers une pyramide forcément plus petite qui ne pourra donc pas être dans ton dico ? Ça ne sera utile que dans la version diviser pour régner.

Si tu veux vraiment faire de la mémoisation sur plusieurs appels tu peux utiliser le décorateur lru_cache. Tu pourras vérifier l'inutilité sur un appel en checkant la valeur max_trail.cache_info().

Si tu tiens à le faire à la main tu peux créer ton décorateur →

def memoize(f):
  memo = {}
  def memoized(x):
    if x not in memo:            
      memo[x] = f(x)
    return memo[x]
  return memoized

@memoize
def max_trail( pyramid ):
  ...

J'ai suivi ta construction mais le code memoize est plus lent ... 

-
Edité par Ilan00 21 décembre 2016 à 18:37:51