par sos-math(21) » ven. 11 mars 2022 11:14
Bonjour,
Pour les réponses à la question 2, il faut que tu t'appuies sur les schémas fournis : un arbre binaire filaire qui va avoir un nombre de feuilles et un nombre de nœuds minimal , et un arbre binaire complet qui va avoir un nombre de feuilles et un nombre de nœuds maximal. Je ne vois pas comment justifier autrement sans rentrer dans les calculs et démarches demandées par la suite.
Pour la question suivante, un arbre binaire filaire étant composé de nœuds ayant chacun exactement un fils, l'avant-dernier nœud aura exactement un fils qui sera donc le seul nœud à ne pas avoir d'enfant, donc ce sera une feuille. Il y a donc une feuille.
Pour la taille, c'est un peu pareil : chaque nœud ayant exactement un fils, il y a donc un nœud par génération, soit h nœud(s) auxquels on rajoute la racine donc \(T=h+1\).
Pour la question 5, tu as un arbre complet donc chaque nœud d'un niveau \(n\) a exactement 2 fils : ainsi le nombre de noeuds au niveau \(n+1\) est donc le double de celui au niveau \(n\), donc \u_{n+1}=2\times u_n\). Tu reconnais la relation de récurrence caractérisant une suite géométrique.
Avec \(u_0=1\), tu obtiens la formule explicite \(u_n=2^n\).
Donc le nombre total de feuilles d'un arbre de hauteur \(h\) est égal au nombre de nœuds du dernier niveau, c'est-à-dire celui de rang \(h\) donc cela fait ... feuilles.
\(S\) est la taille de l'arbre de hauteur \(h\), donc c'est la somme des termes de la suite \((u_n\) du rang 0 au rang \(h\).
On doit donc calculer \(\sum_{k=0}^{h} 2^k= 2^0+2^1+\ldots+2^h\). Dans ton cours, tu as du voir une formule donnant la somme des termes d'une suite de puissances de \(q\), avec \(q>1\) : \(\sum_{k=0}^{h} q^n= q^0+q^1+\ldots+q^n= \dfrac{1-q^n}{1-q}\).
Je te laisse appliquer cette formule dans ta situation.
Avec les résultats trouvés tu peux déduire les encadrements obtenus à partir des cas extrêmes de l'arbre binaire filaire et de l'arbre binaire complet.
il te reste ensuite à faire des essais pour trouver à partir de quelle hauteur \(h\) la valeur \(S\) dépasse 130.
Bons calculs
Bonjour,
Pour les réponses à la question 2, il faut que tu t'appuies sur les schémas fournis : un arbre binaire filaire qui va avoir un nombre de feuilles et un nombre de nœuds minimal , et un arbre binaire complet qui va avoir un nombre de feuilles et un nombre de nœuds maximal. Je ne vois pas comment justifier autrement sans rentrer dans les calculs et démarches demandées par la suite.
Pour la question suivante, un arbre binaire filaire étant composé de nœuds ayant chacun exactement un fils, l'avant-dernier nœud aura exactement un fils qui sera donc le seul nœud à ne pas avoir d'enfant, donc ce sera une feuille. Il y a donc une feuille.
Pour la taille, c'est un peu pareil : chaque nœud ayant exactement un fils, il y a donc un nœud par génération, soit h nœud(s) auxquels on rajoute la racine donc \(T=h+1\).
Pour la question 5, tu as un arbre complet donc chaque nœud d'un niveau \(n\) a exactement 2 fils : ainsi le nombre de noeuds au niveau \(n+1\) est donc le double de celui au niveau \(n\), donc \u_{n+1}=2\times u_n\). Tu reconnais la relation de récurrence caractérisant une suite géométrique.
Avec \(u_0=1\), tu obtiens la formule explicite \(u_n=2^n\).
Donc le nombre total de feuilles d'un arbre de hauteur \(h\) est égal au nombre de nœuds du dernier niveau, c'est-à-dire celui de rang \(h\) donc cela fait ... feuilles.
\(S\) est la taille de l'arbre de hauteur \(h\), donc c'est la somme des termes de la suite \((u_n\) du rang 0 au rang \(h\).
On doit donc calculer \(\sum_{k=0}^{h} 2^k= 2^0+2^1+\ldots+2^h\). Dans ton cours, tu as du voir une formule donnant la somme des termes d'une suite de puissances de \(q\), avec \(q>1\) : \(\sum_{k=0}^{h} q^n= q^0+q^1+\ldots+q^n= \dfrac{1-q^n}{1-q}\).
Je te laisse appliquer cette formule dans ta situation.
Avec les résultats trouvés tu peux déduire les encadrements obtenus à partir des cas extrêmes de l'arbre binaire filaire et de l'arbre binaire complet.
il te reste ensuite à faire des essais pour trouver à partir de quelle hauteur \(h\) la valeur \(S\) dépasse 130.
Bons calculs