SD-MStructures de données et modularité

Transformer une chaîne selon une règle décrite par l'exemple : résultats pour deux entrées, algorithme à saisie contrôlée, tableau de déclaration, version sans boucle

Idée directrice

Le bac décrit une règle nouvelle sur les chaînes à l'aide de deux exemples — translation d'ordre n en 2021, insertion à une position en 2017 — puis demande toujours la même suite : appliquer la règle à la main sur deux entrées, dont l'une est un cas limite ; écrire l'algorithme complet avec ses saisies contrôlées (chaîne non vide de longueur bornée, paramètre borné par la longueur) ; dresser le tableau de déclaration. Tout se joue dans la traduction de la règle en indices : quels caractères, dans quel ordre, entre quelles bornes.

Ce qui aide à reconnaître la démarche

« consiste à déplacer les n derniers caractères de la chaîne vers son début » ; « donner le résultat de la translation d'ordre » ; « Lire une chaîne ch non vide de 10 caractères au maximum » ; « Dresser le tableau de déclaration des objets utilisés dans l'algorithme » ; « Le texte ne doit pas comporter des espaces successifs »

Besoin d’un point de départ ? Voir la méthode

Commencer par les exemples : découper la chaîne en blocs et vérifier la règle sur l'énoncé avant d'écrire une boucle ; la question « résultat pour deux entrées » contient presque toujours un cas limite (bloc vide, n = Long(ch)).
Lire d'abord la chaîne, puis le paramètre : la borne de n dépend de Long(ch) et se contrôle dans un second Répéter … Jusqu'à.
Construire le résultat dans une nouvelle chaîne res, bloc par bloc, plutôt que de modifier ch pendant qu'on la parcourt.
Une portion contiguë recopiée par une boucle Pour s'écrit Sous_chaine(ch, d, f) avec f = dernier indice + 1 : c'est la clé de la version sans boucle.
Tableau de déclaration : tous les objets de l'algorithme, compteur et longueur intermédiaire compris, avec un rôle d'une ligne.

Les pièges à vérifier dans ta démarche

Contrôler n avant d'avoir lu ch ; écrire n ≤ Long(ch) quand la règle impose n ≤ Long(ch) Div 2 ; écrire Sous_chaine(ch, L-n, n) comme si le troisième paramètre était une longueur (ancienne notation « position, longueur ») ; parcourir ch de 1 à Long(ch) alors que les indices vont de 0 à Long(ch) − 1 ; oublier le cas du milieu vide dans les résultats demandés.

Sujet principal

Exercice 1 (6,5 points) — dans l'esprit de la session principale 2021

6 questionsCorrigé masqué

Un échange d'ordre n appliqué à une chaîne de caractères ch consiste à permuter les n premiers caractères de ch avec ses n derniers caractères, les caractères du milieu restant à leur place. L'ordre n vérifie 1 ≤ n ≤ Long(ch) Div 2.

Exemples :

Pour ch = "soleil" et n = 1, on permute le caractère de tête s et le dernier caractère l : on obtient "loleis".
Pour ch = "soleil" et n = 2, on permute so et il, le milieu le ne bouge pas : on obtient "illeso".

Pour ch = "cle_2026", donner le résultat de l'échange d'ordre n = 3, puis de l'échange d'ordre n = 4.
Écrire un algorithme nommé Echange qui permet de : lire une chaîne ch d'au moins 2 caractères et de 10 caractères au maximum ; lire l'ordre n (entier compris entre 1 et Long(ch) Div 2) ; construire, en parcourant ch caractère par caractère, la chaîne res obtenue par l'échange d'ordre n, puis l'afficher.
Dresser le tableau de déclaration des objets utilisés dans l'algorithme Echange, en adoptant l'en-tête : Objet | Type | Rôle.
Réécrire l'étape de construction de res sans structure itérative, en utilisant uniquement la fonction prédéfinie Sous_chaine et l'opérateur de concaténation +.

