SD-IStructures de données et modularité

Problème modulaire : deux tableaux parallèles, cumul pondéré et affichage de tous les ex æquo

Idée directrice

Le problème de 12 à 13 points (session principale 2024, même famille qu'en 2018 et 2019) : deux tableaux de même longueur liés par l'indice, l'un portant des libellés, l'autre un cumul chiffré. Trois décisions le caractérisent : contrôler chaque saisie, mettre à jour le second tableau à travers l'indice rendu par un module de recherche, puis afficher tous les ex æquo et non le premier trouvé. L'attendu de la première question n'est pas du code mais l'analyse modulaire avec ses tableaux de déclaration.

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

« Ecrire un algorithme du programme principal, solution à ce problème, en le décomposant en modules » ; « TS[i] est le total des points cumulés du joueur ayant pour nom TJ[i] » ; « d'afficher le score MVP de la saison, ainsi que le nom de chaque joueur ayant ce score » ; « composés uniquement de lettres alphabétiques et d'espaces »

Sujet principal

Problème — élection du projet primé par un jury

5 questionsCorrigé masqué

Problème (13 points) — dans l'esprit du problème de la session principale 2024

En fin d'année, un jury d'enseignants élit le meilleur projet parmi ceux soutenus par les élèves. Chaque enseignant classe trois projets par ordre de préférence : le premier choix rapporte 5 points, le deuxième 3 points, le troisième 1 point. Le projet totalisant le plus grand nombre de points est primé ; en cas d'égalité, tous les projets concernés le sont.

On veut écrire une solution algorithmique permettant :

de remplir un tableau TP par n titres de projets distincts, chaque titre étant une chaine de caracteres formée uniquement de lettres et d'espaces, avec 5 ≤ n ≤ 40 ;
de déterminer, dans un tableau TC, le cumul des points de chaque projet d'après les votes des m enseignants, avec 3 ≤ m ≤ 60, sachant que chaque enseignant doit citer trois titres distincts et présents dans TP, et que TC[i] est le cumul du projet dont le titre est TP[i] ;
d'afficher le score maximal, puis le titre de chaque projet ayant atteint ce score, au format : Score maximal : valeur puis Projet(s) primé(s) : titre1, titre2, ....

Exemple. Pour n = 5 et TP = ["Serre connectee", "Bras robotise", "Bus scolaire", "Tri des dechets", "Ruche numerique"], TC part de [0,0,0,0,0]. Après le vote d'un premier enseignant classant Bras robotise, Serre connectee, Ruche numerique, on obtient TC = [3,5,0,0,1]. Après un deuxième vote classant Serre connectee, Bras robotise, Bus scolaire, on obtient TC = [8,8,1,0,1]. L'affichage attendu est alors :

Score maximal : 8
Projet(s) prime(s) : Serre connectee, Bras robotise

Travail demandé :

Analyser le problème en le décomposant en modules, et donner les tableaux de déclaration des nouveaux types et des objets globaux.
Écrire l'algorithme du module de dépouillement des votes et celui du module d'affichage, avec leurs objets locaux.

N.B. On utilisera sans les développer les deux modules suivants : Alpha(ch), fonction booléenne vraie si la chaîne ch ne contient que des lettres et des espaces ; Rang(ch, T, k), fonction retournant l'indice de la case de T contenant ch parmi ses k premières cases, ou -1 si ch n'y figure pas.

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

1. Analyse du programme principal

Nom : Palmares
  Resultat = PROC Afficher(TP, TC, n)
  TC = PROC Depouiller(TP, TC, n, m)
  (TP, n) = PROC Remplir(TP, n)
Fin Palmares

La décomposition suit les trois demandes de l'énoncé : un module de saisie contrôlée, un module de dépouillement qui alimente TC, un module d'affichage qui ne dépend que des deux tableaux remplis. Aucun module ne recalcule ce qu'un autre a déjà produit.

TDNT

TabCh = Tableau [1..40] de chaine de caractères
TabEnt = Tableau [1..40] d'entiers

TDOG

TP — Type/Nature : TabCh — Rôle : contenant les titres des projets
TC — Type/Nature : TabEnt — Rôle : contenant le cumul des points de chaque projet
n — Type/Nature : entier — Rôle : le nombre de projets
m — Type/Nature : entier — Rôle : le nombre d'enseignants votants
Remplir — Type/Nature : procédure — Rôle : saisir n et les titres, chaque titre étant contrôlé et non déjà présent
Depouiller — Type/Nature : procédure — Rôle : lire les votes et cumuler les points dans TC
Afficher — Type/Nature : procédure — Rôle : afficher le score maximal puis tous les projets qui l'atteignent

2. Algorithme du module de dépouillement

DEF PROC Depouiller (TP : TabCh ; var TC : TabEnt ; n : entier ; var m : entier)
0) Pour i de 1 à n faire
     TC[i] ← 0
   FinPour
