Manier le logarithme

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 5 — Algorithmes dichotomiques

Énoncé

Sans calculatrice, donner le nombre de tours maximum d'une recherche dichotomique pour $n = 100$ et $n = 1 0^{6}$ . Combien de divisions par 2 successives sont nécessaires pour ramener $1 0^{9}$ à 1 ? Si un algorithme dichotomique effectue au plus 13 itérations, quelle est la taille maximale $n$ acceptée ?

Corrigé

Pour $n = 100$ : $2^{6} = 64 \leq 100 < 128 = 2^{7} ⟹ ⌊ lo g_{2} 100 ⌋ = 6$ . L'algorithme réalise au plus $6 + 1 = 7$ tours.
Pour $n = 1 0^{6}$ : $2^{19} < 1 0^{6} < 2^{20} ⟹$ au plus 20 itérations (chaque puissance de 10 de l'exposant, soit un facteur $1 0^{3}$ , correspond à environ 10 divisions par 2).
Pour $1 0^{9} \approx 2^{30}$ , il faut environ 30 divisions par 2.
Au plus 13 tours signifie $⌊ lo g_{2} n ⌋ + 1 \leq 13 ⟹ n < 2^{13} = 8192$ . La taille maximale est $n = 8191$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.