N.B. Notation algorithmique en vigueur : les caractères d'une chaîne sont indicés à partir de 0 ; Sous_chaine(ch, d, f) retourne les caractères d'indices d à f − 1.

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

1. Idée : découper ch en trois blocs — les n caractères de tête, le milieu, les n derniers — puis écrire les derniers, le milieu, ceux de tête. "cle_2026" compte 8 caractères.

n = 3 : cle | _2 | 026, d'où $\boxed{\text{"026\_2cle"}}$ .
n = 4 = Long(ch) Div 2 : cle_ | (milieu vide) | 2026, d'où $\boxed{\text{"2026cle\_"}}$ .

2. Idée : chaque contrainte de saisie devient une boucle Répéter … Jusqu'à ; la borne de n dépend de ch, donc ch est lue en premier.

Algorithme Echange
DEBUT
    Répéter
        Ecrire("Donner ch : ")
        Lire(ch)
    Jusqu'à (Long(ch) ≥ 2) Et (Long(ch) ≤ 10)
    Répéter
        Ecrire("Donner n : ")
        Lire(n)
    Jusqu'à (n ≥ 1) Et (n ≤ Long(ch) Div 2)
    L ← Long(ch)
    res ← ""
    Pour i de L-n à L-1 Faire
        res ← res + ch[i]
    Fin Pour
    Pour i de n à L-n-1 Faire
        res ← res + ch[i]
    Fin Pour
    Pour i de 0 à n-1 Faire
        res ← res + ch[i]
    Fin Pour
    Ecrire("Résultat : ", res)
FIN

La première boucle recopie les n derniers caractères, la deuxième le milieu, la troisième les n caractères de tête. Quand L est pair et n = L Div 2, la deuxième boucle va de n à n − 1 : elle ne s'exécute pas, c'est le cas n = 4 de la question 1.

3. Tableau de déclaration des objets de Echange :

ch — Chaîne — chaîne saisie
n — Entier — ordre de l'échange
L — Entier — longueur de ch
res — Chaîne — chaîne obtenue après l'échange
i — Entier — compteur

4. Idée : chaque boucle recopie une portion contiguë de ch, c'est-à-dire une sous-chaîne ; dans Sous_chaine(ch, d, f), f est l'indice qui suit le dernier caractère recopié, pas une longueur.

L ← Long(ch)
res ← Sous_chaine(ch, L-n, L)
      + Sous_chaine(ch, n, L-n)
      + Sous_chaine(ch, 0, n)

Vérification sur "cle_2026" avec n = 3 et L = 8 : Sous_chaine(ch, 5, 8) = "026", Sous_chaine(ch, 3, 5) = "_2" et Sous_chaine(ch, 0, 3) = "cle", d'où "026_2cle".

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

Variantes rencontrées : translation d'ordre n, les n derniers caractères passent en tête (principale 2021, exercice entier de 6,5 points) ; insertion d'une chaîne à une position p, puis module prédéfini équivalent (principale 2017) ; découpage « NumE#commentaire » avec Pos dans un problème (principale 2018) ; occurrences d'un caractère sans distinction de casse (principale 2019) ; miroir d'une chaîne dans une séquence à lire (principale 2025). En section Sciences de l'informatique : classes de caractères et plus longue suite de minuscules d'un mot de passe (principale 2015), nettoyage d'un texte appliqué à chaque ligne d'un fichier (contrôle 2020), suppression des occurrences répétées écrite en récursif (contrôle 2026).

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

1 Drill SD-M.1 — découper un message « k#texte » avec Pos et Sous_chaine

Entraînement 01 / 05

Drill SD-M.1 — découper un message « k#texte » avec Pos et Sous_chaine

4 questionsCorrigé masqué

