TD — Séance 4 — Les tableaux

Parcourir, chercher, corriger, concevoir

TD de la séance 4 d’Algorithmique : ranger, parcourir, chercher, transformer.
Auteur

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

ImportantObjectif

Désigner une case par un indice calculé, dérouler à la main des parcours et des recherches dans un tableau, repérer et corriger un indice hors bornes ou une case écrasée trop tôt, puis écrire et vérifier ses propres algorithmes à tableaux. 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 et des cases après le pas (souligner la valeur qui change), le résultat du test, et ce qu’écrit Écrire ; un arrêt sur erreur s’écrit « arrêt » avec sa cause.

Exercice 1 : deux parcours successifs

Une boulangerie de Saint-Louis note le nombre de baguettes vendues avant 8 heures pendant cinq jours. L’algorithme suivant calcule la moyenne, puis compte les jours qui la dépassent.

n ← 5
V : tableau[1..n] d'entiers
V ← [40, 25, 60, 35, 40]
s ← 0
Pour i de 1 à n Faire
  s ← s + V[i]
FinPour
moy ← s / n
c ← 0
Pour i de 1 à n Faire
  Si V[i] > moy Alors
    c ← c + 1
  FinSi
FinPour
Écrire moy, c

  1. Relever, pour chaque tour de la première boucle, V[i] et la valeur de s après le tour.

    \(i\) V[i] s après le tour
    1
    2
    3
    4
    5

  2. Quelle valeur reçoit moy à la ligne 8 ? Relever ensuite, pour chaque tour de la seconde boucle, V[i], le résultat du test de la ligne 11 et la valeur de c après le tour.

    \(i\) V[i] V[i] > moy c après le tour
    1
    2
    3
    4
    5

  3. Qu’écrit la ligne 15 ?

  4. Qu’écrit l’algorithme si la ligne 11 devient Si V[i] \(\geq\) moy Alors ?

  5. Combien de fois chaque case de V est-elle lue pendant l’exécution ? Pourquoi la moyenne ne peut-elle pas être comparée aux cases dans la première boucle ?

Exercice 2 : indices et cases

  1. Après les instructions \(\texttt{n}\leftarrow5\), T : tableau[1..n] déntiers, T \(\leftarrow\) [5, 3, 8, 1, 6] et \(\texttt{i}\leftarrow2\), donner la valeur de chacune des expressions suivantes, ou l’indice hors bornes qu’elle demande.

    Expression Valeur, ou indice hors bornes
    T[i]
    T[i + 3]
    T[n - i]
    T[n - i + 1]
    T[T[4]]
    T[T[2] + 3]
    T[i - 2]
    T[n div 2]
    T[i] + 1
    T[i + 1]

  2. On considère l’algorithme suivant. Donner le contenu des quatre cases de U après chaque affectation d’une case (lignes 3, 5 et 6).

    U : tableau[1..4] d'entiers
Pour k de 1 à 4 Faire
  U[k] ← k × k + 1
FinPour
U[2] ← U[4] - U[1]
U[U[1] + 1] ← 0
    Ligne exécutée U[1] U[2] U[3] U[4]

  3. Que se passe-t-il si la ligne 2 devient Pour k de 0 à 4 Faire ? À quel pas l’exécution s’arrête-t-elle ?

Exercice 3 : recherche avec arrêt

Au centre d’examen de Thiès, le tableau D contient les numéros de table des candidats d’une salle, dans l’ordre des rangées. Un même numéro peut figurer deux fois par erreur de saisie.

n ← 6
D : tableau[1..n] d'entiers
D ← [214, 108, 375, 108, 452, 296]
Lire x
pos ← 0
i ← 1
TantQue i ≤ n ET pos = 0 Faire
  Si D[i] = x Alors
    pos ← i
  FinSi
  i ← i + 1
FinTantQue
Écrire "case :", pos

  1. Pour l’entrée 108, relever \(i\), D[i], pos et le résultat du test à chaque exécution de la ligne 7.

    Test i D[i] pos Test de la ligne 7
    1
    2
    3
    4
    5

  2. Pour chacune des entrées 108, 296 et 500, donner le nombre de comparaisons faites par la ligne 8 et ce qu’écrit la ligne 13.

    x Comparaisons (ligne 8) Écrit
    108
    296
    500

  3. La ligne 7 devient TantQue \(i\leq n\) Faire. Qu’écrit l’algorithme pour l’entrée 108 ? Combien de comparaisons fait-il ? Quelle position rend-il, en général ?

  4. Modifier l’algorithme pour qu’il rende la dernière position de \(x\), en gardant l’arrêt dès que \(x\) est trouvé. Tracer la nouvelle version pour l’entrée 108 et compter ses comparaisons.

