Animé par : Dr. Guelzim Ibrahim
Exercice 1 :
- Question 0 :
écrire une fonction qui prend en paramètres une liste d'entiers et qui retourne le min et le max de la liste (sans faire recours aux fonctions min et max)
def MinMaxL(Lmm):
# solution
if not Lmm:
raise ValueError("La liste ne doit pas être vide.")
min_val = Lmm[0]
max_val = Lmm[0]
for x in Lmm[1:]:
if x < min_val:
min_val = x
elif x > max_val:
max_val = x
return min_val, max_val
import random
N = 13
LMM = [random.randint(0, 100) for _ in range(N)]
print(LMM)
[78, 42, 55, 5, 100, 26, 9, 50, 97, 34, 54, 6, 11]
# Application
print("Résultat (min, max) :", MinMaxL(LMM))
Résultat (min, max) : (5, 100)
- Question 1 :
écrire une fonction qui calcule le maximum de chaque ligne d'une liste de listes, et qui retourne le minimum de tous ces maxima.
N.B. (Sans faire recours aux fonctions min et max)
import random
n_listes = 5 # nombre de sous-listes
taille_liste = 4 # nombre d’éléments par sous-liste
min_val, max_val = 0, 100 # bornes des entiers
# Génération
LL = [[random.randint(min_val, max_val) for _ in range(taille_liste)] for _ in range(n_listes)]
print(LL)
[[95, 15, 89, 76], [44, 51, 15, 31], [45, 87, 19, 17], [94, 15, 8, 34], [71, 80, 59, 18]]
def MinMax(LLt):
if not LLt:
raise ValueError("La liste principale ne doit pas être vide.")
max_list = []
for ligne in LLt:
if not ligne:
raise ValueError("Chaque sous-liste doit contenir au moins un élément.")
max_val = ligne[0]
for x in ligne[1:]:
if x > max_val:
max_val = x
max_list.append(max_val)
min_val = max_list[0]
for val in max_list[1:]:
if val < min_val:
min_val = val
return min_val
print("Le minimum de tous ces maximum est :",MinMax(LL))
Le minimum de tous ces maximum est : 51
- Question 2 :
Ecrire une fonction qui prend en paramètres 4 entiers a, b, c, et d et qui retourne 1 si les intervalles [a,b] et [c,d] se chevauchent et 0 sinon
N.B. On suppose que a < b et c < d
def chevauchement(a, b, c, d):
if b < c or d < a:
return 0
else:
return 1
a=1
b=5
c=4
d=8
print(chevauchement(a, b, c, d))
1
Exercice 2 : (nombres : parfaits, super-parfaits , amicaux)
- Question 1 :
Un nombre parfait est un entier positif supérieur à 1, égal à la somme de ses diviseurs ;
On compte 1 comme diviseur, mais on ne compte pas le nombre lui-même comme diviseur.
Exemple : 6 est un nombre parfait puisque : 6 = 3 + 2 + 1.
Ecrire une fonction nbr_parfait qui prend comme paramètre un nombre entier n et retourne 1 si n est un entier parfait et 0 sinon.
def nbr_parfait(n):
# Solution
if n <= 1:
return 0
somme = 0
for i in range(1, n):
if n % i == 0:
somme += i
if somme == n:
return 1
else:
return 0
# Application
n = 6
print(nbr_parfait(n))
1
- Question 2 :
Un nombre super-parfait est un entier positif qui vérifie l’égalité suivante : σ2(n) = σ(σ(n)) = 2n Où σ(n) est la fonction de la somme des diviseurs de n, y compris 1 et n. Exemple : σ(6) = 1 + 2 + 3 + 6 = 12 1. Ecrire une fonction sigma qui prend en paramètre un entier strictement positif n et qui retourne σ(n) 2. Ecrire une fonction NSP qui prend en paramètre un entier strictement positif n et qui retourne 1 si le nombre n est super-parfait et 0 sinon. Ex : 5 n’est pas super-parfait car σ(5) = 6 et σ2(5) = σ(6) = 12 ≠ 2*5
# 1.
def sigma(n):
# Solution
if n <= 0:
raise ValueError("n doit être strictement positif")
somme = 0
for i in range(1, n + 1):
if n % i == 0:
somme += i
return somme
# 2.
def NSP(n):
# Solution
if n <= 0:
raise ValueError("n doit être strictement positif")
if sigma(sigma(n)) == 2 * n:
return 1
else:
return 0
print("La somme sigma est :",sigma(n))
print("n est super-parfait ?",NSP(n))
La somme sigma est : 12 n est super-parfait ? 0
- Question 3 : (Nombres amicaux)
Deux nombres (entiers strictement positifs) sont dits amicaux s'ils sont distincts et si chacun des deux nombres est égal à la somme des diviseurs stricts de l'autre.
Rappelons qu’un diviseur strict d’un nombre k est un nombre entier naturel, diviseur de k et distinct de k.
Exemple: 1184 et 1210 sont amicaux car :
• Les diviseurs stricts de 1184 sont : 1, 2, 4, 8, 16, 32, 37, 74, 148, 296 et 592 et leur somme est : 1 + 2 + 4 + 8 + 16 + 32 + 37 + 74 + 148 + 296 + 592 = 1210
• Les diviseurs stricts de 1210 sont : 1, 2, 5, 10, 11, 22, 55, 110, 121, 242 et 605 et leur somme est : 1 + 2 + 5 + 10 + 11 + 22 + 55 + 110 + 121 + 242 + 605 = 1184
Ecrire une fonction nbr_amicaux( ) qui prend en paramètres deux entiers naturels m et n et retourne :
* 1 si les entiers m et n sont amicaux
* 0 sinon
def somme_diviseurs_stricts(n):
if n <= 0:
raise ValueError("n doit être strictement positif")
somme = 0
for i in range(1, n):
if n % i == 0:
somme += i
return somme
def nbr_amicaux(m, n):
if m <= 0 or n <= 0:
raise ValueError("m et n doivent être strictement positifs")
if m == n:
return 0
if somme_diviseurs_stricts(m) == n and somme_diviseurs_stricts(n) == m:
return 1
else:
return 0
a = 1184
b = 1210
print(nbr_amicaux(a, b))
1
Exercice 4 : (Multiplication par SHIFTs de 2 naturels)
Voici un algorithme qui réalise l'exploit de multiplier 2 nombres entiers N et M en n'utilisant que des multiplications/divisions par 2 selon la conception suivante : A chaque étape, N est divisé par 2 (division entière) et M est multiplié par 2. Si N est impair, la valeur de M est ajoutée au futur résultat. Si N est strictement positif, on s’arrête à N = 1. Exemple: 321 * 457 N M 321 457 N est impair donc futur résultat=457 160 914 N est pair donc on n'ajoute pas 914 80 1828 N est pair donc on n'ajoute pas 1828 40 3656 N est pair donc on n'ajoute pas 3656 20 7312 N est pair donc on n'ajoute pas 7312 10 14624 N est pair donc on n'ajoute pas 14624 5 29248 N est impair donc futur résultat=457+29248=29705 2 58496 N est pair donc on n'ajoute pas 58496 1 116992 N est impair donc résultat=29705+116992=146697 1. Ecrire une fonction itérative prod_shift_iter qui prend en paramètres deux entiers, respectivement, N et M et retourne leur produit 2. Ecrire un programme qui lit deux entiers positifs N et M puis, pour calculer leur produit, fait appel à la fonction itérative prod_shift_iter de sorte à ce que le nombre d’itérations soit minimal.
# 1.
def prod_shift_iter(N,M):
# Solution
produit = 0
while N > 0:
if N % 2 == 1:
produit += M
N = N // 2
M = M * 2
return produit
# 2.
def prod_shift_Rec(N,M):
# Solution
if N == 0:
return 0
if N % 2 == 1:
return M + prod_shift_Rec(N // 2, M * 2)
else:
return prod_shift_Rec(N // 2, M * 2)
# 3.
N, M = 321, 457
result_iter = prod_shift_iter(N, M)
result_rec = prod_shift_Rec(N, M)
# Affichage des résultats
print(f"\nRésultat avec version itérative : {result_iter}")
print(f"Résultat avec version récursive : {result_rec}")
Résultat avec version itérative : 146697 Résultat avec version récursive : 146697
Exercice 5 : date de naissance
1. Définir une fonction VDN(jj , mm , aa ) qui retourne la valeur vrai si la date saisie est juste, sinon elle retourne faux.
Le paramètre jj représente le jour, mm le mois et aaaa l’année.
NB. Nous supposons que le paramètre aa doit être supérieur ou égal à 1900.
2. On considère qu’une date est une chaine de 10 caractères formatée de la manière suivante : "jj/mm/aaaa" tels que jj,mm et aaaa représentent respectivement le jour, mois et l’année.
Ex : "29/02/2016"
Dans ce qui suit, toutes les dates sont supposées des dates valides.
Ecrire une fonction COMD(D1 , D2) qui prend en paramètre respectivement deux dates D1 et D2 et qui retourne :
* 1 si la date D1 est postérieure à la date D2
* 0 si la date D1 est égale à la date D2
* -1 si la date D1 est antérieure à la date D2
Exemples :
- COMD("01/03/2007","07/03/2005") retourne 1
- COMD("11/05/1997","07/03/2005") retourne -1
3. Ecrire une fonction DIFFED qui prend en paramètre deux dates D1 et D2 et qui retourne le nombre de jours entre les deux dates. On suppose que les deux dates sont dans la même année.
def VDN(jj , mm , aaaa ):
# Solution
if aaaa < 1900:
return False
if mm < 1 or mm > 12:
return False
if mm in [1, 3, 5, 7, 8, 10, 12]:
jours_mois = 31
elif mm in [4, 6, 9, 11]:
jours_mois = 30
elif mm == 2:
if (aaaa % 4 == 0 and aaaa % 100 != 0) or (aaaa % 400 == 0):
jours_mois = 29
else:
jours_mois = 28
else:
return False
if jj < 1 or jj > jours_mois:
return False
return True
print(VDN(29, 2, 2016), VDN(29, 2, 2015), VDN(31, 4, 2020))
True False False
def COMD(D1 , D2):
# solution
jj1, mm1, aa1 = map(int, D1.split("/"))
jj2, mm2, aa2 = map(int, D2.split("/"))
if aa1 > aa2:
return 1
elif aa1 < aa2:
return -1
else:
if mm1 > mm2:
return 1
elif mm1 < mm2:
return -1
else:
if jj1 > jj2:
return 1
elif jj1 < jj2:
return -1
else:
return 0
def DIFFED(D1 , D2):
# solution
jj1, mm1, aa1 = map(int, D1.split("/"))
jj2, mm2, aa2 = map(int, D2.split("/"))
if aa1 != aa2:
raise ValueError("Les deux dates doivent être dans la même année.")
jours_mois = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
if (aa1 % 4 == 0 and aa1 % 100 != 0) or (aa1 % 400 == 0):
jours_mois[1] = 29
jour_annee1 = sum(jours_mois[:mm1 - 1]) + jj1
jour_annee2 = sum(jours_mois[:mm2 - 1]) + jj2
return abs(jour_annee1 - jour_annee2)
print(COMD("01/03/2007", "07/03/2005"), COMD("11/05/1997", "07/03/2005"))
print(DIFFED("01/01/2024", "01/03/2024"))
1 -1 60
Exercice 5 : Occurrence maximale
On considère une liste T d’entiers positifs ordonnées dans un ordre décroissant. La liste T est de taille N. Ecrire une fonction qui qui prend en paramètres T et N et qui retourne la valeur de la liste qui y figure le plus grand nombre de fois. Par exemple dans le tableau ci-dessous, la valeur qui y figure le plus est 7 (4 fois) 10 7 7 7 7 5 5 2 2 2 1 N.B. Au cas d’égalité, nous gardons la première valeur. Ex : dans ce cas nous gardons la valeur 9 (avec deux apparences) 10 9 9 7 7 5 5 2 2 1 1
def OccurrenceMax(T, N):
if N == 0:
return None
val_max = T[0]
occ_max = 1
val_cour = T[0]
occ_cour = 1
for i in range(1, N):
if T[i] == val_cour:
occ_cour += 1
else:
if occ_cour > occ_max:
occ_max = occ_cour
val_max = val_cour
val_cour = T[i]
occ_cour = 1
if occ_cour > occ_max:
occ_max = occ_cour
val_max = val_cour
return val_max
T1 = [10, 7, 7, 7, 7, 5, 5, 2, 2, 2, 1]
T2 = [10, 9, 9, 7, 7, 5, 5, 2, 2, 1, 1]
print(OccurrenceMax(T1, len(T1)))
print(OccurrenceMax(T2, len(T2)))
7 9
Exercice 6 :
- Question 1 :
Écrire une fonction récursive OccR qui retourne le nombre d'occurrence d'un caractère c dans une chaine ch
def OccR(ch , c):
# Solution
if ch == "":
return 0
if ch[0] == c:
count=1 + OccR(ch[1:], c)
return count
else:
return OccR(ch[1:], c)
c='c'
ch="choubikc"
print(OccR(ch,c))
2
Faire la même question pour le nombre d'occurrence d'un chiffre dans un nombre
Exemple:
si N = 43128309 et chif = 3, alors la fonction NbCR doit retourner 2
def NbCR(N, chif):
# Solution
if N == 0:
return 0
if N % 10 == chif:
return 1 + NbCR(N // 10, chif)
else:
return NbCR(N // 10, chif)
N=43128309
chif=3
print(NbCR(N,chif))
2
- Question 2 :
Écrire une fonction récursive prod_shift_rec qui fournit le même résultat que prod_shift_iter vue à l'Exercice 3 (Multiplication par SHIFTs de 2 naturels)
def prod_shift_rec(m , n):
# Solution
if m == 0:
return 0
if m % 2 == 1:
return n + prod_shift_rec(m // 2, n * 2)
else:
return prod_shift_rec(m // 2, n * 2)
m, n = 5, 6
resultat = prod_shift_rec(m, n)
print(f"Le produit de {m} et {n} est : {resultat}")
Le produit de 5 et 6 est : 30
Exercice 7 :
Écrire une fonction récursive MaxRec qui s'inspire de la recherche dichotomique et retourne le max d'une liste
def MaxRec(L):
# Solution
if len(L) == 1:
return L[0]
mid = len(L) // 2
a = L[:mid]
b = L[mid:]
max_a = MaxRec(a)
max_b = MaxRec(b)
return max_a if max_a > max_b else max_b
import random
L = [random.randint(0, 100) for _ in range(10)]
print("Liste :", L)
maximum = MaxRec(L)
print("Le maximum de la liste est :", maximum)
Liste : [77, 46, 25, 90, 93, 86, 59, 34, 34, 37] Le maximum de la liste est : 93
Exercice 8 :
- Question 0 :
Ecrire une fonction récursive Multi_13( ) qui prend en paramètre un nombre n entier positif et retourne vrai si n est multiple de 13 et faux sinon, (sans utiliser l’opérateur %).
def Multi_13(n):
# solution
if n == 0:
return True
if n<13:
return False
return Multi_13(n - 13)
print(Multi_13(258))
False
- Question 1 : (exponentiation rapide)
• Écrire une fonction récursive qui calcule xn pour x réel et n entier naturel en utilisant : xn = x.xn-1
• Refaire la même question en utilisant
o xn = xn/2.xn/2 pour n pair
o xn = x.xn/2.xn/2 pour n impair
• Calculer le temps d'execution des deux méthodes pour des valeurs assez grandes de n
def Exp(x,n):
# solution
if n == 0:
return 1
else:
return x * Exp(x, n - 1)
def ExpR(x,n):
# solution
if n == 0:
return 1
elif n % 2 == 0:
demi = ExpR(x, n // 2)
return demi * demi
else:
demi = ExpR(x, n // 2)
return x * demi * demi
# Comparaison des temps d'execution
import time
x = 1.0001
n = 900 # Exp est récursive : au-delà de ~1000 Python lève RecursionError
repetitions = 1000
t1 = time.perf_counter()
for _ in range(repetitions):
Exp(x, n)
temps_simple = time.perf_counter() - t1
t2 = time.perf_counter()
for _ in range(repetitions):
ExpR(x, n)
temps_rapide = time.perf_counter() - t2
print(f"Temps version simple : {temps_simple:.4f} s")
print(f"Temps version rapide : {temps_rapide:.4f} s")
Temps version simple : 0.2041 s Temps version rapide : 0.0020 s
- Question 2 : (Conversion Décimal -> Binaire)
Écrire une fonction récursive qui retourne une chaine de caractère contenant la représentation binaire d'un nombre entier positif.
def RepBinNb(n):
# solution
if n < 2:
return str(n)
else:
# Division entière par 2 et ajout du reste (n % 2)
return RepBinNb(n // 2) + str(n % 2)
# Exemple
nb = 8
ch = RepBinNb(nb)
print ( f"La representation binaire de {nb} est : {ch}" )
La representation binaire de 8 est : 1000