TD — Séance 3 — Les boucles

Dérouler, compter, corriger, concevoir

TD de la séance 3 d’Algorithmique : répéter une action, compter, accumuler, s’arrêter.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Dérouler à la main les trois boucles du cours, compter leurs tours et leurs tests, repérer et corriger une boucle fautive, puis écrire et vérifier ses propres boucles. Les traces se remplissent comme dans le CM : une ligne par pas, le numéro de la ligne exécutée, l’état des variables après le pas (souligner la valeur qui change), le résultat du test quand la ligne en contient un, et ce qu’écrit Écrire.

Exercice 1 : trace d’une boucle TantQue

Le numéro d’un colis déposé à la gare routière des Baux maraîchers est 4072. L’algorithme suivant lit un entier positif ou nul, compte ses chiffres et calcule leur somme.

Lire n
nb ← 0
s ← 0
TantQue n > 0 Faire
  s ← s + n mod 10
  n ← n div 10
  nb ← nb + 1
FinTantQue
Écrire "chiffres :", nb, "somme :", s
  1. Dérouler l’algorithme pour l’entrée 4072 dans le tableau ci-dessous.
  2. Combien de tours la boucle fait-elle ? Combien de fois la condition de la ligne 4 est-elle testée ? Qu’écrit la ligne 9 ?
  3. Que valent n mod 10 et n div 10 pour \(\texttt{n}=407\) ? Expliquer en une phrase le rôle de chacune des lignes 5 et 6.
  4. Dérouler l’algorithme pour l’entrée 0. Qu’écrit-il ? Ce résultat est-il le nombre de chiffres de 0 ?
  5. Réécrire l’algorithme avec une boucle Répéter … Jusqu’à, de sorte que l’entrée 0 donne un chiffre. Vérifier par une trace l’entrée 0, puis indiquer ce qu’écrit la nouvelle version pour 4072.
Pas Ligne n nb s Test Écrit

Exercice 2 : nombre de tours d’une boucle Pour

  1. Pour chacun des en-têtes suivants, donner les valeurs prises par i dans le corps, le nombre de tours et le nombre de tests de l’en-tête.

    En-tête Valeurs prises par i Tours Tests
    Pour i de 3 à 9 Faire
    Pour i de 5 à 5 Faire
    Pour i de 8 à 2 Faire
    Pour i de 0 à 20 pas 5 Faire
    Pour i de 10 à 1 pas \(-\) 3 Faire
    Pour i de 1 à 10 pas 4 Faire

  2. On considère l’algorithme suivant. Le dérouler pour l’entrée 5 dans le tableau, et donner ce qu’il écrit.

    Lire n
s ← 0
Pour k de 1 à n Faire
  s ← s + 2 × k - 1
FinPour
Écrire "somme :", s
    Pas Ligne n s k Test Écrit

  3. Combien de tours la boucle fait-elle pour l’entrée 0 ? Qu’écrit alors l’algorithme ?

  4. Relever la valeur de s après chacun des tours de la question (b). Quelle valeur l’algorithme écrit-il pour un entier \(n\) quelconque ? Énoncer la propriété de s vraie à chaque test de la ligne 3.

Exercice 3 : saisie contrôlée avec Répéter

Un point de transfert d’argent de Touba ne verse que des montants positifs multiples de 500 F. L’algorithme suivant redemande le montant jusqu’à obtenir une valeur acceptée et compte les saisies.

essais ← 0
Répéter
  Lire m
  essais ← essais + 1
Jusqu'à m > 0 ET m mod 500 = 0
Écrire "montant :", m, "saisies :", essais

  1. Dérouler l’algorithme pour les entrées 1250, 0 et 3000, dans cet ordre.

    Pas Ligne essais m Test Écrit

  2. Combien de tours la boucle fait-elle ? Pour chaque montant refusé, indiquer la partie de la condition de la ligne 5 qui est fausse.

  3. Combien de tours fait la boucle si le premier montant saisi est 500 ? Peut-elle faire zéro tour ?

  4. Réécrire l’algorithme avec une boucle TantQue. Écrire la condition de la boucle TantQue en fonction de celle de la ligne 5, puis vérifier que la nouvelle version écrit la même ligne pour les entrées de la question (a).

