[PDF] Correction CNC 2019 - MP Correction CNC 2019 - MP. ESSADDOUKI

View - Download Correction CNC 2019 - MP

Previous PDF

Next PDF

Algorithmique et programmation Problèmes et concours

Correction CNC 2019 - MP

ESSADDOUKI Mostafa (essaddouki@gmail.com), WhatsApp (+212) 616 374 790

Exercice - Médian d"une liste de nombres

1.

Ecrir ela fonction grands(L,x)qui reçoit en paramètres une liste de nombreL, et un élémentxde

L. la fonction renvoie le nombre d"éléments de L qui sont supérieure strictement àx1defg rands(L,x ):

2#i nitialiserl ed écompte( nb)a vec0

3nb = 0

4#P uiso nc omparex à c haqueé lémentd ut ableau

5fori i nr ange(len(L)):

6#S iu né lémente sts upérieurà x ,i ncrémentezn bp ar1

7ifL [i]> x :

8nb += 1

9returnn b2.Déter minerla complexité de la fonction grands(L,x), et justifier votre réponse

la compléxité estO(n), parce que nous bouclons sur tous les éléments, et à l"intérieur de la boucle,

nous n"avons que des opérations élémentaires avec un coûtO(1) 3.

Ecrir ela fonction petits(L,x)qui reçoit en paramètres une liste de nombreL, et un élémentxde

L. la fonction renvoie le nombre d"éléments de L qui sont inférieurs strictement àx1defp etits(L,x ):

2#i nitialiserl ed écompte( nb)a vec0

3nb = 0

4#P uiso nc omparex à c haqueé lémentd ut ableau

5fori i nr ange(len(L)):

6#S iu né lémente sti nférieurà x ,i ncrémentezn bp ar1

7ifL [i]< x :

8nb += 1

9returnn bL est un une liste de taille n qui contient des nombres, et m un élément de L. L"élément m est un médian

de L, si les deux conditions suivantes sont vérifiées :

Le nom bred"élémen tsde L, qui son tsup érieursstrictemen tà m, e stinférieur ou égale à n/2

Le nom bred"élémen tsde L, qui son tinférieurs stric tementà m, est inférieur ou égale à n/2Mr. ESSADDOUKI Mostafa1 https://www.developpement-informatique.com

Algorithmique et programmation Problèmes et concours 4.

Ecrir ela fonction median(L)qui reçoit en paramètre une liste de nombres L non vide, et qui renvoie

un élément médian de la liste L.1defm edian(L):

2#T ailled el al iste

3n =l en(L)

4#N ousb ouclonss url et ableau, e tn ousp renonsc haqueé lémentc omme

candidat p our l a m diane

5fori i nr ange(n):

6#L [i]e stu nc andidat

7gd = grands(L, L[i])

8pt = petits(L, L[i])

9

10#V érifiezs il ec andidatv érifiel esp ropriétés

