Combien de tours au maximum pour éléments

Application directe du cours · niveau 1 (application) · NSI (première), chapitre 8 — Dichotomie, voisins et gloutons · Dichotomie

Énoncé

Combien de tours au maximum pour $1000$ éléments ? pour un million ? pour un milliard ? Répondre avec bit_length.

Corrigé


assert (1000).bit_length() == 10
assert (10**6).bit_length() == 20
assert (10**9).bit_length() == 30
assert 2 ** 10 == 1024 > 1000       # 10 divisions par deux passent 1000

Dix, vingt, trente. Multiplier la taille par mille n'ajoute que dix tours, parce que $2^{10} = 1024$ dépasse mille : chaque millier coûte dix comparaisons de plus, pas mille.

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.