Exercice 4 : deux boucles fautives

Partie A. Au départ d’une course de pirogues à Ziguinchor, le starter annonce un compte à rebours de 3 en 3.

i ← 10
TantQue i ≠ 0 Faire
  Écrire i
  i ← i - 3
FinTantQue
Écrire "partez"

  1. Relever la valeur de i, le résultat du test et ce qui est écrit, pour les sept premiers tests de la ligne 2.

    Test i i \(\neq\) 0 Écrit avant le test suivant

  2. L’algorithme s’arrête-t-il ? Justifier à partir des valeurs prises par i.

  3. Corriger la ligne 2 par un seul changement de l’opérateur de comparaison, et donner toutes les lignes écrites par l’algorithme corrigé.

Partie B. L’algorithme suivant doit écrire le nombre de multiples de 3 compris entre 1 et \(n\), bornes incluses.

Lire n
c ← 0
i ← 1
TantQue i < n Faire
  Si i mod 3 = 0 Alors
    c ← c + 1
  FinSi
  i ← i + 1
FinTantQue
Écrire "multiples de 3 :", c

  1. Relever i, c et le résultat du test à chaque exécution de la ligne 4, pour l’entrée 9. Qu’écrit l’algorithme ?

    Test i c i < n

  2. Quel résultat est attendu pour \(n=9\) ? Quel multiple manque, et pourquoi ?

  3. Corriger l’algorithme en modifiant un seul caractère. Vérifier la correction par une trace complète sur le cas limite \(n=3\), où le seul multiple est la borne elle-même.

Exercice 5 : boucles imbriquées

Pour i de 1 à 3 Faire
  Pour j de i à 4 Faire
    Écrire i, j
  FinPour
FinPour

  1. Pour chaque valeur de i, donner les valeurs prises par j, les lignes écrites et le nombre de tests de la ligne 2.

    i Valeurs de j Lignes écrites Tests de la ligne 2

  2. Combien de fois la ligne 3 est-elle exécutée ? Combien de fois l’en-tête de la ligne 1 est-il testé ? Et celui de la ligne 2, au total ?

  3. Même question (nombre d’exécutions de la ligne 3) si la ligne 2 devient Pour j de 1 à 4.

  4. On généralise avec l’algorithme suivant. Donner la valeur écrite pour \(n=1\) et pour \(n=4\), puis pour un entier \(n\geq1\) quelconque. Justifier par une somme.

    Lire n
c ← 0
Pour i de 1 à n Faire
  Pour j de i à n Faire
    c ← c + 1
  FinPour
FinPour
Écrire "tours :", c

Exercice 6 : conception

Fatou tient une boutique de tissus au marché HLM, à Dakar. Chaque soir, elle saisit les montants de ses ventes de la journée.

Partie A. Elle connaît le nombre \(n\geq1\) de ventes avant de saisir les montants.

  1. Écrire un algorithme qui lit \(n\), puis les \(n\) montants, et écrit le total des ventes et le montant de la plus grande vente. Numéroter les lignes ; une instruction par ligne.

    Algorithme :

  2. Tracer l’algorithme pour \(n=4\) et les montants 2500, 1200, 4000 et 800. Les colonnes de variables sont à nommer.

    Pas Ligne Test Écrit

  3. Tracer l’algorithme pour le cas limite \(n=1\) et le montant 1500. Combien de tours fait la boucle ?

    Pas Ligne Test Écrit

Partie B. Un soir, Fatou ne connaît pas le nombre de ventes : elle saisit les montants l’un après l’autre et termine par 0, qui n’est pas une vente.

  1. Écrire un algorithme qui écrit le nombre de ventes et leur total. Justifier le choix de la boucle.

    Algorithme :

  2. Tracer l’algorithme pour les saisies 3000, 500, 0, puis pour le cas limite où la seule saisie est 0.

    Pas Ligne Test Écrit
    Pas Ligne Test Écrit

Pour cette séance

Le cours

Les slides

Retour au sommet