1) Répéter
     Ecrire("Nombre d'enseignants : ") ; Lire(m)
   Jusqu'à (m dans [3..60])
2) Pour j de 1 à m faire
     C[1] ← 0 ; C[2] ← 0
     Pour r de 1 à 3 faire
       Répéter
         Ecrire("Choix n° ", r, " de l'enseignant ", j, " : ") ; Lire(t)
         p ← Rang(t, TP, n)
       Jusqu'à (p ≠ -1) ET (p ≠ C[1]) ET (p ≠ C[2])
       C[r] ← p
       Si (r = 1) Alors TC[p] ← TC[p] + 5
       Sinon Si (r = 2) Alors TC[p] ← TC[p] + 3
             Sinon TC[p] ← TC[p] + 1
             FinSi
       FinSi
     FinPour
   FinPour
3) Fin Depouiller

TDOL de Depouiller : i, j, r, p entiers, p recevant l'indice rendu par Rang ; t chaîne, le titre saisi ; C tableau de 3 entiers, indices des projets déjà cités par l'enseignant en cours (remis à 0 à chaque enseignant ; un indice valant 0 ne correspond à aucun projet). La mise à jour passe toujours par p : c'est l'indice, et non le titre, qui relie TP à TC.

Algorithme du module d'affichage

DEF PROC Afficher (TP : TabCh ; TC : TabEnt ; n : entier)
1) max ← TC[1]
   Pour i de 2 à n faire
     Si (TC[i] > max) Alors max ← TC[i] FinSi
   FinPour
2) Ecrire("Score maximal : ", max)
   ch ← ""
   Pour i de 1 à n faire
     Si (TC[i] = max) Alors
       Si (ch = "") Alors ch ← TP[i]
       Sinon ch ← ch + ", " + TP[i]
       FinSi
     FinSi
   FinPour
3) Ecrire("Projet(s) prime(s) : ", ch)
4) Fin Afficher

TDOL de Afficher : i entier ; max entier, le plus grand cumul ; ch chaîne, la liste en construction. Deux parcours sont nécessaires et non un seul : tant que le maximum n'est pas connu, on ne peut pas savoir quels projets l'atteignent, et un affichage au fil du premier parcours imprimerait des titres finalement battus.

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

Entraînement 01 / 02

Drill SD-I.1 — tableaux de déclaration d'un problème à deux tableaux parallèles

3 questionsCorrigé masqué

Une bibliothèque scolaire suit ses emprunts. Un tableau AD contient les noms de na adhérents, chaque nom étant une chaine de caracteres, avec 5 ≤ na ≤ 100. Un tableau NB de même longueur contient, à l'indice correspondant, le nombre de livres empruntés par l'adhérent. Une procedure Remplir saisit les noms, une procédure Compter met NB à jour à partir de ne fiches d'emprunt, et une procédure Editer affiche les adhérents ayant emprunté le plus de livres.

Donner le tableau des nouveaux types nécessaires à cette solution.
Donner le tableau des objets globaux, avec pour chacun son type ou sa nature et son rôle.
Dire pourquoi le type des deux tableaux ne peut pas figurer dans le tableau des objets globaux.

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

1. TDNT

TabNom = Tableau [1..100] de chaine de caractères
TabEnt = Tableau [1..100] d'entiers

