Chaînes de caractères Partie I — Opérations de base sur les chaînes

tp d’informatique n˚5 (Python)
Chaînes de caractères
Partie I — Opérations de base sur les chaînes
Rappelons pour commencer qu’on fabrique les chaînes de caractères avec
s1 = "Bonjour le monde !"
et qu’on les affiche (dans la console) avec
print(s1)
Exercice 1 — Tester et expliquer ce que font les méthodes s1.upper(), s1.lower(), s1.lstrip(),
s1.rstrip() et s1.strip().
Exercice 2 — Que fait l’opérateur + appliqué à une chaîne ? Peut-on soustraire deux chaînes ? Peut-on
multiplier une chaîne par un entier ?
Exercice 3 — Parcours des chaînes
Comparer (en les testant !) les deux programmes suivants.
def parcourir_1(s) :
for i in range(len(s)) :
print(s[i])
def parcourir_2(s) :
for c in s :
print(c)
Ensuite, écrire deux programmes prenant comme entrée une chaîne s : le premier qui écrit un caractère sur
deux de s, le second qui écrit tous les caractères de s sauf les espaces. Modifier ensuite ces deux programmes
pour qu’au lieu d’écrire leur résultat, ils renvoient une nouvelle chaîne contenant ce résultat.
Exercice 4 — Conversions chaînes ←→ nombres
a) Les fonctions str(x) et int(s) permettent respectivement de créer une chaîne de caractères à partir
d’un nombre (entier ou pas) x et de créer un entier à partir d’une chaîne valide s. Écrire une fonction
accoler_deux(x,y) qui étant donnés deux entiers x et y renvoie l’entier obtenu en les mettant bout à bout :
par exemple, accoler_deux(15,18) doit renvoyer 1518.
b) Écrire une fonction accoler_plusieurs(t) qui étant donné un tableau d’entiers renvoie l’entier obtenu en
les mettant tous bout à bout : par exemple accoler_plusieurs([14,25,6,0,11]) doit renvoyer 14256011.
c) La fonction float(s) renvoie le nombre à virgule flottante représenté par la chaîne s. Écrire une fonction
EF(x,y) qui à partir de deux entiers x et y fabrique un nombre décimal dont la partie entière est x et la
partie fractionnaire est y.
d) Tester les fonctions ci-dessous. Expliquer le rôle des mots-clés try et except (on pourra essayer d’écrire
ces fonction en les omettant pour voir la différence).
Lycée Saint Louis — MPSI 3
1
TP d’informatique n˚5 (Python)
def essai_1(s) :
try :
x = int(s)
print(x)
except ValueError :
print("Ce n’est pas un nombre à virgule.")
def essai_2(s) :
try :
x = float(s)
print(x)
except ValueError :
print("Ce n’est pas un nombre à virgule.")
e) Tester chr(97) et ord("a"). La différence ord("a") - ord("A") dépend-t-elle de la lettre choisie ?
Essayer avec des caractères exotiques comme "ç" et "é".
Exercice 5 — Fonctions de recherche
a) Comparer les résultats de s.find("Le"), s.find("le") et s.find("le", 9, 12) pour la chaîne s =
"Bonjour le monde et le soleil".
b) Écrire un algorithme trouver_tous(s, m) qui renvoie le tableau de tous les indices auxquels apparaît la
chaîne m dans s. Le tableau renvoyé sera vide si le motif n’apparaît pas.
Partie II — Recherche
Exercice 6 — Écrire une fonction ComparerÀPartirDe(s, m, j) qui teste si le motif m apparaît à partir
de l’indice j dans la chaîne s, et renvoie True ou False en conséquence.
Exercice 7 — Écrire une fonction RechercheNaïve(s, m) qui étant donnée une chaîne s renvoie le tableau
de tous les indices où y apparaît le motif m. L’usage de la fonction find est interdit. Évaluer la complexité
de l’algorithme proposé, en fonction des longueurs des deux chaînes.
Exercice 8 — Algorithme de Rabin-Karp (1987)
Appelons clé d’une chaîne de caractères m la somme des ord(c) pour c in s comme dirait Python. L’algorithme de recherche de motifs de Rabin et Karp consiste à dresser la liste de tous les indices où démarre
une sous-chaîne de s de même longueur que m, et ayant la même clé. Ce tableau étant construit, on vérifie
ensuite naïvement à chacune de ces positions la présence de m.
a) Comment calculer la clé de la sous-chaîne s[i+1:j+1] à partir de la clé de s[i:j] ?
b) En déduire un programme RabinKarp(s, m) qui met en œuvre cet algorithme. La construction du tableau
avec tous les indices potentiels doit s’effectuer en O(`s ) opérations, où `s est la longueur de s.
c) Évaluer la complexité totale de l’algorithme de Rabin-Karp, et la comparer avec celle de l’algorithme naïf.
Partie III — Manipulation des fichiers
Dans cette partie très brève, nous allons voir comment ranger dans un fichier du disque dur le contenu d’une
chaîne, ainsi que l’opération inverse, c’est-à-dire comment récupérer dans une chaîne de caractères le contenu
d’un fichier.
On stockera l’adresse des différents fichiers à utiliser dans des variables, par exemple :
src = "M:/Mon dossier/source.txt"
Lycée Saint Louis — MPSI 3
2
TP d’informatique n˚5 (Python)
dst = "M:/Mon dossier/destination.txt"
Exercice 9 — Après avoir créé (avec le bloc-notes par exemple) un fichier source.txt contenant une phrase
arbitraire, tester le code ci-dessous.
def MettreEnMajuscules(src, dst) :
# Ouverture en mode lecture
with open(source, ’r’) as f:
s1 = f.read()
# La chaîne s1 contient alors la totalité du fichier
# Ouverture en mode écriture
s2 = s1.upper()
with open(cible, ’w’) as f:
f.write(s2)
Exercice 10 — Écrire un programme qui prend en argument un fichier du disque dur et une chaîne de
caractères, et renvoie les indices de toutes les positions où cette chaîne apparaît dans le fichier.
Exercice 11 — Cadavres exquis
On sera prié de ne pas jouer trop longtemps avec le programme de cet exercice, une fois qu’on a réussi à
l’écrire.
a) Écrire un programme qui étant donnés quatre tableaux de chaînes de caractères sujets, verbes, adverbes
et compléments choisit un élément de chacun d’eux au hasard, et renvoie la phrase obtenue en les concaténant
(on ajoutera des espaces là où il faut et un point à la fin). On pourra utiliser par exemple les listes suivantes.
sujets = ["Un poisson rouge", "Le hamster vert", "La grande Prêtresse du Nord",
"Un moine bénédictin", "Napoléon Ier", "Un MPSI 3 mal réveillé",
"Une MPSI 3 mal réveillée", "Lancelot du lac", "Médor"]
verbes = ["mange", "boit", "voit", "croit", "désigne", "fait disparaître",
"met en pièces", "émerveille", "entend", "adoube", "dissimule",
"colorie en rose", "absorbe", "éponge", "écume", "mélange", "extrait"]
adverbes = ["élégamment", "avec insistance", "goulûment", "sans hâte",
"indécemment", "très vite", "sans le savoir", "souvent",
"avec malice"]
compléments = ["une pomme empoisonnée", "son labrador préféré",
"un liquide visqueux", "un chapelet de saucisses",
"une fibre textile", "du papier journal",
"le prochain contrôle d’informatique",
"son voisin de palier", "un nuage frémissant"]
b) Écrire un programme qui écrit dans un fichier du disque dur une centaine de phrases aléatoires ainsi
construites. Entre chacune d’elles, on ajoutera un retour de charriot (c’est-à-dire le caractère "\n").
Partie IV — Un peu de cryptographie
On termine ce TP par deux algorithmes de cryptographie classiques.
Exercice 12 — Cryptage par décalage constant
Celui-ci consiste à appliquer aux caractères de la chaîne s la transformation si 7→ si + c mod 128, avec c une
valeur donnée appelée clé. Écrire les fonctions de cryptage et de décryptage correspondant. Ces fonctions
Lycée Saint Louis — MPSI 3
3
TP d’informatique n˚5 (Python)
s’appliqueront à un fichier du disque dur et produiront un nouveau fichier contenant le texte transformé. On
vérifiera que le texte obtenu après avoir successivement crypté et décrypté le texte initial est correct.
Exercice 13 — L’algorithme de Vigénère
Cette fois-ci on applique la transformation si 7→ si + c(i mod N) mod 128, où c est une chaîne de caractères
qu’on appelle à nouveau la clé, et N est sa longueur. Mêmes questions qu’à l’exercice précédent.
Lycée Saint Louis — MPSI 3
4
TP d’informatique n˚5 (Python)

Download Report