Bonsoir a tous,

Je dois écrire une fonction récursive qui parcours une liste pyramidale c'est a dire [[8,3,6,1],[4,5,2],[5,2],[4]] trouver le terme maximale de chaque ligne et calculer la somme totale.

En commencant di haut de la pyramide, len =1, puis quand on "descend" on peux additionner que le membre en dessous seulement soit celui de  droite ou de gauche.

Quelles seraient ici les conditions de base ?

Merci !

-
Edité par Ilan00 17 décembre 2016 à 17:58:44

Bonjour,

si je décode bien ce que tu dis, tu pars d'un triangle de nombre comme :

   4
  5 2
 4 5 2
8 3 6 1

Et tu dois trouver la plus grande somme possible en partant du haut du triangle puis en ajoutant soit le nombre en-dessous à gauche soit en-dessous à droite. La solution de l'exemple serait donc 21 = 4 (sommet)  + 5 (gauche) + 4 (gauche) + 8 (gauche).

Déjà un cas simple : si ton triangle se réduit à un nombre alors la solution est ce nombre. Pour réduire la taille du problème il faut pouvoir enlever une ligne du triangle.

On note \(T = [ L_1, …, L_{n-1}, L_n ]\) le triangle où les \(L_i\) représentent les lignes de longueur i ; donc dans l'exemple on a \(T = [ L_1=(4), L_2=(5,2), L_3=(4,5,2), L_4=(8,3,6,1) ]\). Si tu arrives à prouver que \(T' = [ L_1, …, L'_{n-1} ]\) a la même solution que \(T\) avec \(L'_{n-1} = \left( max( L_{n-1}(i)+L_n(i), L_{n-1}(i)+L_n(i+1) \right)_{i=1..n-1} \) alors le tour est joué

Avec ton exemple on aurait successivement :

     4
   5   2
 12  11  2

-

     4
  17   13

-

     21

Edit : c'est récursivité ou récursif : avec un S

-
Edité par PicoDev 17 décembre 2016 à 18:59:45

Donc faudrait commencer par calculer les sous liste du " bas" ..?

oui.

     4
   5   2
 12  11  2
 
-
 
     4
  17   13
 
-
 
     21

J'ai juste pas compris "l'un au dessous de l'autre" comment 12 peut s'additionner qu'avec  5 et pas avec 2 ..

La ligne 12 11 8 (erreur de transcription, c'est 8 et non 2)  s'obtient à partir des lignes :

 4 5 2
8 3 6 1

12 = max(4+8, 4+3)
11 = max(5+3, 5+6)
8 = max(2+6, 2+1)

def max_trail(pyramid,row=0,col=0):
    if not pyramid:
        return 0
    if len(pyramid)==1:
        return pyramid[0]
    if len(pyramid[0])!=0:
        m=max(pyramid[row][col]+pyramid[row+1][col], pyramid[row+1][col]+pyramid[row+1][col+1])

J'arrive pas a continuer :(((

Il faut penser récursivement et surtout ne pas commencer à coder avant de pouvoir le faire à la main avec un crayon et une feuille de papier.

L'idée est essentiellement de partir d'un triangle, d'enlever la dernière ligne et de remplace l'avant-dernière par une nouvelle → il faut impérativement réduire la taille du problème.

J'ai compris que la Ln ligne est remplace par le max de Ln(0)+Ln-1(0) et Ln(0) + Ln-1(1), et ainsi de suite pour chaque element de Ln

Donc un début de squelette d'algo pourrait ressembler à :

si la pyramide n'a qu'une ligne
  renvoyer la valeur de cette ligne
sinon
  last est la dernière ligne de la pyramide
  upper est le reste de la pyramide
  modifier la dernière ligne de la pyramide
  faire un appel récursif pour résoudre le problème avec upper et renvoyer la valeur

Remarque que :

• tu n'as pas besoin de données comme row et col car la première ligne ne contient forcément qu'un seul élément, la seconde forcément deux, …
• comme tu as présenté les choses, la première ligne est la dernière de ta liste, …, la dernière ligne est la première de ta liste
• avec des slice tout se passera pour le mieux

J'ai bien compris mais j'ai aucune ideee comment l'écrire, du moins comment apres avoir vérifier pour le premier élément de la liste, verifier ensuite le deuxième etc..

C'est pas hyper compliqué

Au départ tu as pyramide :

   4
  5 2
 4 5 2
8 3 6 1

Dans ton code tu la «coupes en deux», d'un côté la ligne last et le reste du dessus de la pyramide :

upper :
   4
  5 2
 4 5 2

last :
8 3 6 1

tu modifies upper :

      4
   5     2
12    11    8

et tu sais que cette pyramide plus petite (enfin ça reste normalement à prouver …) a la même solution que la pyramide d'origine … dont tu recommences avec upper.

La partie "mathématique" je l'ai bien maîtrise C'est le passage en code que je ne visualise pas  

j'ai du mal avec la recurcivite 

grrr … récursivité … d'ailleurs tu pourrais éditer le titre du fil …

Tu as l'algo … le plus dur est de trouver l'algo, ensuite si tu a compris comment ça fonctionne l'implémentation vient d'elle-même.

L'algo est celui que j'ai donné un peu plus haut :

si la pyramide n'a qu'une ligne
  renvoyer la valeur de cette ligne
sinon
  last est la dernière ligne de la pyramide
  upper est le reste de la pyramide
  modifier la dernière ligne de la pyramide
  faire un appel récursif pour résoudre le problème avec upper et renvoyer la valeur

en partant du principe que dans le code la pyramide t'est donnée par une liste de liste :

   4
  5 2
 4 5 2   →  [ [8,3,6,1], [4,5,2], [5,2], [4] ]
8 3 6 1

La première partie (condition d'arrêt) est simple :

def max_trail( pyramid ):
  if len(pyramid) == 1:
    return pyramid[0][0]

La seconde partie = création d'un problème plus petit et appel récursif :

  else:
    last, upper = ...
    tu modifies upper ...
    return max_trail(upper)

def max_trail(pyramid,row=0,col=0):
     if len(pyramid)==1:
         return pyramid[0][0]
     if len(pyramid)>1:
        for rows in pyramid:
            last=max(pyramid[row][col]+pyramid[row+1][col],pyramid[row][col+1]+pyramid[row+1][col])
            pyramid[i+1][i]=last

Je prefere utiliser les variables row et col pour mieux visualise... mais je suis toujours bloque

J'ai desormais la premiere valeur max soit 12 qui a ete ajoute dans la Ln i place, mais comment cotinuerla boucle ..

-
Edité par Ilan00 18 décembre 2016 à 19:22:21

Tu veux pas changer le titre … pourtant ça pique les yeux.

Ton code est faux. Je suppose que tu n'as pas compris comment ça fonctionne …

Si tu pars du triangle :

  1
 4 2
3 5 7

Avec l'algo que je t'ai donné tu obtiens quoi pour last et upper ?

Haha je suis désolé pour la faute, je trouve pas ou changer le titre du topic .. 
Ici

Last= 9,9

Upper = [9,9],[1] 

non,

va pas trop vite.

La première étape c'est simplement last = [3,5,7] et upper = [ [4,2], [1] ]

Ensuite tu fais quoi ?

Mais déjà je bloque a trouver la premiere sous liste de upper = [ [4,2], [1] ] .... 

la suite serait de rappeler la fonction avec comme liste upper et non l'originale

Tu connais les slices ?

oui

c'est quoi pyramide[1:] ? c'est quoi pyramide[0] ?

pyramide[1:] c'est toute les sous liste de la pyramide sauf la premiere, pyramide[0] c'est la premiere sous liste de pyramide

peux-tu exprimer last et upper en fonction de slices de pyramide ?

last c'est pyramide[0]
upper[0] s'obtient en remplacant pyramide[1] par les valeurs max + pyramid[2:]

non

upper est simplement pyramide[1:]

les upper[0][colonne] s'obtiennent en fonction des upper[0][colonne] et last[colonne] … attention aux types des objets que tu manipules (liste, liste de liste, nombre).

Tu pourrai me propose une solution, je maîtrise pas le sujet ...

Entre

PicoDev a écrit:

Donc un début de squelette d'algo pourrait ressembler à :

si la pyramide n'a qu'une ligne
  renvoyer la valeur de cette ligne
sinon
  last est la dernière ligne de la pyramide
  upper est le reste de la pyramide
  modifier la dernière ligne de la pyramide
  faire un appel récursif pour résoudre le problème avec upper et renvoyer la valeur

Remarque que :

• tu n'as pas besoin de données comme row et col car la première ligne ne contient forcément qu'un seul élément, la seconde forcément deux, …
• comme tu as présenté les choses, la première ligne est la dernière de ta liste, …, la dernière ligne est la première de ta liste
• avec des slice tout se passera pour le mieux

et

PicoDev a écrit:

La première partie (condition d'arrêt) est simple :

def max_trail( pyramid ):
  if len(pyramid) == 1:
    return pyramid[0][0]

La seconde partie = création d'un problème plus petit et appel récursif :

  else:
    last, upper = ...
    tu modifies upper ...
    return max_trail(upper)

Tu as tout … ensuite je ne peux que te donner la solution. Essaye encore avant.

J'y arrive pas 😔😔

comment tu fais pour trouver tout les max, j'ai compris qu'il faut utilise les slices, mais fait également une boucle non ?

Oui, bien sûr il faut une boucle car il faut modifier tous les éléments de la première liste de upper avec la formule que je t'ai donné dès mon premier message. C'est clair qu;il faut se creuser la tête et surtout pouvoir le faire à la main avant d'essayer de le coder.