DS2- 2ème Trimestre
LYCEE LISSANE EDDINE BEN AL KHATIB Filière: MPSI
CPGE-LAAYOUNE
2013/2014 Matière : Informatique
Durée : 2H
Exercice 1:
1). Il s'agit d'écrire une fonction impairs(a, b) qui retourne la liste de tous les nombres impairs se
trouvant entre deux entiers a et b, inclus.
Exemple :
Pour a=10 et b=15 la fonction retournera la liste [11, 13, 15]
Proposez deux solutions :
a- En utilisant la méthode append
b- Construire la liste par compréhension avec la structure [f(k) for k in ..]
2). Écrire une fonction pdt_scal(U, V) qui prend 2 listes de même longueur en argument et
retournera leur produit scalaire.
3). Écrire une fonction miroir (T) qui permet d’inverser les éléments du tableau T (sans utiliser
la méthode reverse). Par exemple : [2, 1, 4, 3] deviendra [3, 4, 1, 2].
4). Écrire une fonction positions(x, T) qui retourne la liste des positions du nombre x dans T.
5). Adapter la fonction tri_selection(T) pour trier un tableau de nombres en ordre décroissant.
Exercice 2:
Dans cet exercice, nous allons représenter des ensembles finis d’entiers par une liste dont les
éléments sont des nombres entiers triés par ordre croissant et tous différents (sans doublons).
Exemple : l’ensemble E={-2, 1, 4, 13} sera représenté par la liste : E=[-2, 1, 4, 13]
Écrire les fonctions suivantes :
a. appartient(x, E) qui retourne True si x est dans E et False sinon. On utilisera
l’algorithme de recherche dichotomique.
Exemple :
Si E={-2, 1, 4, 13} et x=4 alors la fonction retournera True
Si E={-2, 1, 4, 13} et x=0 alors la fonction retournera False
b. inclus(E1, E2) qui retourne True si E1 est inclus dans E2 (i.e : tous les éléments de E1
appartiennent à E2) et False sinon ;
Exemple :
Si E1={0, 1, 4} et E2={-2, 1, 4, 13} alors la fonction retournera False
Si E1={ -2, 4} et E2={-2, 1, 4, 13} alors la fonction retournera True
c. intersection(E1, E2) qui retourne une liste contenant les éléments communs à E1 et E2.
La fonction retournera la liste vide [ ] si E1E2=
Exemple : Si E1={0, 1, 4} et E2={-2, 1, 4, 13} alors la fonction retournera [1, 4]
d. union(E1, E2) qui retourne la liste représentant E1 E2.
Exemple : Si E1={0, 4, 25} et E2={-2, 1, 4, 13} alors la fonction retournera [-2, 0, 1, 4, 13, 25]
Pr. Mohamed EL-KHLIFI 1/2
Exercice 3: Evaluation de polynômes
On représente un polynôme P(x)=a0+a1x+...+anxnde degré n à l’aide d’une liste P= [a0, a1, ..., an] de taille n+1.
1) Écrire une fonction puiss(x, n) calculant xn par multiplications successives (xn =x*x*…*x , n fois)
2) Écrire une fonction evalPolynome(P, x) qui fait appel à la fonction puiss de la question
précédente pour calculer la valeur d’un polynôme de degré n en un point donné x.
3) Pour optimiser le calcul, on applique la méthode de Horner qui consiste à effectuer le calcul
suivant : P(x)=a0+x[a1+x(a2+...+x(an-1+anx)...))]
a) Par exemple, si P(x) = 3 + 2x – 3x2 + x3 – 5x4, alors :
P(x) = 3 + x [2 + x (-3 + x(1 - 5x))]
Compléter les instructions suivantes pour que res contienne à la fin la valeur de P(x).
res = -5
res = .........
res = .........
res = .........
res = .........
(Chaque ligne ne devra contenir qu'une seule multiplication).
b) En s'appuyant sur les observations précédentes écrire une fonction evalHorner(P, x) qui
permet d’évaluer un polynôme suivant la méthode de Horner.
Exercice 4:
Écrire une fonction transposee(M) qui retourne la matrice transposée de la matrice M.
Rappel:
1 5 9
1 2 3 4
2 6 10
A = 5 6 7 8 A =
T
9 10 11 12 3 7 11
4 8 12
Bon travail !
Pr. Mohamed EL-KHLIFI 2/2