11ifg d< =( n//2)a nd( pt< =n //2):

12#r etournerl am édiane

13returnL [i]5.Déter minerla complexité de la fonction median(L), et justifier votre réponse.

O(n2), parce que nous bouclons sur tous les éléments, et à l"intérieur de la boucle, nous appelons les

fonctions "grands" et "petits" et ces fonctions ont un coût O (n) chacune

Partie II :

II. 1- Calcul du déterminant d"une grille binaire carrée

Dans le but de calculer le déterminant d"une matrice carrée G qui représente une grille binaire carrée, on

propose d"utiliser la méthode dupivot de Gauss, dont le principe est le suivant :

C réerune matrice C copie de la matrice G ;

En utilisan tla métho dedu piv otde Gauss, transformer la matrice C e nmatrice triangulaire inférieure,

ou bien en matrice triangulaire supérieure, en comptant le nombre d"échanges de lignes dans la matrice

C. On pose k le nombre d"échanges de lignes dans la matrice C; C alculerle déterminan tD de la matrice triangulaire C ; Le déterminan tde la matric eM est égal à : D?(-1)k

1. a-Ecrire la fonctioncopie_matrice(G), qui reçoit en paramètre une matrice carrée G qui

représente une grille binaire carrée, et qui renvoie une matrice C copie de la matrice G.Mr. ESSADDOUKI Mostafa2 https://www.developpement-informatique.com

Algorithmique et programmation Problèmes et concours

1defc opie_matrice(G):

2#m e tn s ontr espectivementl en ombred el ignese td ec olonnesd el a

matrice G

3m, n =l en(G),l en(G[0])

4#C réezu nem atriceC d em êmet ailleq ueG q uin ec ontientq ued esz é

ros

5C = zeros((m, n))

6#p ourc haquel igne,

7fori i nr ange(m):

8#p ourc haquec olonne

9forj i nr ange(n):

10C[i, j] = G[i, j]

11

12#r etournerl ac opieC d eG

13returnC 1. b-Ecrire la fonctionechange_lignes(C,i,j), qui reçoit en paramètres une matrice carrée C qui

représente une grille binaire carrée. La fonction échange les lignes i et j dans la matrice C.1defe change_lignes(C,i ,j ):

2#l en ombred ec olonnes

3n =l en(C[i])

4

5#b ouclers url en ombred ec olonnes

6fork i nr ange(n):

7#é changerl "élémentd ansl ac olonnek d el al ignei a vec

8#l "élémentd ansl am êmec olonnem aisd ansl al ignej

9C[i, k], C[j, k] = C[j, k], C[i, k]1. c-Ecrire la fonctiontriangulaire(C), qui reçoit en paramètre une matrice carrée C qui représente

une grille binaire carrée. En utilisant la méthode du Pivot de Gauss, la fonction transforme la matrice

C en matrice triangulaire inférieure ou bien triangulaire supérieure, tout en comptant le nombre de

fois qu"il y a eu échange de lignes dans la matrice C. La fonction doit retourner le nombre d"échanges

de lignes.Mr. ESSADDOUKI Mostafa3 https://www.developpement-informatique.com Algorithmique et programmation Problèmes et concours

1#C ettef onctionc herched ansl esé lémentsC (k+1,k),C (k+2,k). .C (m,k)

2#l ep remierp ivotn onn ule tq uir envoiel "indiced el al igne

correspondante

3#S inonr envoie- 1d oncl am atricee stn oni nversible

4defc hoix_pivot(C,k ):

5m =l en(C)

6fori i nr ange(k+1,m ):

7ifC [i,k ]! =0 :

8returni

9return- 1

10 11

12deft riangulaire(C):

13#N ombred el ignes

14m =l en(C)

15

16#C ompterl en ombred "échange

17k = 0

18

19#b ouclers url esl ignes( chaquel ignec ontientu np ivot)

20fori i nr ange(m):

21#S il ep ivotd el al ignei c ontient0

22ifC [i][i]= =0 :

23#C hercheru np ivotd ansl esl igness ousl al ignei

24pivot = choix_pivot(C, i)

25#S il am atricee stn oni nversible( aucunp ivott rouvé)

26ifp ivot= =- 1:

27return( -1)

28

29#é changerl al ignei a vecl al igned up ivot

30echange_lignes(C, i, pivot)

31

32#I ncrémenterl en ombred "échange

33k += 1

34#p ourc haquel ignej s ousl al ignei ,r éaliserl "opérationL :

Ligne

35#L (j)=L(j)-L(i)*(L(j,k)/L(i,i))

36#p ourq uel esl igness ousl al ignep ivot( mêmesc olonnesq uel e

pivot s oient galesquotesdbs_dbs2.pdfusesText_2

[PDF] CONCOURS DE L 'INTERNAT EN PHARMACIE - CNCI

[PDF] Le Directeur Gnral

[PDF] Loi 09-08 - CNDP

[PDF] Conduite en douane des colis postaux L acheminement d

[PDF] Untitled - CNDP

[PDF] CNEC CNEC - Institut National Du Cancer

[PDF] français - Cned

[PDF] au service de toutes les reussites 2017 - Cned

[PDF] Calendrier_Etablissements ? l 'Etranger_2016-2017

[PDF] Livret de l étudiant du DECESF - Cned

[PDF] Calendrier des envois de devoirs

[PDF] master 2 sciences de l 'éducation ? distance international

[PDF] CNED : DAEU A - Université de Paris-Sud, Paris-11

[PDF] Direction - Cned

[PDF] L 'échographie de dépistage prénatal - Ordre des sages-femmes