cned devoir 3

« DEVOIR 3-MATHS 1- EXERCICE 1 1) On nous représente un arbre binaire dont on demande de donner la taille T1, la hauteur H1 et le nombre de feuilles F1: -Cet arbre binaire est de hauteur H=3, car à partir de la racine de Martine, on a 3 générations.

Ensuite le nombre de feuilles de cet arbre est de F=2, car il y a 2 sommets: Oscar et Tartuffe qui n’ont pas d’enfant.

Enfin, la taille de cet arbre est de T=5, la taille est définie par le nombre de personnes dans l’arbre binaire. 2) Nous avons un arbre binaire de hauteur 3 a)Un arbre binaire filaire aura plusieurs feuilles et un nombre minimum de nœuds, chacun avec un et un seul enfant (donc un nœud par hauteur). On définit pour commencer le nombre de feuilles minimales d’un arbre filaire où chaque nœud a un enfant: Par conséquent, Fminimum=1. Cependant, un arbre binaire complet aura plusieurs feuilles et un nombre maximum de nœuds, chaque nœud ayant exactement 2 enfants. On définit pour commencer la taille maximale d’un arbre filaire complet où chaque nœud a 2 enfants par noeud: Fmaximale=2 nœuds pour h=1 à partir de la racine, 4 nœuds pour h=2 et 8 nœuds,h=3. Par conséquent, Fmaximale=8. Ainsi, un arbre binaire de hauteur 3 peut avoir de 1 à 8 feuilles, Soit : 1 ≤ F ≤ 8.

on peut également écrire cet encadrement comme cela: 4≤F≤8 b) Un arbre binaire filaire est un arbre où chaque nœud a un enfant. On définit pour commencer la taille minimale d’un arbre filaire où chaque nœud a un enfant: Donc, Tminimum=racine+3 hauteur du nœud=4. Ensuite, nous savons donc qu'un arbre binaire complet a 2 enfants par nœud. On définit à présent la taille maximale d’un arbre binaire complet a 2 enfants par nœud: Donc, Tmaximal=racine + 2 nœuds de hauteur 1 + 4 nœuds de h=2 + 8 nœuds de h=3 = 15. Ainsi un arbre binaire de hauteur 3 peut avoir une taille comprise entre 4 et 15, Soit : 4 ≤ T ≤ 15, on peut également écrire cet encadrement comme cela: 7 ≤ T ≤ 15 3) D’après la propriété du cours, de la somme des n premiers termes : Soit un réel q ≠ de 1: ∑^n q^k = 1 + q + q^2+ … + q^n = 1 - q^n+1⁄1-q k=0 On applique cette formule: ∑^8 2^i = 1 + 2 + 2^2+ 2^3+ … + 2^8 = 1 - 2^8+1⁄1-2 = 511 i=0 Ainsi la solution de la somme des termes est 511. 4) On s’intéresse pour commencer à un arbre binaire filaire de hauteur h quelconque (h est un entier strictement positif).

Nous avons donc un arbre dans lequel chaque nœud a un unique fils. a) Un arbre filaire de hauteur h est composé d’une branche qui part de sa racine et contient h nœuds.

Cependant, le dernier nœud a un unique fils. le nombre de feuilles est le nombre de noeud sans enfant donc F=1 Ainsi un arbre binaire filaire de hauteur h quelconque a une seule feuille, donc h>0 b) La taille d’un arbre filaire est le nombre total de nœuds qu’il compose. D'après La réponse précédente, un arbre binaire de hauteur h quelconque, ce sera chaque nœud sauf la feuille qui a un fils.

Ainsi, il y a 1 chemin à parcourir de la racine jusqu’à la feuille.

donc, il y.... »