Python débutant

[JohannLiebert]

Bonjour,
Pour mon cours d'informatique, j'ai pour tâche de créer un arbre généalogique. Cependant, je rencontre des difficultés avec une fonction que je suis en train de développer, car elle ne produit pas les résultats attendu. Je souhaite créer une fonction permettant de déterminer le nombre de générations de descendants qu'une personne a, que j'ai nommée 'fct_cache_profondeur'. Mon problème réside dans le fait que la fonction que j'ai programmée ne renvoie pas toujours la profondeur la plus élevée. Le problème se situe dans la partie du code où j'itère à travers la liste des enfants. En effet, cette boucle 'for enfant in liste_enfants' ne prend en compte que le premier enfant, ce qui fait que la fonction suit uniquement la descendance du premier enfant à chaque itération. Par exemple, sur l'arbre généalogique présenté ci-dessous, si je demande la profondeur de Agatha, ma fonction renverra 2, alors que la réponse correcte devrait être 4 (veuillez excuser la qualité médiocre de l'arbre). Merci d'avance pour votre aide. Pour info mapping est un dict qui a pour clé le nom de la personne et pour valeur une liste de ses enfants.

:def fct_cache_profondeur (nom, mapping, cache_profondeur = 0) :
    if nom in mapping.keys():

        liste_enfants = mapping[nom]
        if len(liste_enfants) != 0:

            for enfant in liste_enfants:
                if construire_mapping(enfant) != []:
                    return fct_cache_profondeur(enfant, construire_mapping(enfant), cache_profondeur + 1)
        return cache_profondeur
    else:
        return None

-----

[pm42]

Dans ta boucle des enfants, il ne faut pas faire return mais calculer le max de tous les enfants. Et c'est cette valeur que tu dois renvoyer une fois la boucle finie.

De plus, appeler 2 fois construire_mapping(enfant), une fois dans le test puis dans l'appel à fct_cache_profondeur n'est pas optimal.
Tu l'appelles une fois, tu mets le résultat dans une variable et c'est sur elle que tu fais le if.

Tu peux aussi faire mieux que :

if nom in mapping.keys():
        liste_enfants = mapping[nom]
        if len(liste_enfants) != 0:

            for enfant in liste_enfants:

avec :

liste_enfants = mapping.get(nom)
if liste_enfants:
   for enfant in liste_enfants:

[JohannLiebert]

Dsl mais j'ai pas compris ce que tu veux dire par "max de tous les enfants"

[vgondr98]

Il ne faut pas mettre

return fct_cache_profondeur(enfant, construire_mapping(enfant), cache_profondeur + 1)

mais

fct_cache_profondeur(enfant, construire_mapping(enfant), cache_profondeur + 1)

En effet, le return fait sortir de la boucle immédiatement donc tu n'itères pas sur tout les enfants mais seulement sur le premier.
Il faut aussi ajouter une variable profondeurmax (inité à 0) pour stocker la profondeur maximal atteinte avec une condition qui vérifie si profondeurmax<cache_profondeur .

En gros, ta fonction parcourt d'abord Byron -> Chrales donc profondeurmax = 2 puis ensuite parcourt Barbara -> Conor ->Dimitri -> Eve donc profondeurmax = 4
puis ensuite Barbara -> Conor -> Damien où profondeurmax (4) > cache_profondeur (2) donc profondeurmax reste à 4.

[A voir en vidéo sur Futura]

[JohannLiebert]

J'ai suivi tes instructions (du moins, je pense l'avoir fait), mais cela n'a pas abouti. Je pense que ça coince au niveau le l'initialisation de profondeurmax = 0 car il va à chaque fois être réinitialisé. J'ai essayé une autre approche en créant une liste pour stocker les profondeurs maximales, puis j'ai tenté de retourner la valeur maximale de cette liste. Cependant, cette méthode n'a pas fonctionné non plus, car la liste était réinitialisée à chaque fois. Avec ton approche, j'ai eu 0 pour Agatha et avec mon approche j'ai eu 3 pour Agatha (donc la dernière ligné). Je dois faire en sorte que ma liste ne soit pas vidé mais je n'arrive pas à trouver comment.
Ta méthode :

