Resumé du logarithme binaire 1. Logarithme binaire : C'est le nombre de chiffres nécessaires pour écrire un nombre en base 2. Exemple : 42 en binaire s'écrit "101010", donc blog(42) = 6. 2. Propriétés : - Propriété 1 : Tout nombre n est compris entre deux puissances de 2. Si 2^k <= n < 2^(k+1), alors blog(n) = k + 1. - Propriété 2 : Si n est une puissance de 2, alors blog(n) = k + 1, où n = 2^k. 3. Exemples : Exemple 1 : Pour n = 727, les puissances de 2 proches sont 512 et 1024. Donc 512 <= 727 < 1024, donc blog(727) = 10. Exemple 2 : Pour n = 64, qui est une puissance de 2, blog(64) = 7. 4. Définition mathématique : Le logarithme binaire se calcule comme : log2(x) = ln(x) / ln(2) Mais pour les entiers, on utilise les propriétés des puissances de 2. Résumé final : - Le logarithme binaire détermine combien de chiffres il faut pour écrire un nombre en binaire. - Il suit des règles simples liées aux puissances de 2. La fonction dlog renvoie le nombre de digit dans l’écriture du nombre en base 10. Elle propose donc une définition du logarithme décimal similaire à celle du logarithme binaire (qui rappelons-le représente le nombre de digit dans l’écriture du nombre en base 2) INTERVALLE : 1) Les entiers n tels que blog(n) = 4 sont les éléments de l’intervalle [ 2pui3 ; 2pui4 [ ; c’est-à-dire les entiers compris entre 8 inclus et 16 exclus QUESTION DIFFICILE : Le père du nœud n a pour étiquette le quotient de la division de n par 2. La hauteur de l’arbre est donc le nombre de division successive par deux que l’on peut faire à partir de n, c’est-à-dire le nombre de digit dans son écriture binaire. On en déduit que la hauteur de l’arbre est bien blog(n)