Exercices sur les chaînes de caractères

\(\newcommand{\ds}{\displaystyle}\) \(\newcommand{\Frac}{\ds\frac}\) \(\renewcommand{\r}{\mathbb{ R}}\) \(\newcommand{\C}{\mathbb{ C}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\z}{\mathbb{ Z}}\) \(\newcommand{\Q}{\mathbb{ Q}}\) \(\newcommand{\N}{\mathbb{ N}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\ol}{\overline}\) \(\newcommand{\abs}[1]{\left| \,{#1} \right|}\) \(\newcommand{\pv}{\;;\;}\) \(\newcommand{\ens}[1]{\left\{ {#1} \right\}}\) \(\newcommand{\mens}[1]{\setminus\left\{ {#1} \right\}}\) \(\newcommand{\Par}[1]{\left({#1}\right)}\) \(\newcommand{\pe}[1]{\left\lfloor {#1} \right\rfloor}\) \(\newcommand{\trans}[1]{\,^t\!{#1}}\)

Exercices sur les chaînes de caractères

Entier léger suivant

Un entier strictement positif est dit léger si tous ses chiffres sauf le premier sont nuls. Par exemple, les entiers 7000, 40 ou 5 sont légers tandis que les entiers 2200, 50050 ou 42 ne le sont pas.

On donne un entier \(1\leq n\leq 10^9\) et on demande de trouver le plus petit entier léger \(p>n\). Par exemple si \(n=42\) alors \(p=50\). On commencera par déterminer le nombre de chiffres de \(n\) ainsi que son premier chiffre.

L’exercice a été posé sur codeforces et la suite des entiers « légers » est répertoriée sur le site OIES.

Numéronyme

On va décrire ci-dessous un procédé de compression de mot. On donne une chaîne de caractères, par exemple

s = "Kubernetes"

et on demande de construire une nouvelle chaîne S, dans notre exemple, ce sera

S = "K8s".

La règle de construction de la chaîne S est précisée ci-dessous :

  • si s a au moins trois caractères:

    • le premier caractère de S est identique à celui de s
    • le dernier caractère de S est identique à celui de s
    • les caractères de S strictement entre le premier et le dernier caractère de S sont remplacés par le nombre d’éléments de s strictement compris entre les extrémités de s
  • sinon S = s.

Voici quelques exemples de comportement :

Kubernetes -> K8s
Python -> P4n
Internationalization -> I18n
globalization -> g11n

On aura besoin d’utiliser la fonction str.

Calculer une moyenne

On donne une chaîne de caractères représentant une addition de nombres flottants séparés par des signes + et d’éventuels espaces et on vous demande de calculer la moyenne des nombres qui apparaisent. La virgule décimale n’est pas écrite à l’aide d’un point mais d’une virgule. Par exemple, si la chaîne est

"12,25+  1+10+10,75 + 7+1,25+6,25   + 6,75+13,5+8,5"

la moyenne à calculer devrait être 7,725. On utilisera les méthodes de chaînes split et replace et le constructeur float.

Diagonale de 1

On donne un entier \(\mathtt{n\geq 0}\), par exemple \(\mathtt{n=5}\) et on demande de construire une chaîne \(\mathtt{s}\) formant un motif comme expliqué ci-dessous. Si \(\mathtt{n=5}\) alors \(\mathtt{s}\) s’affichera ainsi :

1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

Plus généralement, la chaîne s à construire est formée de n lignes, chacune de n caractères parmi '0' ou '1' et en sorte que le \(\mathtt{k^e}\) caractère de la \(\mathtt{k^e}\) ligne soit '1', les autres valent '0'. Entre deux caractères d’une même ligne, il aura un espace.

On utilisera la méthode join et les opérateurs + et * sur les chaînes et éventuellement le constructeur list. Vous pouvez aussi utiliser des listes en compréhension si elles vous sont connues.

Noter qu’on demande de construire une chaîne et non pas seulement de réaliser l’affichage du motif.

Il est possible d’écrire le code sur une seule ligne.

Chaîne représentant un motif en forme de croix

On souhaite générer une chaîne de caractère représentant un motif en forme de croix décrit ci-après. On part d’un entier impair \(n>1\) et le motif est de forme carrée, rempli de zéros ou de uns, en sorte que les zéros forment une croix. Par exemple, si \(n=9\), le motif est :

1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0
1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1

Le motif est un carré formé de \(n\times n\) chiffres valant 0 ou 1. Deux chiffres seront toujours séparés d’un unique espace. Les axes vertical et horizontal de symétrie du carré sont formés de 0 et les autres parties du carré sont formées de 1.

Il est attendu de créer une chaîne (et pas seulement d’afficher le motif). On utilisera la méthode join et la fonction list et les opérations d’addition et d’itération de chaînes (du type, k * sk est un entier positif et s est une chaîne). On pourra aussi utiliser l’itération de liste comme l’exemple ci-dessous l’explique :

k = 5
L = k * ["Noix"]

print(L)
['Noix', 'Noix', 'Noix', 'Noix', 'Noix']

Carrés concentriques de lettres

On demande de dessiner un motif formé de lettres majuscules placées dans l’ordre alphabétique et formant des carrés emboîtés. Voici le motif à dessiner pour \(n=10\) :

A A A A A A A A A A
A B B B B B B B B A
A B C C C C C C B A
A B C D D D D C B A
A B C D E E D C B A
A B C D E E D C B A
A B C D D D D C B A
A B C C C C C C B A
A B B B B B B B B A
A A A A A A A A A A

Le motif est constitué d’une succession de carrés concentriques formés de lettres majuscules toutes identiques et progressant de l’extérieur vers l’intérieur dans l’ordre alphabétique. Entre deux caractères d’une même ligne, il y aura un espace. On demande de créer une chaîne de caractères qui une fois affichée aura l’allure indiquée ci-dessus.

Plusieurs méthodes sont envisageables. On pourra par exemple créer une liste 2D dans laquelle les caractères seront placés individuellement. La liste sera ensuite transformée en chaîne en utilisant, à plusieurs reprises, la méthode join. Il est conseillé de calculer le nombre N de carrés concentriques en fonction de n, bien qu’il soit aussi possible de s’en passer.

Il est possible de réaliser la construction en un one-liner.

Mettre un nom au pluriel

Ecrire une fonction qui prend en entrée un nom commun de la langue française et renvoie le même mot mais écrit au pluriel. Les règles de mise au pluriel sont les suivantes :

  • pour mettre au pluriel, on ajoute un s à la fin du mot, sauf exceptions décrites ci-dessous ;
  • si le mot se termine par s, z ou x, on ajoute pas de s final ;
  • les noms se terminant en AIL, en AL ou en AU font leur pluriel en AUX, comme décimal qui devient décimaux, travail qui devient travaux, etc. ; il y a cependant une liste d’exceptions signalées ci-dessous ;
  • les noms se terminant en EU font leur pluriel en EUX ; il y a cependant une liste d’exceptions signalées ci-dessous ;
  • certains mots signalés ci-dessous, comme bijou, se terminant en OU, font leur pluriel en OUX.

Exceptions :

  • AIL : corail, émail, soupirail, travail, vantail, vitrail
  • AL : bal, cal, carnaval, cérémonial, chacal, festival, récital, régal
  • AU : landau, sarrau
  • EU : bleu, pneu, émeu, lieu
  • OU : bijou, caillou, chou, genou, hibou, joujou, pou

Si vous ne connaissez pas les slices, vous pourrez avoir besoin d’écrire une fonction term(mot, k) qui renvoie la partie d’un mot formée de ses k dernières lettres. Si k dépasse la longueur du mot, la fonction renverra le mot en entier.

Découpage en syllabes

Dans cet exercice, on demande d’écrire un programme qui découpe un mot écrit en syllabes. Pour simplifier, les exemples soumis au code seront sans accents et les mots ne contiendront ni apostrophe (comme aujourd’hui) ni tiret (comme chou-fleur). Certaines exceptions ne seront pas implémentées.

Une syllabe contient toujours un groupe de voyelles (par exemple ba-teau contient deux syllabes)

Toutes les voyelles contiguës d’un mot comptent comme une seule et donc une syllabe ne peut couper une suite de voyelles contiguës (par exemple, on découpe théâ-tre). Par exemple, dans le mot pointeur, la séquence oi compte comme une seule voyelle et de même, la séquence eu comme une seule voyelle

Certains groupements de consonnes sont insécables, tels que gn, ph, th, lh, ou encore des groupements du type br ou fl où la 2e consonne est un r ou un l.

La césure se fait entre un groupement de voyelles et un groupement de consonnes (par exemple a-dieu ou bra-ve) ou entre deux groupements de consonnes (comme ad-mis).

On ne laisse pas dans une même syllabe deux blocs consécutifs de consonnes. Lorsqu’on a une succession deux consonnes qui ne forment pas un bloc, on découpe entre les deux consonnes. Lorsqu’on a une succession de trois blocs de consonnes, on coupe entre le 2e et le 3e, par exemple obs-tiné.

Quelques références :

Afficher le développement par la formule du binôme

On donne un entier \(\mathtt{n \geq 0}\) et on demande d’afficher le développement de \((x+y)^n\) par la formule du binôme de Newton.

Par exemple, pour n=7, le développement est :

\(\mathtt{(x+y)^7=x^7 + 7x^6y + 21x^5y^2 + 35x^4y^3 + 35x^3y^4 + 21x^2y^5 + 7xy^6 + y^7}\).

Dans l’exercice, l’affichage attendu sera :

x^7 + 7x^6y + 21x^5y^2 + 35x^4y^3 + 35x^3y^4 + 21x^2y^5 + 7xy^6 + y^7

On notera qu’il n’y a pas de facteur 1 et que les puissances d’exposant 0 et 1 sont écrites de manière simplifiée.

On pourra essayer d’obtenir, dans un premier temps, l’affichage approximatif :

1x^7y^0 + 7x^6y^1 + 21x^5y^2 + 35x^4y^3 + 35x^3y^4 + 21x^2y^5 + 7x^1y^6 + 1x^0y^7

On utilisera des f-strings, il n’y a que le minimum à connaître. On utilisera la méthode join pour placer les signes +.

Pour traiter le facteur 1 et les puissances d’exposant 0 et 1, on pourra, au choix

  • écrire une fonction monome(c, a, i, b, j) et qui renverra une chaîne représentant convenablement \(\mathtt{ca^iby^j}\) ; pour ne pas avoir trop de cas à traiter, on pourra introduire une fonction puissance(x, k) représentant convenablement \(\mathtt{x^k}\) ;
  • utiliser la méthode replace mais, ici, c’est plutôt un hack.

L”exercice a été posé sur le forum Python du site OpenClassrooms.

On pourra réaliser un affichage de la formule sous Matplotlib avec la syntaxe demandée plus haut pour obtenir une mise en forme correcte des exposants :

../../../_images/binome_newton_mpl.png

Nombres dont la somme des chiffres vaut 42

Déterminer combien d’entiers existent entre 1 et un million et dont la somme des chiffres de l’écriture en base 10 vaut 42 (on devra en trouver 6062). On utilisera les fonctions natives int et str même si c’est algorithmiquement peu efficace. Si vous les connaissez, vous pouvez utiliser la fonction standard sum, une liste en compréhension voire une expression génératrice.

On pourra écrire une fonction dsum(n) renvoyant la somme des chiffres de l’écriture en base 10 de l’entier n.

Concaténer des entiers consécutifs (méthode de chaînes)

Si on écrit côte-à-côte tous les entiers entre 1 et n = 42, on obtient le très grand entier N suivant :

123456789101112131415161718192021222324252627282930313233343536373839404142

On peut vérifier que N est un entier composé de \(\mathtt{p=75}\) chiffres (il suffit de compter).

Plus généralement, étant donné un entier \(\mathtt{n\geq 1}\), on place côte-à-côte tous les entiers entre 1 et \(\mathtt{n}\), écrits en base 10 ce qui construit un très grand entier \(\mathtt{N}\). On demande de calculer le nombre \(\mathtt{p}\) de chiffres de \(\mathtt{N}\).

On construira explicitement la représentation de N sous forme de chaîne de caractères dont on calculera la longueur.

Mots en lignes, en colonnes (avec la méthode join)

On donne une liste de mots, tous de même longueur.

On demande de construire deux chaînes :

  • l’affichage de la première chaîne montre les chaînes écrites les une sous-les autres
  • l’affichage de la deuxième chaîne montre les chaînes écrites en colonnes séparés de traits verticaux.

Par exemple, si la liste des mots est :

mots = ["POIRE", "SAVON", "LAVER", "LABEL"]

alors l’affichage horizontal sera :

POIRE
SAVON
LAVER
LABEL

et l’affichage vertical sera :

|P|S|L|L|
|O|A|A|A|
|I|V|V|B|
|R|O|E|E|
|E|N|R|L|

Il s’agit de placer les mots dans des colonnes. On notera la présence de traits aux extrémités.

Un trait vertical s’obtient avec la combinaison Alt Gr + 6. Noter qu’on demande de produire une chaîne et pas seulement un affichage. On utilisera à plusieurs reprises la méthode join afin d’obtenir la chaîne

Nombre de pages à imprimer

Certains utilitaires d’impression permettent à l’utilisateur de définir les pages à imprimer. Par exemple, s’il écrit

3-5, 7, 9, 11-15

les pages à imprimer sont les pages :

3, 4, 5, 7, 9, 11, 12, 13, 14, 15.

ce qui fait un total de 10 pages.

On demande d’écrire un programme Python qui calcule le nombre total de pages à imprimer. Les pages seront données sous la forme d’une chaîne de caractères formée d’un ou plusieurs items séparés par une virgule suivie d’un unique espace. Tout item est de l’une des deux formes suivantes :

  • un nombre décimal
  • deux entiers décimaux, écrits dans l’ordre croissant et séparés par un simple et unique tiret, sans espaces.

Par exemple, la chaîne littérale Python suivante :

"3-5, 7, 9, 11-15"

est une présentation valide d’une suite d’items.

Pour séparer suivant les virgules et les tirets, on aura besoin de la méthode split. On aura aussi besoin de la fonction int.

Afficher une somme de fractions

  1. On donne deux entiers positifs non nuls et on demande d’afficher, en mode texte, la fraction \(\mathtt{\ds\frac ab}\). Par exemple, les fractions \(\mathtt{\ds\frac {45073}{512}}\) et \(\mathtt{\ds\frac {45073}{2030}}\) devront s’afficher comme suit :

    45073
    -----
     512
    
    45073
    -----
    2030
    

    On centrera au mieux le numérateur et le dénominateur par rapport au trait de fraction. Si l’un deux ne peut être exactement centré, comme c’est le cas de la 2e fraction donnée en exemple, il y aura un blanc de moins à gauche du nombre qu’à droite. Une fraction sera représentée par une liste de trois chaînes de même longueur (espaces inclus) :

    • le numérateur,
    • le trait de fraction écrit avec des tirets
    • le dénominateur.

    On écrira une fonction pretty_frac(a, b). On ne cherchera pas à simplifier la fraction. Une fraction du type \(\mathtt{\ds\frac {a}{1}}\) sera représentée par \(\mathtt{a}\) mais la fonction renverra toujours une liste de trois chaînes de même longueur.

    Par exemple, pretty_frac(45073, 42) renverra la liste suivante :

    ['45073', '-----', ' 42  ']
    

    formée de 3 chaînes ayant 5 caractères chacune.

  2. Utiliser la fonction précédente pour afficher la somme de fractions suivante

    \(\mathtt{1+\frac 12+\frac 13+\dots+\frac 1n}\)

    pour un entier \(\mathtt{n>0}\) donné. On affichera la fraction simplifiée égale à la somme à calculer. Par exemple, si n = 12, on devra obtenir :

        1   1   1   1   1   1   1   1   1    1    1    86021
    1 + - + - + - + - + - + - + - + - + -- + -- + -- = -----
        2   3   4   5   6   7   8   9   10   11   12   27720
    

    Pour calculer la valeur de la somme des fractions, on utilisera le module standard fractions. On montre ci-dessous des exemples de ce qu’il faut savoir pour calculer la somme demandée :

    from fractions import Fraction
    
    # Fraction 2/3
    x = Fraction(2, 3)
    
    # Fraction 1/12
    y = Fraction(1, 12)
    print(x, y)
    
    # on peut calculer une somme de fractions
    # avec l'opérateur + comme pour des entiers
    s = x + y
    
    # La fraction est fournie simplifiée
    print(s)
    
    2/3 1/12
    3/4
    

Afficher une addition

On donne une liste de nombre entiers positifs et on demande d’afficher l’opération d’addition de tous ces entiers et du résultat. Par exemple, si les entiers sont 10, 2038 et 8, l’opération sera affichée comme ci-dessous :

    10
+ 2030
+    8
------
  2048

Plutôt que de réaliser un affichage, on produira une chaîne dont l’affichage est l’opération d’addition visible ci-dessus. On utilisera la méthode join et la fonction str

Affichage à sept segments

L’objectif de l’exercice est d’écrire un ensemble de fonctions permettant de réaliser, en mode texte, un affichage de chiffres avec sept segments. Par exemple, l’entier 2038 sera affiché sous la forme :

 _____________    _____________    _____________    _____________
              |  |             |                |  |             |
              |  |             |                |  |             |
              |  |             |                |  |             |
              |  |             |                |  |             |
              |  |             |                |  |             |
 _____________|  |             |   _____________|  |_____________|
|                |             |                |  |             |
|                |             |                |  |             |
|                |             |                |  |             |
|                |             |                |  |             |
|                |             |                |  |             |
|_____________   |_____________|   _____________|  |_____________|

Chaque chiffre est représenté en affichant des segments parmi les sept possibles que montre l’image ci-dessous :

../../../_images/ssd_label.png

Pour la commodité de l’écriture du code, les segments utilisés sont étiquettés par une lettre de A à G (cf. l’image ci-dessus).

Chaque segment horizontal d’un chiffre est construit en utilisant w caractères blanc souligné (autrement dit, le caractère _) et chaque segment vertical est construit en utilisant h caractères comme ceci | (une barre verticale). Dans l’exemple ci-dessus de l’affichage de 2038, on a choisi w=13 et h=6. Tous les autres caractères (des blancs) sont des caractères espace.

Les 7 segments seront étiquettés de A à G suivant la disposition visible ci-dessus. Chaque chiffre reçoit un code formé des lettres entre A et G utilisées pour représenter le chiffre. Par exemple, le chiffre 9 se code avec la chaîne "GFABCD" et qui indique les 6 segments affichés.

Pour construire un chiffre, on utilise un liste à deux dimensions formée de caractères, initialement des caractères espace Cette liste sera appelée t. La taille, lignes x colonnes, de t est \(\mathtt{(2h+3)\times (w+2)}\). Pour coder chacun des chiffres, on utilise son « code » sous la forme d’une chaîne de caractères entre A et G, par exemple le code "GFABCD" correpond au chiffre 9 et on change dans la liste t les caractères espace d’un segment par le caractère de remplissage adapté (_ pour un segment horizontal et | pour un segment vertical). Il est conseillé de faire un schéma indiquant les indices dans la liste t de début et de fin de chaque segment. Pour construire un chiffre, on définira une fonction remplir(code, h, w)code est la chaîne de caractères entre A et G indiquant les segments utilisés. On écrira aussi une fonction chiffre(c) qui renvoie le code d’un chiffre donné c.

Enfin, on écrira une fonction ssd(n) qui affiche le nombre entier n en représentant chaque chiffre avec un affichage à 7 segments. Deux chiffres voisins seront affichés en les séparant d’une colonne de deux espaces.

Mot suivant dans l’ordre alphabétique

On se donne un alphabet formé de lettres distinctes et classées dans l’ordre strictement croissant, par exemple alpha = "ABIL". On donne un mot m, composé de lettres uniquement dans l’alphabet donné et on demande de trouver le mot qui suit immédiatement le mot m dans l’ordre alphabétique et composé uniquement de lettres parmi l’alphabet donné. Par exemple, avec l’aphabet "ABIL", le mot qui suit "BAILL" est "BALAA". De même, le mot qui suit "LLLLL" est "AAAAAA". On écrira une fonction suivant(mot, alpha).

Anagrammes par ordre lexicographique

On donne une chaîne s. On demande d’écrire une fonction suivant(s) qui détermine, le mot obtenu en permutant les lettres de s et qui soit immédiatement postérieur à s pour l’ordre lexicographique (ie l’ordre du dictionnaire). Par exemple :

  • le suivant de « RARBA » est « RBAAR »
  • le suivant de « ARRBA » est « BAARR »
  • « RRBAA » n’a pas de suivant

En déduire une fonction qui génère tous les anagrammes d’un mot donné. Par exemple, vérifier que la liste des anagrammes de « BARRA » est :

['AABRR', 'AARBR', 'AARRB', 'ABARR', 'ABRAR', 'ABRRA', 'ARABR', 'ARARB', 'ARBAR',
'ARBRA', 'ARRAB', 'ARRBA', 'BAARR', 'BARAR', 'BARRA', 'BRAAR', 'BRARA', 'BRRAA',
'RAABR', 'RAARB', 'RABAR', 'RABRA', 'RARAB', 'RARBA', 'RBAAR', 'RBARA', 'RBRAA',
'RRAAB', 'RRABA', 'RRBAA']

Vérifier que le mot ABRACADABRA possède 83160 anagrammes.

Ecriture dans une base de l’entier suivant

On donne une base \(b\) de numération et une chaîne de caractères s représentant un entier \(n\) dans la base \(b\). Par exemple, si \(n=1599\) alors

  • si \(\mathtt{b = 10}\) alors s = "1599"
  • si \(\mathtt{b = 2}\) alors s = "11000111111"
  • si \(\mathtt{b = 20}\) alors s = "3jj"

On demande d’écrire une fonction suivant(n, b) qui renvoie la chaîne de caractères représentant l’entier \(n+1\) en base \(b\). Par exemple, si \(n=1599\) alors

  • si \(\mathtt{b = 10}\) alors suivant(n, b) = 1600
  • si \(\mathtt{b = 2}\) alors suivant(n, b) = 11001000000
  • si \(\mathtt{b = 20}\) alors suivant(n, b) = 400

On supposera que \(2\leq b\leq 36\) et les chiffres de la base \(b\) seront les \(b\) premiers caractères de la chaîne formée des chiffres décimaux (de 0 à 9) suivis des lettres alphabétiques minuscules (de a à z), autrement dit la chaîne :

0123456789abcdefghijklmnopqrstuvwxyz

Immatriculation suivante

En France, le système d’immatriculation de véhicules (SIV) utilise des immatriculations ayant le motif suivant :

AB-012-CD

autrement dit, de la gauche vers la droite :

  • un bloc de deux lettres majuscules,
  • un bloc de trois chiffres,
  • un bloc de deux lettres majuscules.

Par exemple, CZ-421-UB est une immatriculation valide. Le bloc central 000 n’est jamais utilisé. Pour simplifier, on suppose que toutes les lettres sont utilisées.

Les immatriculations évoluent depuis la 1re immatriculation qui est AA-001-AA jusqu’à la dernière qui est ZZ-999-ZZ. Pour obtenir l’immatriculation qui suit immédiatement une immatriculation donnée, on fait avancer un des trois blocs au bloc suivant avec la priorité définie par :

  • le bloc de 3 chiffres,
  • puis le bloc de lettres à droite,
  • puis le bloc de lettres à gauche.

Le suivant d’un bloc est le suivant dans l’ordre naturel des chiffres ou dans l’ordre alphabétique. Par exemple, le suivant de 421 est 422, le suivant du bloc CE est CF. Le suivant du bloc 999 est 001 et le suivant du bloc ZZ est AA.

Ecrire une fonction qui étant donné une immatriculation renvoie l’immatriculation suivante ou, si l’immatriculation n’a pas de suivante, renvoie la chaîne vide.