Exo Formules AB

Identification

Infoforall

9 - Exercices Formules sur les AB


Exerices sur les formules des arbres binaires.

Exercices liés à cette activité Données Exercices sur les Arbres

01° Que pouvez-vous dire des fonctions log2(x) et 2x ?

...CORRECTION...

Ce sont des fonction réciproques.

log2( 2x ) = x

2log2(x) = x

02° Voyons comment retrouver la formule de la hauteur d'un arbre binaire parfait le jour de l'examen.

Dessiner un arbre binaire parfait ayant 7 noeuds..

Donner la formule permettant de calculer la hauteur h d'un arbre parfait en fonction de n ( en convention pR = 1).

...CORRECTION...

Arbre parfait

7 n'est pas une puissance de 2.

Par contre 7+1 = 8 = 23.

Ce 3 correspond bien à la hauteur h de l'arbre parfait si n=7.

On en déduit la formule suivante :

h = log2(n+1) (avec la convention pR = 1)

 

03° En déduire h=f(n) avec pR = 0.

...CORRECTION...

h = log2(n+1) - 1 (avec la convention pR = 0)

 

04° Justifier qu'un arbre de 14 noeuds puisse être parfait, ou pas.

SANS CALCULATRICE

...CORRECTION...

On utilise h = log2(n+1) et on tente de voir si on peut obtenir un entier.

log2(2) = log2(21) = 1

log2(4) = log2(22) = 2

log2(8) = log2(23) = 3

log2(16) = log2(24) = 4

La fonction logarithme est croissante et continue.

On doit calculer h = log2(14+1) = log2(15).

8 < 15 < 16

log2(8) < log2(15) < log2(16)

3 < log2(15) < 4

 

Le log ne peut donc pas fournir un entier et l'arbre n'est donc pas parfait.

05° Utiliser la formule fournie pour encadrer la hauteur d'un arbre de 17 noeuds.

log2(n+1)≤ h ≤ n (formule valable si profondeur 1 pour la racine)

 

...CORRECTION...

L'arbre quelconque a une forme entre filiforme et parfait.

h = n = 17 pour le cas filiforme.

Pour l'autre cas, il faut calculer log2(18) et arrondir au supérieur.

log2(16) = log2(24) = 4

log2(32) = log2(25) = 5

La fonction logarithme étant croissante et continue, on en déduit que h = log2(18) = 4,.... Si on arrondit au supérieur, on obtient 5.

Conclusion :

5 ≤ h ≤ 17 (formule valable si profondeur 1 pour la racine)

 

FIN

Activité publiée le 26 01 2025
Dernière modification : 26 01 2025
Auteur : ows. h.