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
N = 13
LMM = [random.randint(0, 100) for _ in range(N)]
print(LMM)
# Application
- 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)
def MinMax(LLt):
# Solution
- 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
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
# Application
- 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
# 2.
def NSP(n):
# Solution
- 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
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
# 2.
def prod_shift_Rec(N,M):
# Solution
# 3.
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
def COMD(D1 , D2):
# solution
def DIFFED(D1 , D2):
# solution
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
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
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
- 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):
# Solutiuon
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
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
- 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
def ExpR(x,n):
# solution
# Compaison des temps d'execution
- 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
# Exemple
nb = 8
ch = RepBinNb(n)
print ( f"La representation binaire de {nb} est : {ch}" )