Objectif : Ces exercices ont pour but de vous faire écrire des fonctions récursives manipulant des paramètres de type nombre. On demande donc que toutes les fonction écrites soient récursives (usage des boucles interdit). Il est également important de bien tester vos fonctions.
On cherche dans ce TP à calculer une liste représentant la décomposition en facteurs premiers d’un entier donné, c'est-à-dire son écriture sous la forme d'un produit de facteurs $p^e$ tels que $p$ est un nombre premier et $e$ est un entier le plus grand possible.
Par exemple, $2^2 \times 3^1 \times 5^2$ est la décomposition en facteurs premiers de $300$.
Dans un second temps, on cherchera à optimiser les fonctions écrites.
On représentera en Python la décomposition en facteurs premiers d'un nombre entier $n \geq 2$ comme une liste de couples de la forme (p, e) indiquant que le facteur $p^e$ apparaît dans la décomposition de $n$. On supposera que cette liste est triée par facteurs croissants, et ne contient aucun exposant nul.
Par exemple, la décomposition de $13$ est
[(13,1)]car $13$ est un nombre premier et $13 = 13^1$, et celle de $300$ est[(2, 2), (3, 1), (5, 2)]car $300 = 2^2 \times 3^1 \times 5^2$.
Complétez la fonction récursive recomposition qui étant donnée une liste sous cette forme calcule la valeur du nombre correspondant.
def recomposition(liste_facteurs):
"""Renvoie le nombre dont la décomposition en facteurs premiers
est fournie.
"""
if len(liste_facteurs) == 1:
return(liste_facteurs[0][0]**liste_facteurs[0][1])
else:
liste_2=liste_facteurs*1
liste_2.pop(0)
return(liste_facteurs[0][0]**liste_facteurs[0][1])*(recomposition(liste_2))
print(recomposition([(2, 2), (3, 1), (5, 2)]) == 300)
Complétez la fonction récursive chaine_decomp(liste_facteurs) qui renvoie une chaîne représentant sous une forme lisible la décomposition en facteurs premiers fournie en paramètre.
Par exemple, chaine_decomp([(2, 2), (3, 1), (5, 2)]) pourrait renvoyer la chaîne "2**2 * 3 * 5**2".
def chaine_decomp(liste_facteurs):
"""Renvoie une chaîne de caractères représentant la décomposition
en facteurs premiers fournie.
"""
if len(liste_facteurs)==1:
return(str(liste_facteurs[0][0]) + str("**") + str(liste_facteurs[0][1]))
else:
liste_2=liste_facteurs*1
liste_2.pop(0)
return(str(liste_facteurs[0][0]) + str("**") + str(liste_facteurs[0][1])+ str(" * ") +chaine_decomp(liste_2))
print(chaine_decomp([(2, 2), (3, 1), (5, 2)]))
print(chaine_decomp([(2, 2), (3, 1), (5, 2)]) == "2**2 * 3 * 5**2")
Complétez la fonction suivante, puis testez-la.
from math import sqrt
def est_premier(n, div=2):
"""Renvoie True si n n'a aucun diviseur supérieur ou égal à div (et
différent de lui-même).
Exception : renvoie False si n est inférieur ou égal à 1.
Si div n'est pas précisé lors de l'appel, renvoie True si n est premier.
"""
if n <= 1:
return False # Ni 1, ni 0 ne sont premiers
elif div >= (sqrt(n))+1:
return True
elif n%div == 0: # Si div est un diviseur de n
return False
else:
# Si aucun de ces cas n'est vérifié
return(est_premier(n,div+1)) # Faire ici un appel récursif !
# Écrivez vos tests ici :
#A modifier plus tard
est_premier(5)
Essayez de déterminer si le nombre 64231 est premier.
# Écrivez votre test ici.
est_premier(64231)
Le nombre d'appels récursifs effectués par un appel à est_premier(n) est de l'ordre de n. Ceci peut poser des problèmes, comme on l'a vu dans le test précédent. Comment améliorer la fonction pour diminuer le nombre d'appels récursifs nécessaires ? Faites la modification nécessaire ci-dessus. Testez à nouveau la primalité de $64231$.
À l’aide de la fonction est_premier programmée à la section précédente, complétez la fonction ci-dessous qui calcule le plus petit nombre premier strictement supérieur à $p$.
Par exemple,
premier_suivant(15)renvoie 17,premier_suivant(11)renvoie 13.
def premier_suivant(p):
"""Renvoie le plus petit nombre premier strictement supérieur à p."""
if est_premier(p+1):
return p+1
else:
return(premier_suivant(p+1))
print(premier_suivant(11) == 13)
print(premier_suivant(12) == 13)
Complétez la fonction ci-dessous qui étant donnés $n$ et $p$ renvoie l’exposant de $p$ dans la décomposition en facteurs premiers de $n$ , ainsi que le nombre restant à décomposer.
Par exemple, comme $600$ est divisible trois fois par 2 et que $600 = 2^3 \times 75$,
exposant(600,2)devra renvoyer(3,75), et comme 600 n’est pas divisible par 7,exposant(600,7)devra renvoyer(0,600).
def exposant(n, p, puis = 0):
"""Renvoie l'exposant de p dans la décomposition en facteurs premiers de
n, et le nombre restant à décomposer."""
if n%p != 0 :
return(puis,n)
else:
return(exposant(n//p,p, puis+1))
print(exposant(600,2))
print(exposant(600,2) == (3, 75))
#A faire
À l’aide de la fonction précédente, complétez la fonction récursive decomposition(n) suivante, qui doit renvoyer la liste des couples représentant la décomposition en facteurs premiers de n.
Par exemple,
decomposition(13)renverra[(13,1)], etdecomposition(300)renverra[(2, 2), (3, 1), (5, 2)].
def decomposition(n, p=2, l=[]):
"""Renvoie une chaîne décrivant la décomposition en facteurs premiers de
n. Si l'argument p est donné, la recherche de facteur commence à
cette valeur."""
if est_premier(n):
l.append((n,1))
return(l)
else:
(x,y)=exposant(n,p)
if x == 0:
return(l)
l.append((p,x))
return(decomposition(n,premier_suivant(p),l))
print(decomposition(300))
print(decomposition(13) == [(13,1)])
print(decomposition(300) == [(2, 2), (3, 1), (5, 2)])
#A faire
Vous connaissez l'algorithme d'Euclide qui calcule le plus grand commun diviseur à deux entiers $a$ et $b$. Cependant, si l'on connaît la décomposition en facteurs premiers de $a$ et $b$, il est facile d'en déduire leur PGCD : en effet, la décomposition en facteurs premiers du PGCD de $a$ et $b$ contient tous les facteurs premiers communs à $a$ et $b$, et l'exposant de chacun de ces facteurs est le minimum des exposants de ce facteur dans la décomposition de $a$ et de $b$.
Par exemple le PGCD de $75$ et $90$ est $15 = 3^1 \times 5^1$ car $75 = 3^1 \times 5^2$ et $90 = 2^1 \times 3^2 \times 5^1$.
Complétez la fonction suivante qui calcule la décomposition en facteurs premiers du PGCD de deux nombres à partir de leurs décompositions.
def pgcd_decomp(decomp_a, decomp_b, l=[], i=0,j=0):
if i >= len(decomp_a):
return(l)
elif j >= len(decomp_b):
return(pgcd_decomp(decomp_a,decomp_b,l,i+1,j=0))
else:
if decomp_a[i][0] != decomp_b[j][0]:
return(pgcd_decomp(decomp_a,decomp_b,l,i,j+1))
else:
if decomp_a[i][1]< decomp_b[j][1]:
l.append(decomp_a[i])
else:
l.append(decomp_b[j])
return(pgcd_decomp(decomp_a,decomp_b,l,i+1,j=0))
return(l)
print(pgcd_decomp([(3, 1), (5, 2)], [(2, 1), (3, 2), (5, 1)]))
print(pgcd_decomp([(3, 1), (5, 2)], [(2, 1), (3, 2), (5, 1)]) == [(3, 1), (5, 1)])
Compléter la fonction ppcm_decomp suivante calculant la décomposition du PPCM de deux nombres en fonction de leurs décompositions.
def ppcm_decomp(decomp_a, decomp_b, l=[], i=0, j=0, a=0):
if a == 2:
return(l)
elif i>= len(decomp_a):
i=0
j=0
return(ppcm_decomp(decomp_b, decomp_a,l,i,j,a+1))
elif j>= len(decomp_b):
if decomp_a[i] not in l:
l.append(decomp_a[i])
j=0
return(ppcm_decomp(decomp_a, decomp_b,l ,i+1, j,a))
else:
if decomp_a[i][0] != decomp_b[j][0]:
return(ppcm_decomp(decomp_a, decomp_b, l, i, j+1,a))
else:
if decomp_a[i][1]> decomp_b[j][1]:
if decomp_a[i] not in l:
l.append(decomp_a[i])
else:
if decomp_b[j] not in l:
l.append(decomp_b[j])
j=0
return(ppcm_decomp(decomp_a, decomp_b, l, i+1, j,a))
print(ppcm_decomp([(3, 1), (5, 2)], [(2, 1), (3, 2), (5, 1)]))
print(ppcm_decomp([(3, 1), (5, 2)], [(2, 1), (3, 2), (5, 1)]) == [(2, 1), (3, 2), (5, 2)])
Les différentes fonctions réalisés lors des questions précédentes ont tendance à effectuer plusieurs fois les mêmes calculs, par exemple :
Dans la suite, nous allons utiliser une liste et un dictionnaire pour mémoriser les nombres premiers que nous rencontrons, ainsi que les décompositions déjà calculées, ceci afin d'être sûrs de ne jamais les recalculer une seconde fois.
Ré-écrivons les fonctions est_premier et premier_suivant de sorte que l'on ne fasse que des divisions par des nombres premiers. Pour ce faire on stockera dans une liste tous les nombres premiers inférieurs à une certaine valeur.
def est_premier_opti(n, L, indice_premier=0):
""" Vérifie si n est premier en ne divisant que par les nombres
premiers de L. S'il manque des nombres, on appelera 'premier_suivant_opti'
pour compléter la liste.
Le nombre `indice_premier` représente l'indice dans L du nombre premier
que l'on est en train de traiter.
"""
if n<= 1:
return False
if L[len(L)-1] > n:
return True
# Il faut ajouter à L les nombres premier qu'il nous manque
if indice_premier >= len(L):
L.append(premier_suivant_opti(L[-1], L))
return est_premier_opti(n, L,indice_premier)
def premier_suivant_opti(n, L, indice_premier=0):
""" Renvoie le plus petit nombre premier strictement supérieur à n
à partir de L[indice_premier] en utilisant la fonction 'est_premier_opti.
"""
if est_premier_opti(L[indice_premier],L, indice_premier):
if n < L[indice_premier]:
return(L[indice_premier])
else:
return(premier_suivant_opti(n,L,indice_premier+1))
P = [2] # liste des nombres premiers connus initialement
print(est_premier_opti(11, P))
print(est_premier_opti(64231, P))
print(not est_premier_opti(64233, P))
print(premier_suivant_opti(15, P)==17)
print(permier_suivant_opti(11, P)==13)
print(premier_suivant_opti(0, P)==2)
print(P) # liste des nombres premiers connus en fin de calcul
Proposer une fonction decomposition_opti qui ne calcule pas plusieurs fois la primalité d'un même entier et qui ne calculerait qu'une fois chaque décomposition si l'utilisateur décompose plusieurs nombres.
def decomposition_opti(n, L, mem): # déterminer le type du paramètre `mem`
"""Renvoie une liste décrivant la décomposition en facteurs premiers de
`n`. La fonction doit stocker dans `L` les nombres premiers déjà vus,
et dans `mem` les décompositions déjà traitées.
"""
...
mem = ... # état initial de la structure de données auxiliaire
for n in range(100):
print(chaine_decomp(decomposition_opti(n, L, mem)))
print(mem) # état après calculs
(Bonus) Pour se convaincre de l'efficacité de nos optimisations, nous allons comparer le nombre d'opérations (par exemple de divisions et calculs de reste) effectuées au total par le dernier test effectué ci-dessus. Modifiez l'ensemble des fonctions précédentes afin d'effectuer ce comptage, et comparez les résultats obtenus.