Dans un groupe de discussion, chaque message est enregistré dans une chaîne au format k#texte, où k est l'indice (à partir de 0) de l'émetteur dans le tableau A des noms des adhérents, et texte le commentaire envoyé, qui peut lui-même contenir le caractère #.

On donne A = ["Rym", "Karim", "Nour", "Yassine"] (na = 4) et le tableau M de nm = 5 messages : M = ["2#Salut", "0#Salut tout le monde", "3#Salut", "2#Merci", "1#Salut"].

Pour m = "1#Top #1", donner la valeur de Pos("#", m), puis l'indice de l'émetteur et le texte du message.
Écrire une fonction Emetteur(m) qui retourne l'indice de l'émetteur du message m, et une fonction Texte(m) qui retourne son commentaire.
Écrire une fonction booléenne Valide(m, na) qui vérifie que m respecte le format : un # précédé d'au moins un caractère, uniquement des chiffres avant le premier #, un indice strictement inférieur à na et un commentaire non vide.
Écrire une procédure Envoyeurs(M, nm, A, c) qui affiche le nom de chaque adhérent ayant envoyé exactement le commentaire c. Quel est l'affichage pour c = "Salut" ?

N.B. Notation algorithmique en vigueur : les caractères d'une chaîne sont indicés à partir de 0 ; Sous_chaine(ch, d, f) retourne les caractères d'indices d à f − 1.

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

1. Idée : Pos retourne la position de la première occurrence ; ce qui précède est l'indice, ce qui suit est le texte, même s'il contient un autre #. Pos("#", "1#Top #1") = 1, l'émetteur est Valeur(Sous_chaine(m, 0, 1)) = 1 et le texte Sous_chaine(m, 2, 8) = "Top #1" (Long(m) = 8).

Fonction Emetteur (m : Chaîne) : Entier
DEBUT
    p ← Pos("#", m)
    Retourner Valeur(Sous_chaine(m, 0, p))
FIN

Fonction Texte (m : Chaîne) : Chaîne
DEBUT
    p ← Pos("#", m)
    Retourner Sous_chaine(m, p+1, Long(m))
FIN

3. Idée : ne jamais appeler Valeur sur une chaîne qui n'est pas formée de chiffres ; les tests s'emboîtent.

Fonction Valide (m : Chaîne, na : Entier) : Booléen
DEBUT
    ok ← Faux
    p ← Pos("#", m)
    Si p ≥ 1 Alors
        k ← Sous_chaine(m, 0, p)
        Si Estnum(k) Alors
            ok ← (Valeur(k) < na)
                 Et (p < Long(m) - 1)
        FinSi
    FinSi
    Retourner ok
FIN

p ≥ 1 écarte à la fois l'absence de # (p = -1) et un # en tête (p = 0) ; p < Long(m) − 1 garantit au moins un caractère après le #. Ainsi Valide("7#Salut", 4), Valide("a#Salut", 4) et Valide("3#", 4) sont faux, Valide("2#Salut", 4) est vrai. Objets locaux : p (Entier, position du premier #), k (Chaîne, partie avant le #), ok (Booléen, résultat).

4. Idée : comparer le commentaire entier à c, puis convertir l'émetteur en indice de A.

Procédure Envoyeurs (M : TabCh, nm : Entier,
                     A : TabCh, c : Chaîne)
DEBUT
    Pour i de 0 à nm-1 Faire
        Si Texte(M[i]) = c Alors
            Ecrire(A[Emetteur(M[i])])
        FinSi
    Fin Pour
FIN

Pour c = "Salut", les messages retenus sont "2#Salut", "3#Salut" et "1#Salut" : l'affichage est $\boxed{\text{Nour, Yassine, Karim}}$ . Le message "0#Salut tout le monde" n'est pas retenu : son commentaire n'est pas exactement "Salut".

2 Drill SD-M.2 — classes de caractères et plus longue suite de minuscules d'un mot de passe

Entraînement 02 / 05

Drill SD-M.2 — classes de caractères et plus longue suite de minuscules d'un mot de passe