def fct_cache_profondeur(nom, mapping, cache_profondeur=0):
    if nom in mapping.keys():
        profondeur_max = 0
        liste_enfants = mapping[nom]
        if len(liste_enfants) != 0:

            for enfant in liste_enfants:
                if construire_mapping(enfant) != []:
                    fct_cache_profondeur(enfant, construire_mapping(enfant), cache_profondeur + 1)
                if cache_profondeur > profondeur_max :
                    profondeur_max = cache_profondeur

        return profondeur_max
    else:
        return None

Ce que j'ai tenté :

def fct_cache_profondeur(nom, mapping, cache_profondeur = 0, liste = None):
    if nom in mapping.keys():
        if liste is None :
            liste = []
        liste_enfants = mapping[nom]
        if len(liste_enfants) != 0:

            for enfant in liste_enfants:
                if construire_mapping(enfant) != []:
                    fct_cache_profondeur(enfant, construire_mapping(enfant), cache_profondeur + 1, liste)
                liste.append(cache_profondeur)

        if liste :
            return max(liste)
        else :
            return cache_profondeur
    else:
        return None

[pm42]

Le 1er code aurait une chance de marcher si tu mettais le résultat de fct_cache_profondeur dans profondeur_max
Là tu initialises à 0 et tu n'en fais plus rien après.

Le 2nd code est une variante plus lourde avec la même erreur.

[vgondr98]

De plus il faut mettre profondeur_max en paramètre de fct_cache_profondeur et l'initialisé en dehors de la fonction.

[pm42]

De plus il faut mettre profondeur_max en paramètre de fct_cache_profondeur et l'initialisé en dehors de la fonction.

Ce qui est faux et ne servira à rien, pas plus d'ailleurs que le cache_profondeur actuellement utilisé.

Ce qu'il faut, c'est calculer récursivement. Quand on lui passe un noeud de l'arbre, fct_cache_profondeur doit :
- calculer les profondeurs des arbres dont une racine est un des enfants.
- calculer le maximum de ces profondeurs (ou 0 si pas d'enfants)
- renvoyer cette valeur + 1 : la profondeur de l'arbre à partir de ce noeud est le maximum des profondeur des enfants + ce noeud
- par exemple, si on a un arbre avec un seul noeud, sa profondeur est 1. Si on a un noeud avec des enfants qui sont tous des feuilles (rien en dessous), on va calculer 1 pour chaque enfant, le max sera 1 et on renverra 2. Etc

Comme déjà dit, l'erreur de fond des codes postés et du mauvais conseil donné par vgondr98 est de passer des valeurs aux appels récursifs qui ne servent absolument à rien au lieu de traiter correctement la valeur qu'elle doit retourner.

Il faudrait aussi traiter le cas où on renvoie None ce qui empêcherait ce genre de calcul et n'a pas de sens ici : fct_cache_profondeur doit renvoyer une profondeur, pas "une profondeur ou je ne sais pas".

[vgondr98]

J'ai pas compris ta remarque, j'interprète cache_profondeur comme la profondeur en cours donc au moment de Dana, elle vaudra normalement 3 alors que la réponse attendu est 4.

[pm42]

J'ai pas compris ta remarque, j'interprète cache_profondeur comme la profondeur en cours donc au moment de Dana, elle vaudra normalement 3 alors que la réponse attendu est 4.

On ne peut pas écrire une fonction récursive en ignorant tout retour de l'appel récursif. C'est ce qui est fait dans le code proposé par JohannLiebert et dans ta suggestion.

[vgondr98]

Mais ca tu l'avais déjà dit dans ton message 6, à quoi cela aurait servi de le répéter ?

[pm42]

Mais ca tu l'avais déjà dit dans ton message 6, à quoi cela aurait servi de le répéter ?

Parce que tu n'as clairement pas compris où est le problème et que tu proposes des solutions fausses. La pédagogie est l'art de la répétition.

[vgondr98]

C'est faux.

[JohannLiebert]

Merci beaucoup pm42! J'ai réussi à mettre en place la fonction. J'ai simplement créé la liste en dehors de la fonction et ajouté un +1. Un grand merci également à tous les autres pour avoir consacré du temps à cela.