[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 gales 0

37forj i nr ange(i+1,m ):

38C[j] = C[j]-C[i]*(C[j, i]/C[i, i])

39

40#r etournerl en ombred "échange

41returnk 1. d-Ecrire la fonctiondeteminant(G), qui reçoit en paramètre une matrice G qui représente

une grille binaire carrée. En utilisant la méthode du pivot de Gauss, la fonction renvoie la valeur du

déterminant de G,Mr. ESSADDOUKI Mostafa4 https://www.developpement-informatique.com Algorithmique et programmation Problèmes et concours

1defd eteminant(G):

2#C réeru nec opied eG

3C = copie_matrice(G)

4

5#R endreC t riangulaires upérieure

6k = triangulaire(C)

7

8#S il am atricee stn oni nversible

9ifk = =- 1:

10returnN one

11#S inon

12

13#L ed éterminantd el am atricet riangulairee stl ep roduitd "éléments

diagonaux

14diag = 1

15fori i nr ange(len(C)):

16diag *= C[i, i]

17

18#l ed éterminantd el am atricee stl ed éterminantd el am atrice

triangulaire

19#m ultipliép ar( -1)p uissance( nombred "échanged el ignes)

20d = diag*(-1)**(k)

21returnd

Tester la fonction

1G = array([[1, 1, 1, 1, 0, 0, 1, 1, 1, 1], [1, 1, 1, 0, 0, 1, 1, 0, 1,

1], [1, 1, 0, 0, 1, 1, 0, 0, 1, 1], [1, 1, 1, 0, 0, 0, 0, 1, 1, 1],

[1, 0, 1, 1, 1, 0, 1, 1, 1, 1], [1, 0, 0, 1, 1, 1, 0, 1, 1, 0], [1, 1,

0, 1, 1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1, 1, 0, 0, 1], [1, 0, 0, 0,

1, 1, 1, 0, 1, 1],

2[1, 1, 1, 0, 0, 1, 1, 1, 1, 1]],f loat)

3

4print(deteminant(G))

5#r ésultat= - 4II. 2- Représentation de la grille binaire par une liste de listes

La grille binaire de la figure 1 est représentée par la liste G suivante, composée de 10 listes, de taille 12

chacune :

1G =[ [1,1,1,1,0,0,1,1,1,1,1,1] ,[1,1,1,0,0,1,1,0,1,1,1,1] ,

[1,1,0,0,1,1,0,0,1,1,1,1] ,[1,1,1,0,0,0,0,1,1,1,1,1] , [1,0,1,1,1,0,1,1,1,1,1,1] ,[1,0,0,1,1,1,0,1,1,0,0,0] , [1,1,0,1,1,1,0,0,0,0,1,0] ,[1,0,1,0,0,1,1,0,0,1,1,1] , [1,0,0,0,1,1,1,0,1,1,1,1] ,[1,1,1,0,0,1,1,1,1,1,1,1] 2]

-2-à partir de la liste G, de l"exemple ci-dessus, donner le résultat de chacune des expressions sui-

vantes : G[4][2] , len(G[3]) , G[5] , len(G)Mr. ESSADDOUKI Mostafa5 https://www.developpement-informatique.com

Algorithmique et programmation Problèmes et concours

G[4][2] = > 1

len(G[3]) => 12 : nombre de colonnes de la matrice G[5] = > [1,0,0,1,1,1,0,1,1,0,0,0] : ligne 6 de la matrice len(G) => 10 : nombre de lignes de la matriceII. 3- Position valide d"une case

3-Ecrire la fonctionvalide(i,j,G), qui reçoit en paramètres deux entiers i et j. La fonction renvoie

True, si i et j sont positifs, et s"ils représentent, respectivement la ligne et la colonne d"une case qui

existe dans la grille binaire G, sinon, la fonction renvoie False.1defv alide(t,G ):

2#t e stu nt uple, l ep remieré lémentf aitr éférenceà

3#l al ignee tl ed euxièmeé lémentà l ac olonne

4#i e stl al igne, j e tl ac olonne

5i, j = t

6

7#V érifiezs ii e stc omprise ntre0 e tl en ombred el ignesd ansG ,

8#e tj e stc omprise ntre0 e tl en ombred ec olonnesd ansG

9if( 0< =i < l en(G))a nd( 0< =j < l en(G[0])):

10returnT rue

11

12returnF alseII. 4- Couleur d"une case

4-Ecrire la fonctioncouleur(t,G), qui reçoit en paramètres un tupletqui représente une case dans

la grille binaire G. La fonction renvoie 1 si la couleur de la case t est blanche, sinon, elle renvoie 0.1defc ouleur(t,G ):

2#t e stu nt uple, l ep remieré lémentf aitr éférenceà

3#l al ignee tl ed euxièmeé lémentà l ac olonne

4#i e stl al igne, j e tl ac olonne

5i, j = t

6

7#s il ec ase stv alide, r envoyezl av aleurs tockée,

8ifv alide(t,G ):

9returnG [i][j]

10

11#r envoie- 1s ic en "estp asu nec asev alide

12return- 1II. 5- Cases voisines

Dans une grille binaire, deux cases sont voisines, si elles ont la même couleur et si elles ont un seul côté en

commun.

5-Ecrire la fonctionlist_voisines(t,G), qui reçoit en paramètres un tupletreprésentant une case

dans la grille binaire G. La fonction renvoie la liste des cases voisines à la case t, dans la grille G.Mr. ESSADDOUKI Mostafa6 https://www.developpement-informatique.com

Algorithmique et programmation Problèmes et concoursquotesdbs_dbs23.pdfusesText_29

[PDF] Correction CNC, partie informatique

[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