SD-HStructures de données et modularité

Recherche séquentielle dans un tableau : indice trouvé ou -1, TDNT et exploration par les deux bouts

Idée directrice

Deuxième exercice de l'épreuve (session principale 2024) : un module de recherche séquentielle est donné tout fait, et l'énoncé fait travailler autour de lui. On demande d'abord le type du tableau, puis la même boucle écrite avec une autre structure itérative, enfin une variante du principe de parcours — ici l'exploration simultanée des deux extrémités vers le centre. La valeur retournée reste la même dans les trois versions : l'indice de la case trouvée, ou -1.

Signature de reconnaissance — l'énoncé se trahit ainsi

« Compléter le tableau ci-dessous par la déclaration du nouveau type correspondant au tableau T » ; « Ecrire, en utilisant la boucle Tant que, l'équivalent de la séquence d'instructions » ; « retourne l'indice de la case contenant le réel a s'il existe dans T ou la valeur -1 dans le cas contraire » ; « on explore, simultanément, les éléments des deux côtés du tableau en se déplaçant vers le centre »

Sujet principal

Exercice — recherche séquentielle, variante de boucle et exploration symétrique

4 questionsCorrigé masqué

Recherche dans un tableau (esprit de l'exercice 2 de la session principale 2024)

On dispose d'un tableau V de n entiers distincts, avec 5 ≤ n ≤ 100. L'indice du premier élément est zéro. La fonction Position ci-dessous retourne l'indice de la case contenant l'entier x s'il figure dans V, et la valeur -1 sinon.

Fonction Position (x : entier ; V : Tab ; n : entier) : entier
DEBUT
  i ← 0
  Tant que (i < n) ET (V[i] ≠ x) Faire
    i ← i + 1
  Fin Tant que
  Si (i < n) Alors Retourner i
  Sinon Retourner -1
  FinSi
FIN

On considère, pour n = 8 : V = [ 17 , 4 , 23 , 8 , 41 , 12 , 5 , 30 ], la première case portant l'indice 0.

Donner la déclaration du nouveau type correspondant au tableau V.
Écrire, en utilisant une structure Répéter … Jusqu'à, l'équivalent de la boucle Tant que de la fonction Position.
Donner le résultat de chacun des appels Position(41, V, 8) et Position(9, V, 8), puis en déduire le rôle exact de la valeur retournée.
On veut transformer ce principe en une exploration symétrique : à la première itération on compare x au premier et au dernier élément, à la deuxième au deuxième et à l'avant-dernier, et ainsi de suite jusqu'à trouver x ou jusqu'à ce qu'il n'y ait plus d'élément à comparer. Écrire l'algorithme de la fonction Position2 (x, V, n) réalisant ce parcours, ainsi que son tableau de déclaration des objets locaux. La saisie de n doit être contrôlée.

Voir la correction commentéeAprès avoir posé votre démarche

1. Le tableau n'est pas un type prédéfini : il faut le déclarer. Tab = tableau de 100 entiers — la taille déclarée est le maximum autorisé par l'énoncé, pas la valeur courante de n.

2. La boucle Tant que teste avant d'entrer, Répéter teste après : il faut donc protéger le premier accès en partant de l'indice -1, et conclure sur le contenu de la case plutôt que sur i < n : lorsque x est absent, la boucle s'arrête avec i = n-1, valeur qui satisfait pourtant i < n.

i ← -1
Répéter
  i ← i + 1
Jusqu'à (i = n-1) OU (V[i] = x)
Si (V[i] = x) Alors Retourner i
Sinon Retourner -1
FinSi

3. Position(41, V, 8) : la boucle s'arrête sur la case d'indice 4, qui contient 41. On retourne 4. Position(9, V, 8) : aucune case ne contient 9, i atteint 8, la condition i < n est fausse. On retourne -1. La valeur retournée n'est donc pas un booléen : c'est l'emplacement de la valeur cherchée, -1 servant de code d'absence parce qu'aucun indice réel ne peut valoir -1.

4. Deux compteurs encadrent la zone encore à explorer et se rapprochent d'un pas à chaque tour.

DEF FN Position2 (x : entier ; V : Tab ; n : entier) : entier
1) g ← 0
   d ← n - 1
   trouve ← -1
2) Tant que (g ≤ d) ET (trouve = -1) Faire
     Si (V[g] = x) Alors trouve ← g
     Sinon Si (V[d] = x) Alors trouve ← d
           Sinon g ← g + 1
                 d ← d - 1
           FinSi
     FinSi
   Fin Tant que
3) Retourner trouve
FIN Position2

TDOL de Position2

Objet g — Type/Nature : entier — Rôle : indice courant du côté gauche
Objet d — Type/Nature : entier — Rôle : indice courant du côté droit
Objet trouve — Type/Nature : entier — Rôle : indice de la case trouvée, -1 tant que rien n'a été trouvé

Le test g ≤ d couvre les deux fins possibles : les compteurs se croisent quand n est pair, et se rejoignent sur la case centrale quand n est impair — cette case est alors comparée deux fois (V[g] puis V[d], avec g = d), ce qui reste correct mais coûte une comparaison de plus ; le contrôle de saisie de n appartient au programme appelant, pas à la fonction, qui reçoit n en paramètre.

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 02

Drill SD-H.1 — deux propositions, une seule équivalente

2 questionsCorrigé masqué

