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 des
- le dernier caractère de
S
est identique à celui des
- les caractères de
S
strictement entre le premier et le dernier caractère deS
sont remplacés par le nombre d’éléments des
strictement compris entre les extrémités des
- le premier caractère de
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 * s
où k
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
oux
, on ajoute pas des
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 :
- Les coupures de mots à l’écrit
- Tester en ligne le découpage en syllabbe
- Coupure de mots
- Division des mots en syllabes et en fin de ligne de Bertrand Boutin (web archivé).
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 fonctionpuissance(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 :
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¶
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.
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 :
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)
où 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.