Feuille d’exercices 3 – avancé#
Avertissement
Ces exercices sont prévus pour les étudiant·e·s ayant déjà réussi la feuille d’exercices « classiques ».
Exercice 8 : anagrammes#
Deux mots sont appelés des anagrammes s’ils sont composés d’exactement les mêmes lettres (comptées avec leur multiplicité). Par exemple :
« juste » et « sujet » sont des anagrammes
« cannes » et « encas » ne sont pas des anagrammes, car la lettre « n » apparaît 2 fois dans « cannes » et seulement une fois dans « encas ».
Question 1. Écrire une fonction anagramme(mot1, mot2) qui prend en entrée deux mots sous la forme de chaînes de caractères, et qui teste si ces deux mots sont l’anagramme l’un de l’autre.
Voici une solution sans utiliser de dictionnaire. L’idée est la suivante : on crée la liste des caractères de chaque mot, puis tant que c’est possible, on élimine des caractères simultanément dans les deux listes. Si on n’aboutit pas à deux listes vides, c’est que les deux mots ne sont pas des anagrammes.
def anagramme(mot1, mot2):
# on vérifie si les mots ont la même longueur
n = len(mot1)
if n != len(mot2):
return False
# on crée la liste des caractères
caracteres1 = [ c for c in mot1 ]
caracteres2 = [ c for c in mot2 ]
# on parcourt les caractères de la première liste
for i in range(n):
c = caracteres1.pop()
# on cherche le caractère dans la seconde liste
trouve = False
j = 0
while j < n-i and not(trouve):
if caracteres2[j] == c:
caracteres2.pop(j)
trouve = True
else:
j += 1
# si on ne le trouve pas, alors
# les deux mots ne sont pas des anagrammes
if not(trouve):
return False
return True
Voici une autre solution, avec le dictionnaire créé dans un exercice de la feuille « classique » :
def compte_caracteres(texte):
D = {}
for c in texte:
if c in D:
D[c] += 1
else:
D[c] = 1
return D
def anagramme_dictionnaire(mot1, mot2):
return compte_caracteres(mot1) == compte_caracteres(mot2)
Question 2. Testez votre fonction avec les paires de mots suivantes :
« niche » et « chien »
« calcul » et « formel »
« anna » et « naan »
« sagemath » et « sagemath »
« garage » et « rage »
« doree » et « dorer »
print(anagramme("niche", "chien"))
print(anagramme("calcul", "formel"))
print(anagramme("anna", "naan"))
print(anagramme("sagemath", "sagemath"))
print(anagramme("garage", "rage"))
print(anagramme("doree", "dorer"))
True
False
True
True
False
False
La relation « être l’anagramme l’un de l’autre » est une relation d’équivalence (vous pouvez le vérifier mathématiquement si vous le souhaitez). On peut donc essayer d’identifier les différentes « classes d’anagrammes » dans une liste de mots.
Question 3. Écrire une fonction classe_anagrammes(liste) qui prend en entrée une liste de mots liste, et qui retourne une liste des classes d’anagrammes de liste.
Puis, tester sur la liste :
L = ["niche", "casser", "carnet", "crasse", "ressac", "sagemath", "nectar", "chien"]
def classe_anagramme(liste):
classes = []
nb_classes = 0
for mot in liste:
i = 0
trouve = False
while i < nb_classes and not(trouve):
if anagramme(mot, classes[i][0]):
classes[i].append(mot)
trouve = True
i += 1
if not(trouve):
classes.append([mot])
nb_classes += 1
return classes
classe_anagramme(["niche", "casser", "carnet", "crasse", "ressac", "sagemath", "nectar", "chien"])
[['niche', 'chien'],
['casser', 'crasse', 'ressac'],
['carnet', 'nectar'],
['sagemath']]
Exercice 9 : chiffrement ROT13#
Le chiffrement ROT13 est un chiffrement « jouet » (c’est-à-dire, à ne pas utiliser sérieusement) qui fonctionne sur des textes contenant uniquement des lettres de l’alphabet en majuscules. Ce chiffrement s’effectue par substitution : on remplace les lettres du message clair en des lettres du message chiffré selon la règle suivante :
caractère "clair" : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
caractère "chiffré" : N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
Par exemple, le caractère J est remplacé par le caractère W.
Question 1 : Écrire le dictionnaire de substitution de ROT13, c’est-à-dire le dictionnaire SUB qui a pour clés les caractères « clairs » allant de A à Z, et qui a pour valeur correspondant à un caractère clair, le caractère chiffré correspondant. Par exemple, il faut que SUB['J'] soit égal à W.
Solution 1 :
SUB = {'A': 'N', 'B': 'O', 'C': 'P', 'D': 'Q', 'E': 'R',
'F': 'S', 'G': 'T', 'H': 'U', 'I': 'V', 'J': 'W',
'K': 'X', 'L': 'Y', 'M': 'Z', 'N': 'A', 'O': 'B',
'P': 'C', 'Q': 'D', 'R': 'E', 'S': 'F', 'T': 'G',
'U': 'H', 'V': 'I', 'W': 'J', 'X': 'K', 'Y': 'L',
'Z': 'M'}
Solution 2, en utilisant les fonctions de conversion ASCII ord (pur passer du caractère au code ASCII) et chr (pour passer du code au caractère) :
SUB = { chr(ord('A') + x): chr(ord('A') + ((x + 13) % 26)) for x in range(26) }
SUB
{'A': 'N',
'B': 'O',
'C': 'P',
'D': 'Q',
'E': 'R',
'F': 'S',
'G': 'T',
'H': 'U',
'I': 'V',
'J': 'W',
'K': 'X',
'L': 'Y',
'M': 'Z',
'N': 'A',
'O': 'B',
'P': 'C',
'Q': 'D',
'R': 'E',
'S': 'F',
'T': 'G',
'U': 'H',
'V': 'I',
'W': 'J',
'X': 'K',
'Y': 'L',
'Z': 'M'}
Question 2 : Écrire une fonction chiffre_rot13(texte) qui prend en entrée un texte formé uniquement de caractères allant de A et Z, et qui retourne le chiffré correspondant par ROT13.
def chiffre_rot13(texte):
res = ""
for t in texte:
res += SUB[t]
return res
print(chiffre_rot13("SAGEMATH"))
FNTRZNGU
Question 3 : Écrire la fonction de déchiffrement dechiffre_rot13(chiffre) qui « inverse » le chiffrement, c’est-à-dire qui prend en entrée un texte chiffré par ROT13, et qui retourne le texte clair correspondant. Puis, vérifier que le déciffrement d’un chiffré donne le message d’origine.
On note que le chiffrement est « involutif », c’est-à-dire qu’en chiffant deux fois on retrouve le texte d’origine. On peut donc « copier » les fonctions :
dechiffre_rot13 = chiffre_rot13
print(dechiffre_rot13('FNTRZNGU'))
print(dechiffre_rot13(chiffre_rot13("LOGICIELDECALCULFORMEL")))
SAGEMATH
LOGICIELDECALCULFORMEL
Question 4 : Déchiffrer le cryptogramme SRYVPVGNGVBAF.
print(dechiffre_rot13("SRYVPVGNGVBAF"))
FELICITATIONS
Exercice 10 : questions avancées sur les listes#
Question 1. Écrire une fonction plus_grande_plage(L) qui prend en entrée une liste d’éléments L, et qui retourne la taille de la plus grande série d’éléments identiques consécutifs (une telle série est appelée une plage). Par exemple, pour la liste L = [0, 1, 1, 1, 3, 3, 2, 3, 3, 3, 3, 4, 0], la fonction retournera \(4\), car la plus grande série d’éléments identiques consécutifs est de taille \(4\) (c’est une série d’entiers qui valent \(3\)).
def plus_grande_plage(L):
n = len(L)
if n == 0:
return 0
i = 0
valeur = L[0]
longueur_max = 0
longueur = 0
while i < n:
longueur = 0
while (i < n and L[i] == valeur):
longueur += 1
i += 1
if (longueur > longueur_max):
longueur_max = longueur
i += 1
if i < n:
valeur = L[i]
return longueur_max
L = [0, 1, 1, 1, 3, 3, 2, 3, 3, 3, 3, 4, 0]
print(plus_grande_plage(L))
L = [0]*17
print(plus_grande_plage(L))
4
17
Question 2. Écrire une fonction troisieme_plus_petit(L) qui prend en entrée une liste d’entiers L, et qui retourne le troisième plus petit entier de la liste. Par exemple, pour la liste L = [1, -8, -4, 5, 0, 6, -8, 2], la fonction retournera \(-4\). Si la liste a strictement moins de \(3\) éléments, retourner un message d’erreur.
def troisieme_plus_petit(L):
if len(L) < 3:
return "Erreur"
petits = [ L[0] ]
if L[1] < petits[0]:
petits.insert(0, L[1])
else:
petits.insert(1, L[1])
if L[2] < petits[0]:
petits.insert(0, L[2])
elif L[2] < petits[1]:
petits.insert(1, L[2])
else:
petits.insert(2, L[2])
for i in range(3, len(L)):
x = L[i]
if x < petits[0]:
petits.insert(0, x)
elif x < petits[1]:
petits.insert(1, x)
elif x < petits[2]:
petits.insert(2, x)
return petits[2]
L = [1, -8, -4, 5, 0, 6, -8, 2]
print(troisieme_plus_petit(L))
M = [2, 3, 6, 0, 0, 0, 0, -1, 0]
print(troisieme_plus_petit(M))
-4
0