Python débutant
Répondre à la discussion
Affichage des résultats 1 à 14 sur 14

Python débutant



  1. #1
    JohannLiebert

    Python débutant


    ------

    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.

    Code:
    :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

    -----
    Images attachées Images attachées  
    Dernière modification par JohannLiebert ; 06/11/2023 à 20h20.

  2. #2
    pm42

    Re : Python débutant

    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 :
    Code:
    if nom in mapping.keys():
            liste_enfants = mapping[nom]
            if len(liste_enfants) != 0:
    
                for enfant in liste_enfants:
    avec :
    Code:
    liste_enfants = mapping.get(nom)
    if liste_enfants:
       for enfant in liste_enfants:

  3. #3
    JohannLiebert

    Re : Python débutant

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

  4. #4
    vgondr98

    Re : Python débutant

    Il ne faut pas mettre
    Code:
    return fct_cache_profondeur(enfant, construire_mapping(enfant), cache_profondeur + 1)
    mais
    Code:
    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.

  5. A voir en vidéo sur Futura
  6. #5
    JohannLiebert

    Re : Python débutant

    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 :
    Code:
    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é :
    Code:
    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

  7. #6
    pm42

    Re : Python débutant

    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.

  8. #7
    vgondr98

    Re : Python débutant

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

  9. #8
    pm42

    Re : Python débutant

    Citation Envoyé par vgondr98 Voir le message
    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".

  10. #9
    vgondr98

    Re : Python débutant

    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.

  11. #10
    pm42

    Re : Python débutant

    Citation Envoyé par vgondr98 Voir le message
    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.

  12. #11
    vgondr98

    Re : Python débutant

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

  13. #12
    pm42

    Re : Python débutant

    Citation Envoyé par vgondr98 Voir le message
    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.

  14. #13
    vgondr98

    Re : Python débutant

    C'est faux.

  15. #14
    JohannLiebert

    Re : Python débutant

    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.

Discussions similaires

  1. question en python (débutant)
    Par JohannLiebert dans le forum Programmation et langages, Algorithmique
    Réponses: 5
    Dernier message: 30/10/2023, 19h48
  2. Débutant en Python: la boucle For
    Par Jon83 dans le forum Programmation et langages, Algorithmique
    Réponses: 3
    Dernier message: 13/09/2022, 16h16
  3. debutant sur Python
    Par invite97b2fcf1 dans le forum Programmation et langages, Algorithmique
    Réponses: 2
    Dernier message: 30/12/2016, 11h35
  4. Python (débutant)
    Par invitee0960580 dans le forum Programmation et langages, Algorithmique
    Réponses: 2
    Dernier message: 06/12/2012, 14h28
  5. Python débutant
    Par invitee0960580 dans le forum Programmation et langages, Algorithmique
    Réponses: 3
    Dernier message: 20/11/2012, 14h19