Questions / réponses

Paramètres importants des arbres binaires, le retour

Paramètres importants des arbres binaires, le retour

por Lila Beltran -
Número de respostas: 3

Bonjour,

J'ai codé ma fonction mais je ne suis pas sûre de la manière dont il fallait coder "la longueur d'une branche la plus longue dont tous les noeuds satisfont p" et "la longueur d'une branche la plus longue dont au moins un noeud satisfait p", je me dis que la raison pour laquelle ma fonction ne marche pas sur moodle vient peut-être de là. Pourriez-vous m'aider s'il vous plait ?

Merci d'avance,

Cordialement,

Lila Beltran

Em resposta a 'Lila Beltran'

Re: Paramètres importants des arbres binaires, le retour

por Philippe Duchon -

Il faut faire attention, la tentation d'écrire des formules trop simples, notamment pour le cinquième paramètre (longueur de la plus longue branche ne contenant que des noeuds satisfaisant p), a tendance à mener à des formules fausses.

La valeur de -1 pour "il n'y en a pas" n'est qu'une convention: idéalement, il faudrait que la valeur soit "moins l'infini". En effet quand on ajoute 1 à -1, on obtient 0; mais si, par exemple, on a un arbre dont la racine est un noeud unaire qui satisfait p, et dont l'unique sous-arbre non vide n'a pas de branche composée uniquement de noeuds satisfaisant p (par exemple, le sous-arbre a une racine qui ne satisfait pas p), le cinquième paramètre doit valoir -1, et pas la valeur 0 qu'on risque d'obtenir en faisant une addition sans tester à part la valeur -1.

Avec une valeur "moins l'infini" qui serait absorbante pour l'addition, cette difficulté ne se poserait pas sorriso

(Je parle d'expérience: ma première version de la fonction était fausse. D'ailleurs la seconde est encore fausse, à cause du dernier paramètre qui pose des problèmes du même type)