La fonction Compte ci-dessous retourne le nombre de fois qu'un caractère c apparaît dans une chaine ch non vide. Les indices d'une chaîne commencent à zéro.

Fonction Compte (ch : chaine ; c : caractère) : entier
DEBUT
  k ← 0
  Pour i de 0 à Long(ch)-1 Faire
    Si (ch[i] = c) Alors k ← k + 1 FinSi
  Fin Pour
  Retourner k
FIN

On propose deux autres écritures. Une seule est équivalente à Compte.

Proposition A                          Proposition B
Fonction Autre (ch, c) : entier        Fonction Autre (ch, c) : entier
DEBUT                                  DEBUT
  k ← 0                                  k ← 0
  Tant que (ch ≠ "") Faire                Tant que (ch ≠ "") Faire
    Si (ch[0] = c) Alors k ← k+1 FinSi      Si (ch[0] = c) Alors k ← k+1
    ch ← Effacer(ch, 0, 1)                  Sinon ch ← Effacer(ch, 0, 1)
  Fin Tant que                              FinSi
  Retourner k                            Fin Tant que
FIN                                      Retourner k
                                       FIN

Donner le résultat de l'appel Autre("informatique", "i") pour chacune des deux propositions.
En déduire la proposition équivalente à Compte, et dire ce qui cloche dans l'autre.

Voir la correction commentéeAprès avoir posé votre démarche

1. Proposition A : la chaîne est raccourcie à chaque tour quoi qu'il arrive, la boucle parcourt donc les 12 caractères et compte les deux i (positions 0 et 8). On retourne 2.

Proposition B : l'effacement est placé dans la branche Sinon. Dès que ch[0] vaut "i", la chaîne n'est plus raccourcie, la condition ch ≠ "" reste vraie et le même caractère est recompté indéfiniment. Sur "informatique" le premier caractère est déjà un i : la boucle ne s'arrête jamais et aucune valeur n'est retournée.

2. La proposition A est équivalente à Compte : les deux versions examinent chaque caractère une fois et une seule. La proposition B est fautive parce qu'elle fait dépendre l'avancement du parcours du résultat du test, alors que l'avancement doit être inconditionnel.

Entraînement 02 / 02

Drill SD-H.2 — combien de comparaisons dans une exploration symétrique ?

4 questionsCorrigé masqué

Un module explore un tableau T de n entiers distincts en comparant, à chaque itération, la valeur cherchée x avec l'element de gauche puis avec celui de droite, les deux indices se rapprochant du centre. Le module s'arrête dès que x est trouvé, ou lorsqu'il n'y a plus d'élément à comparer.

On travaille sur T = [ 6 , 19 , 3 , 44 , 27 , 8 , 15 ], soit n = 7, la première case portant l'indice 0.

Pour x = 15, indiquer le nombre de comparaisons effectuées et l'indice retourné.
Pour x = 44, indiquer le nombre de comparaisons effectuées et l'indice retourné.
Pour x = 50, indiquer le nombre de comparaisons effectuées et la valeur retournée.
Écrire la séquence de contrôle de saisie de n, sachant que le module n'accepte que 5 ≤ n ≤ 100.

Voir la correction commentéeAprès avoir posé votre démarche

1. x = 15 occupe la dernière case, d'indice 6. Première itération : on compare T[0] = 6 puis T[6] = 15, égalité. Deux comparaisons. On retourne 6.

2. x = 44 occupe la case d'indice 3, exactement au centre du tableau de 7 cases. Itération 1 : T[0] puis T[6]. Itération 2 : T[1] puis T[5]. Itération 3 : T[2] puis T[4]. Itération 4 : les deux compteurs valent 3, on compare T[3], égalité. Sept comparaisons. On retourne 3.

3. x = 50 n'est nulle part. Toutes les cases sont examinées, soit huit comparaisons : trois paires (six comparaisons), puis la case centrale d'indice 3 comparée deux fois, T[g] puis T[d] avec g = d = 3. La valeur retournée est -1.

4. Le contrôle est une boucle à test final, qui redemande tant que la valeur est hors bornes.

Répéter
  Ecrire("Donner le nombre d'éléments : ")
  Lire(n)
Jusqu'à (n dans [5..100])

Méthode / Automatismes

Un tableau passé en paramètre exige un type déclaré avant la fonction : c'est le tableau de déclaration des nouveaux types, jamais le tableau des objets globaux.
Passer de Tant que à Répéter déplace le test : on part d'un indice décalé d'un cran et on inverse la condition.
Une fonction de recherche retourne un indice, pas un booléen ; la valeur -1 code l'absence parce qu'elle n'est l'indice d'aucune case.
Toute saisie chiffrée dans l'énoncé se contrôle par Jusqu'à (n dans [min..max]) : le barème compte ce contrôle.
Pour un parcours à deux compteurs, vérifier à la main le cas n pair et le cas n impair avant de recopier l'algorithme au propre.

Pièges classiques

Écrire Jusqu'à (V[i] = x) sans la seconde condition d'arrêt : quand x est absent, l'algorithme sort du tableau. Autre erreur classique : arrêter l'exploration symétrique sur g < d, ce qui laisse la case centrale d'un tableau de taille impaire jamais comparée. Enfin, déclarer le type du tableau dans le tableau des objets globaux au lieu du tableau des nouveaux types coûte des points même si l'algorithme est juste.