Reprendre le premier programme du chapitre (celui qui calcule total…

Exercice de TD · niveau 2 · NSI (première), chapitre 3 — Langages et programmation · Constructions élémentaires, traces et terminaison

Énoncé

Reprendre le premier programme du chapitre (celui qui calcule total, message et etapes pour $n = 7$ ). Dérouler à la main la boucle while, en dressant le tableau des valeurs de reste et de etapes après chaque tour. Prédire ensuite la valeur de etapes pour $n = 100$ , puis vérifier sur machine. Enfin, exprimer etapes en fonction du nombre de bits de $n$ .

Corrigé

La trace, pour $n = 7$ . On part de reste = 7 et etapes = 0. Le test $reste > 1$ est évalué avant chaque tour.

tour	test $reste > 1$	reste	etapes
---	---	7	0
1	$7 > 1$ vrai	3	1
2	$3 > 1$ vrai	1	2
---	$1 > 1$ faux : sortie	1	2

La boucle fait donc deux tours et etapes vaut $2$ .

Prédiction pour $n = 100$ . Chaque tour divise par deux : $100 \to 50 \to 25 \to 12 \to 6 \to 3 \to 1$ . Six tours.

Vérification.


def etapes_de(n):
    """Nombre de divisions par 2 pour ramener n >= 1 a 1."""
    reste = n
    etapes = 0
    while reste > 1:
        reste = reste // 2
        etapes = etapes + 1
    return etapes

print(etapes_de(7), etapes_de(100))    # 2 6

Le lien avec le chapitre 1. Diviser par deux, c'est effacer le bit de poids faible. Partir d'un nombre de $k$ bits et arriver à $1$ (un seul bit) demande donc $k - 1$ effacements :


for n in range(1, 100000):
    assert etapes_de(n) == nb_bits(n) - 1

Les $99999$ cas passent. Contrôle : $7 = 11 1_{2}$ a trois bits, et $3 - 1 = 2$ ; $100 = 110010 0_{2}$ en a sept, et $7 - 1 = 6$ .

Piège de la trace : placer la mise à jour de etapes avant celle de reste ne change rien ici, mais écrire le test après le corps — c'est-à-dire une boucle « répéter jusqu'à » — donnerait un tour de plus pour $n = 1$ .

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.