2. TDOG

AD — TabNom — contenant les noms des adhérents
NB — TabEnt — contenant le nombre de livres empruntés par chaque adhérent
na — entier — le nombre d'adhérents
ne — entier — le nombre de fiches d'emprunt à dépouiller
Remplir — procédure — saisir na et les noms des adhérents
Compter — procédure — mettre à jour NB à partir des fiches
Editer — procédure — afficher les adhérents au plus grand nombre d'emprunts

3. Le tableau des objets globaux décrit des objets déjà typés : il attribue un type existant à chaque nom. Tableau [1..100] de chaine de caractères n'existe pas dans le langage algorithmique, il faut le créer ; c'est précisément l'office du tableau des nouveaux types. Y renoncer laisse AD et NB sans type déclaré, et les en-têtes de procédures ne peuvent alors plus nommer leurs paramètres.

Entraînement 02 / 02

Drill SD-I.2 — module de remplissage : contrôles de saisie et unicité

2 questionsCorrigé masqué

On veut remplir un tableau TP par n titres de projets. Chaque titre est une chaine de caracteres ne comportant que des lettres et des espaces, sa longueur est comprise entre 4 et 30, et deux projets ne peuvent pas porter le même titre. Le nombre de projets n doit être compris entre 5 et 40.

On dispose des deux modules suivants, à utiliser sans les développer : Alpha(ch), fonction booléenne vraie si ch ne contient que des lettres et des espaces ; Rang(ch, T, k), fonction retournant l'indice de la case de T contenant ch parmi ses k premières cases, ou -1 si ch n'y figure pas.

Écrire l'algorithme de la procedure Remplir(TP, n) respectant toutes les contraintes.
Donner son tableau des objets locaux.

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

Chaque contrainte de l'énoncé devient une boucle à test final : on redemande la valeur tant qu'elle est refusée.

DEF PROC Remplir (var TP : TabCh ; var n : entier)
1) Répéter
     Ecrire("Nombre de projets : ") ; Lire(n)
   Jusqu'à (n dans [5..40])
2) Pour i de 1 à n faire
     Répéter
       Ecrire("Titre du projet n° ", i, " : ") ; Lire(t)
     Jusqu'à Alpha(t) ET (Long(t) dans [4..30]) ET (Rang(t, TP, i-1) = -1)
     TP[i] ← t
   FinPour
3) Fin Remplir

TDOL de Remplir : i — Type/Nature : entier — Rôle : compteur de la boucle de saisie ; t — Type/Nature : chaîne — Rôle : le titre en cours de saisie, avant validation.

Le test d'unicité porte sur Rang(t, TP, i-1) et non sur Rang(t, TP, n) : au tour i, seules les i-1 premières cases sont remplies, et interroger au-delà reviendrait à comparer le titre saisi avec des cases dont le contenu est indéterminé.

Méthode / Automatismes

Écrire l'analyse du programme principal avant tout code : nom, appels, flux de résultats, dans l'ordre inverse de l'exécution comme le font les corrigés officiels.
Les types tableaux se déclarent dans le tableau des nouveaux types, les variables et les modules dans celui des objets globaux, avec leur rôle.
Deux tableaux parallèles se manipulent toujours par l'indice commun : chercher le libellé, garder l'indice, écrire dans l'autre tableau.
Chaque contrainte chiffrée de l'énoncé devient une boucle de contrôle de saisie ; le barème les compte une par une.
Un maximum à afficher avec ses ex æquo se traite en deux parcours : calcul du maximum, puis collecte de toutes les cases égales.

Pièges classiques

Afficher un seul gagnant alors que l'énoncé demande chaque projet ayant le score maximal : c'est la faute qui coûte le plus dans cette famille. Deux autres pertes fréquentes : oublier l'initialisation de TC à zéro avant le dépouillement, et accepter un titre absent des projets ou déjà cité par le même votant, alors que l'énoncé impose trois titres distincts et existants. Enfin, écrire directement les algorithmes sans l'analyse ni les tableaux de déclaration fait perdre les points de la première question, même si le code est correct.