4 questionsCorrigé masqué

Pour évaluer un mot de passe mdp (chaîne sans espace ni lettre accentuée), on calcule le score 4 × L + 5 × A − 2 × S, où L est le nombre total de caractères, A le nombre de caractères non alphabétiques et S la longueur de la plus longue suite de lettres minuscules consécutives. Le mot de passe est « Faible » si le score est inférieur à 40, « Moyen » s'il est inférieur à 70, « Fort » sinon.

Pour mdp = "Tn2026ok#Code", donner le nombre de majuscules, de minuscules et de caractères non alphabétiques, la valeur de S, le score et la force.
Écrire une procédure Compter(mdp, @maj, @mi, @au) qui calcule ces trois nombres de caractères.
Écrire une fonction PlusLongue(mdp) qui retourne S.
Un élève a écrit une version de PlusLongue qui ne met à jour le maximum qu'au moment où une suite de minuscules est interrompue par un autre caractère. Quelle valeur retourne-t-elle pour "Tn2026ok#Code", puis pour "abcdefgh" ?

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

1. "Tn2026ok#Code" compte 13 caractères : 2 majuscules (T, C), 6 minuscules (n, o, k, o, d, e) et 5 caractères non alphabétiques (2, 0, 2, 6, #). Les suites de minuscules sont n, ok et ode : S = 3, et la plus longue termine la chaîne.

4\times13+5\times5-2\times3=\boxed{71}

Le score dépasse 70 : le mot de passe est Fort.

Procédure Compter (mdp : Chaîne,
                   @maj, @mi, @au : Entier)
DEBUT
    maj ← 0
    mi ← 0
    au ← 0
    Pour i de 0 à Long(mdp)-1 Faire
        Si mdp[i] ∈ ["A".."Z"] Alors
            maj ← maj + 1
        Sinon Si mdp[i] ∈ ["a".."z"] Alors
            mi ← mi + 1
        Sinon
            au ← au + 1
        FinSi
    Fin Pour
FIN

3. Idée : lg est la longueur de la suite en cours, remise à 0 sur tout caractère qui n'est pas une minuscule ; le maximum est mis à jour à chaque minuscule, donc aussi pour une suite qui se termine avec la chaîne.

Fonction PlusLongue (mdp : Chaîne) : Entier
DEBUT
    lg ← 0
    mx ← 0
    Pour i de 0 à Long(mdp)-1 Faire
        Si mdp[i] ∈ ["a".."z"] Alors
            lg ← lg + 1
            Si lg > mx Alors
                mx ← lg
            FinSi
        Sinon
            lg ← 0
        FinSi
    Fin Pour
    Retourner mx
FIN

4. La version de l'élève ne compare jamais la dernière suite quand elle termine la chaîne : elle retourne 2 pour "Tn2026ok#Code" (la suite ode est perdue) et 0 pour "abcdefgh" au lieu de 8, ce qui donnerait à ce mot de passe le score 32 au lieu de 16.

3 Drill SD-M.3 — occurrences d'un caractère sans distinction de casse, puis lettre la plus fréquente

Entraînement 03 / 05

Drill SD-M.3 — occurrences d'un caractère sans distinction de casse, puis lettre la plus fréquente

4 questionsCorrigé masqué

Soit l'algorithme de la fonction Inconnue suivant :

Fonction Inconnue (c : ……, ch : ……) : ……
DEBUT
    k ← 0
    Pour i de 0 à Long(ch)-1 Faire
        Si Majus(ch[i]) = Majus(c) Alors
            k ← k + 1
        FinSi
    Fin Pour
    Retourner k
FIN

Compléter l'en-tête de la fonction par les types des paramètres et du résultat, sachant que la chaîne ch est parcourue par indices et que c est un seul caractère.
Donner le résultat de Inconnue("a", "Abracadabra"), de Inconnue("B", "Abracadabra") et de Inconnue("z", "Abracadabra").
Déduire le rôle de la fonction Inconnue.
En faisant appel à Inconnue, écrire une fonction Frequente(ch) qui retourne, en majuscule, la lettre ayant le plus grand nombre d'occurrences dans ch (qui contient au moins une lettre), sans distinction de casse ; en cas d'égalité, on retient la lettre qui vient en tête dans l'ordre alphabétique. Donner le résultat pour "Mississippi".

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

1. Idée : les types se lisent sur l'usage. ch est parcourue par indices : Chaîne ; c est comparé à un caractère : Caractère ; k est un compteur retourné : Entier. En-tête : Fonction Inconnue (c : Caractère, ch : Chaîne) : Entier.

2. "Abracadabra" contient A une fois et a quatre fois : Inconnue("a", …) retourne $\boxed{5}$ ; b apparaît deux fois : $\boxed{2}$ ; z n'apparaît pas : $\boxed{0}$ .

3. La fonction Inconnue retourne le nombre d'occurrences du caractère c dans la chaîne ch, sans distinction entre majuscules et minuscules.

4. Idée : appeler Inconnue pour chaque lettre de A à Z et garder le plus grand compte ; le test strict k > mx garde la première lettre atteinte en cas d'égalité.

Fonction Frequente (ch : Chaîne) : Caractère
DEBUT
    lettre ← "A"
    mx ← 0
    Pour o de Ord("A") à Ord("Z") Faire
        k ← Inconnue(Chr(o), ch)
        Si k > mx Alors
            mx ← k
            lettre ← Chr(o)
        FinSi
    Fin Pour
    Retourner lettre
FIN

Pour "Mississippi", I et S apparaissent 4 fois chacune, P 2 fois, M une fois : I, atteinte avant S, est retenue et Frequente("Mississippi") retourne $\boxed{\text{"I"}}$ . Objets locaux : lettre (Caractère), mx, k, o (Entier).

4 Drill SD-M.4 — ne garder que la première occurrence de chaque caractère (version itérative)

Entraînement 04 / 05

Drill SD-M.4 — ne garder que la première occurrence de chaque caractère (version itérative)

3 questionsCorrigé masqué

On veut supprimer d'une chaîne ch toutes les occurrences répétées de chacun de ses caractères, sans distinction entre majuscules et minuscules : seule la première occurrence de chaque caractère est conservée, avec sa casse d'origine. Par exemple, pour ch = "Anna" on obtient "An".

Donner le résultat pour ch = "Barbara" et pour ch = "Mississippi".
Écrire une fonction itérative Premieres(ch) qui retourne la chaîne obtenue, en utilisant les fonctions prédéfinies Pos et Majus.
Donner les valeurs successives de la chaîne résultat pendant l'exécution de Premieres("Barbara").

N.B. Pos(ch1, ch2) retourne l'indice de la première occurrence de ch1 dans ch2, ou −1 si ch1 n'y figure pas ; les indices commencent à 0.

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

1. "Barbara" donne $\boxed{\text{"Bar"}}$ et "Mississippi" donne $\boxed{\text{"Misp"}}$ .

2. Idée : un caractère est gardé s'il n'apparaît pas encore, en majuscule, dans le résultat en construction : Pos retourne alors −1.

Fonction Premieres (ch : Chaîne) : Chaîne
DEBUT
    res ← ""
    Pour i de 0 à Long(ch)-1 Faire
        Si Pos(Majus(ch[i]), Majus(res)) = -1 Alors
            res ← res + ch[i]
        FinSi
    Fin Pour
    Retourner res
FIN

On compare les versions en majuscules mais on ajoute ch[i] tel quel : la casse de la première occurrence est conservée. Au départ res est vide et Pos y retourne −1 : le caractère de tête est toujours gardé. Objets locaux : res (Chaîne), i (Entier).

3. Valeurs successives, avec Pos(Majus(ch[i]), Majus(res)) calculé avant l'ajout :

 i  ch[i]  Pos   res
 0   B     -1    "B"
 1   a     -1    "Ba"
 2   r     -1    "Bar"
 3   b      0    "Bar"
 4   a      1    "Bar"
 5   r      2    "Bar"
 6   a      1    "Bar"

5 Drill SD-M.5 — nettoyer une ligne de texte : espaces successifs, virgules, majuscule initiale

Entraînement 05 / 05

Drill SD-M.5 — nettoyer une ligne de texte : espaces successifs, virgules, majuscule initiale

7 questionsCorrigé masqué

On veut nettoyer une ligne de texte ligne (chaîne d'au plus 255 caractères) en respectant les règles suivantes :

la ligne ne commence pas et ne se termine pas par un espace ;
deux mots sont séparés par un seul espace : la ligne ne doit pas comporter d'espaces successifs ;
il n'y a pas d'espace avant une virgule, et une virgule suivie d'un mot est suivie d'un seul espace ;
le caractère de tête de la ligne, s'il est une lettre, est en majuscule.

Exemple : la ligne " le bac ,c'est en juin " devient "Le bac, c'est en juin".

Donner le résultat du nettoyage de "ali , sami,et nour" et de "2026 , année du bac".
Écrire une fonction Nettoyer(ligne) qui retourne la ligne nettoyée.
Dresser le tableau de déclaration des objets locaux de Nettoyer.

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

1. "ali , sami,et nour" devient "Ali, sami, et nour" et "2026 , année du bac" devient "2026, année du bac" : le caractère de tête est un chiffre, Majus le laisse inchangé.

2. Idée : on ne recopie jamais un espace directement ; on retient seulement qu'un espace est « en attente », et on ne l'écrit qu'au moment où arrive un mot — jamais avant une virgule, ni en début ou en fin de ligne.

Fonction Nettoyer (ligne : Chaîne) : Chaîne
DEBUT
    res ← ""
    esp ← Faux
    Pour i de 0 à Long(ligne)-1 Faire
        c ← ligne[i]
        Si c = " " Alors
            esp ← Vrai
        Sinon Si c = "," Alors
            res ← res + ","
            esp ← Vrai
        Sinon
            Si esp Et (res ≠ "") Alors
                res ← res + " "
            FinSi
            res ← res + c
            esp ← Faux
        FinSi
    Fin Pour
    Si res ≠ "" Alors
        res ← Majus(res[0])
              + Sous_chaine(res, 1, Long(res))
    FinSi
    Retourner res
FIN

Une virgule abandonne l'espace en attente (il n'est pas écrit) et en crée un nouveau pour le mot suivant ; en fin de ligne, l'espace en attente n'est jamais écrit ; tant que res est vide, aucun espace n'est ajouté.

3. Objets locaux de Nettoyer :

res — Chaîne — ligne nettoyée en construction
esp — Booléen — vrai quand un espace doit précéder le prochain mot
c — Caractère — caractère courant
i — Entier — compteur

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.

Où veux-tu aller ?

Transformer une chaîne selon une règle décrite par l'exemple : résultats pour deux entrées, algorithme à saisie contrôlée, tableau de déclaration, version sans boucle

Exercice 1 (6,5 points) — dans l'esprit de la session principale 2021

Changer d’énoncé, garder le raisonnement

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

Drill SD-M.1 — découper un message « k#texte » avec Pos et Sous_chaine

Drill SD-M.2 — classes de caractères et plus longue suite de minuscules d'un mot de passe

Drill SD-M.3 — occurrences d'un caractère sans distinction de casse, puis lettre la plus fréquente

Drill SD-M.4 — ne garder que la première occurrence de chaque caractère (version itérative)

Drill SD-M.5 — nettoyer une ligne de texte : espaces successifs, virgules, majuscule initiale

Relier ce raisonnement au bac