Bonjour,
Je rencontre quelques soucis avec mon devoir de mathématiques et notament pour l'exercice 1.
Tout d'abord, pour la question 2 j'ai trouvé les résultats mais je ne sais pas comment je peux les justifier. En effet une réponse sans justification ne vaut rien. J'ai mis: 2)a. L’arbre binaire de hauteur 3 peut avoir entre 1 et 8 feuilles alors : 1 ≤ F ≤ 8 car …. / b. L’arbre binaire de hauteur 3 peut avoir une taille comprise entre 4 et 15 alors : 4 ≤ T ≤ 15 car … .
Ensuite c'est exactement le même problème avec la question 4. J'ai mis: 4) Une arbre binaire filaire de hauteur h est un arbre pour lequel chaque nœud a un et un seul fils (h>0). a.Le nombre de feuilles est le nombre de nœud sans enfant donc F=1 car ... / b. La taille d’un arbre de hauteur h est égale au nombre de nœuds T=h+1 car…
Puis, les deux dernières questions, la 6) et la 7) sont des enigmes pour moi. Je ne sais pas comment procéder.
Pouvez-vous m'aider ?
Merci
Maëlle
Les suites
-
Maëlle
Les suites
- Fichiers joints
-
_0-MA16-DV-WB-S05-N03-B-21.pdf- (585.89 Kio) Téléchargé 114 fois
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: Les suites
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
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
-
Maëlle
Re: Les suites
Merci de votre réponse si rapide.
Pour la question 2, est ce que je peux dire:
2) a. Un arbre binaire filaire va avoir un nombre de feuilles et un nombre de nœuds minimal pour lequel chaque noeud a un seul et unique fils (un seul noeud par hauteur). Ainsi, Fminimum= 1. Mais, un arbre binaire complet va quand à lui avoir un nombre de feuilles et un nombre de nœuds maximal pour lequel chaque noeud a exactement 2 fils (2 noeuds pour h=1 à partir de la racine, 4 noeuds pour h=2 et 8 noeuds pour h=3). Ainsi, Fmaximal= 8. Donc, l’arbre binaire de hauteur 3 peut avoir entre 1 et 8 feuilles soit : 1 ≤ F ≤ 8.
b. On a dit qu'un arbre binaire filaire est un arbre pour lequel chaque noeud a un seul fils. Donc, Tminimum= la racine+ 3 hauteur d'un noeud = 4. De plus, on sait donc que un arbre binaire complet est où chaque noeud a 2 fils. Donc, Tmaximal= la racine+ 2 noeud pour la hauteur 1+ 4 noeud pour h=2 + 8 noeuds pour h=3 = 15. Donc l’arbre binaire de hauteur 3 peut avoir une taille comprise entre 4 et 15 soit : 4 ≤ T ≤ 15
Pour la question 5 j'avais trouver:
Comme q=2, alors S= ∑_(n=0)^n▒〖2^h= u_0×(1-q^(n+1))/(1-q)=(1-2^(n+1))/(-1)〗
je n'ai pas remplacer n par une valeur car je n'en trouver pas, il y en a une ?
Pour la question 2, est ce que je peux dire:
2) a. Un arbre binaire filaire va avoir un nombre de feuilles et un nombre de nœuds minimal pour lequel chaque noeud a un seul et unique fils (un seul noeud par hauteur). Ainsi, Fminimum= 1. Mais, un arbre binaire complet va quand à lui avoir un nombre de feuilles et un nombre de nœuds maximal pour lequel chaque noeud a exactement 2 fils (2 noeuds pour h=1 à partir de la racine, 4 noeuds pour h=2 et 8 noeuds pour h=3). Ainsi, Fmaximal= 8. Donc, l’arbre binaire de hauteur 3 peut avoir entre 1 et 8 feuilles soit : 1 ≤ F ≤ 8.
b. On a dit qu'un arbre binaire filaire est un arbre pour lequel chaque noeud a un seul fils. Donc, Tminimum= la racine+ 3 hauteur d'un noeud = 4. De plus, on sait donc que un arbre binaire complet est où chaque noeud a 2 fils. Donc, Tmaximal= la racine+ 2 noeud pour la hauteur 1+ 4 noeud pour h=2 + 8 noeuds pour h=3 = 15. Donc l’arbre binaire de hauteur 3 peut avoir une taille comprise entre 4 et 15 soit : 4 ≤ T ≤ 15
Pour la question 5 j'avais trouver:
Comme q=2, alors S= ∑_(n=0)^n▒〖2^h= u_0×(1-q^(n+1))/(1-q)=(1-2^(n+1))/(-1)〗
je n'ai pas remplacer n par une valeur car je n'en trouver pas, il y en a une ?
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: Les suites
Bonjour,
je pense que ton argumentation est suffisante.
Pour la somme, tu peux simplifier l'écriture finale \(\dfrac{1-2^{n+1}}{1-2}=\dfrac{1-2^{n+1}}{-1}=2^{n+1}-1\).
Ensuite, si ton arbre a pour hauteur \(h\) , alors il a \(h\) niveaux donc \(T=2^{h+1}-1\) : c'est une formule générale donc il n'y a pas à remplacer \(h\) par une valeur.
Au final, tu dois obtenir les encadrements suivants pour un arbre binaire de hauteur \(h\) :
\(1\leqslant F\leqslant 2^h\) et \(h+1\leqslant T\leqslant 2^{h+1}-1\).
Si tu veux ensuite, retrouver la hauteur minimale qui permet d'atteindre la taille \(T=130\), alors tu sais que tu dois prendre un arbre binaire complet (pour une hauteur donnée, c'est lui qui a le plus grand nombre de nœuds, donc pour une taille donnée, ce sera lui qui aura la hauteur minimal car il utilise le maximum de nœuds à chaque niveau), donc il faut que tu trouves à partir de quelle valeur de \(h\), tu as \(2^{h+1}-1\geqslant 130\).
Bonne continuation
je pense que ton argumentation est suffisante.
Pour la somme, tu peux simplifier l'écriture finale \(\dfrac{1-2^{n+1}}{1-2}=\dfrac{1-2^{n+1}}{-1}=2^{n+1}-1\).
Ensuite, si ton arbre a pour hauteur \(h\) , alors il a \(h\) niveaux donc \(T=2^{h+1}-1\) : c'est une formule générale donc il n'y a pas à remplacer \(h\) par une valeur.
Au final, tu dois obtenir les encadrements suivants pour un arbre binaire de hauteur \(h\) :
\(1\leqslant F\leqslant 2^h\) et \(h+1\leqslant T\leqslant 2^{h+1}-1\).
Si tu veux ensuite, retrouver la hauteur minimale qui permet d'atteindre la taille \(T=130\), alors tu sais que tu dois prendre un arbre binaire complet (pour une hauteur donnée, c'est lui qui a le plus grand nombre de nœuds, donc pour une taille donnée, ce sera lui qui aura la hauteur minimal car il utilise le maximum de nœuds à chaque niveau), donc il faut que tu trouves à partir de quelle valeur de \(h\), tu as \(2^{h+1}-1\geqslant 130\).
Bonne continuation