Exercice 4 : deux décalages fautifs

Au guichet de la poste de Kaolack, le tableau F contient les numéros des tickets en attente, dans l’ordre d’arrivée.

Partie A. Quand le premier client est servi, chacun avance d’une place et la dernière place se libère (0).

n ← 5
F : tableau[1..n] d'entiers
F ← [17, 23, 31, 42, 56]
Pour i de 1 à n Faire
  F[i] ← F[i + 1]
FinPour
F[n] ← 0

  1. Donner le contenu de F après chaque tour. Que se passe-t-il au tour 5 ?

    Tour \(i\) F[1] F[2] F[3] F[4] F[5]
    1
    2
    3
    4
    5

  2. Corriger l’algorithme par un seul changement, puis donner le contenu final de F.

Partie B. Un client prioritaire, ticket 9, doit être placé en tête ; chacun recule d’une place.

n ← 5
F : tableau[1..n] d'entiers
F ← [17, 23, 31, 42, 56]
Pour i de 2 à n Faire
  F[i] ← F[i - 1]
FinPour
F[1] ← 9

  1. Donner le contenu de F après chaque tour, puis à la fin. Quels numéros ont disparu ?

    Tour \(i\) F[1] F[2] F[3] F[4] F[5]
    2
    3
    4
    5

  2. Corriger la ligne 4 seule. Donner le contenu final. Quel numéro est perdu, et pourquoi ne peut-il pas en être autrement avec un tableau de 5 cases ?

Exercice 5 : conception

Cheikh relève chaque jour, à Matam, la température maximale.

Partie A. Écrire un algorithme qui lit \(n\) (\(n\geq2\)), puis \(n\) températures rangées dans un tableau, et écrit la plus forte hausse d’un jour au suivant (différence entre la température d’un jour et celle de la veille, éventuellement négative) et le jour où elle se termine. Numéroter les lignes ; une instruction par ligne.

Algorithme :

  1. Tracer l’algorithme pour \(n=5\) et les températures 30, 34, 33, 39, 37. Les colonnes de variables et de cases sont à nommer.

    Pas Ligne Test Écrit

  2. Tracer l’algorithme pour le cas limite \(n=2\) et les températures 35 et 32. Combien de tours fait la boucle de recherche de la hausse ?

    Pas Ligne Test Écrit

Partie B. Le tableau T de \(n\) cases est déjà rempli. Écrire un algorithme qui écrit 0 si T est rangé par ordre croissant (chaque case inférieure ou égale à la suivante), et sinon le plus petit indice \(i\) tel que T[i] \(>\) T[i + 1]. La boucle doit s’arrêter dès qu’un tel indice est trouvé. Justifier le choix de la boucle et de sa condition.

Algorithme :

  1. Tracer l’algorithme pour T \(\leftarrow\) [3, 5, 4, 8], puis pour le cas limite d’un tableau d’une case, T \(\leftarrow\) [7].

    Pas Ligne Test Écrit
    Pas Ligne Test Écrit

Exercice 6 : tableau des effectifs

Un sondage de quartier, aux Parcelles Assainies, demande à huit habitants de noter un service de 1 à 5. Le tableau R contient les réponses ; l’algorithme compte, dans E, le nombre de réponses de chaque valeur.

n ← 8
R : tableau[1..n] d'entiers
R ← [4, 5, 3, 4, 2, 4, 5, 1]
E : tableau[1..5] d'entiers
Pour v de 1 à 5 Faire
  E[v] ← 0
FinPour
Pour k de 1 à n Faire
  E[R[k]] ← E[R[k]] + 1
FinPour
Pour v de 1 à 5 Faire
  Écrire v, E[v]
FinPour

  1. Donner, pour chaque tour de la boucle des lignes 8 à 10, R[k] et le contenu de E après le tour.

    \(k\) R[k] E[1] E[2] E[3] E[4] E[5]
    1
    2
    3
    4
    5
    6
    7
    8

  2. Qu’écrit l’algorithme ? Pourquoi la somme des cases de E vaut-elle \(n\) ?

  3. On supprime les lignes 5 à 7. À quel tour et sur quelle case l’exécution s’arrête-t-elle ? Pourquoi ?

  4. On remet les lignes 5 à 7, et une réponse 6 est saisie à la place de la sixième réponse. Que se passe-t-il ? Proposer une protection qui ignore les réponses hors de 1 à 5.

Pour cette séance

Le cours

Les slides

Retour au sommet