Modèle de concours : CNC 2020 Informatique (MP) — Concours National Commun
En bref
Ce document est une ancienne épreuve écrite du concours de Concours d'accès aux écoles d'ingénieurs organisé par Concours National Commun (CNC) — CPGE (2020), publiée sur Wadifa Info en consultation et téléchargement PDF gratuits, avec une correction proposée.
- Organisme
- Concours National Commun (CNC) — CPGE
- Grade
- Concours d'accès aux écoles d'ingénieurs
- Spécialité
- Informatique
- Année
- 2020
- Pages
- 9
- Langue des questions
- français
- Correction
- correction proposée disponible sur cette page
📝 Texte des questions (extrait automatiquement des pages scannées)
Ce texte est extrait automatiquement des images de l'épreuve et peut contenir des erreurs de lecture — les images ci-dessus font foi.
— صفحة 1 —
Épreuve d’Informatique — Session 2020 - Filière MP
Les candidats sont informés que la précision des raisonnements algorithmiques ainsi que le soin apporté
à la rédaction et à la présentation des copies seront des éléments pris en compte dans la notation. ١
convient en particulier de rappeler avec précision les références des questions abordées. Si, au cours de
l'épreuve, un candidat repère ce qui peut lui sembler être une erreur d'énoncé, il le signale sur sa copie et
poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.
Remarques générales :
y Cette épreuve est composée d'un exercice et de trois parties toutes indépendantes ;
y Toutes les instructions et les fonctions demandées seront écrites en Python ;
y Les questions non traitées peuvent être admises pour aborder les questions ultérieures ;
y Toute fonction peut être décomposée, si nécessaire, en plusieurs fonctions.
ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند ند نداب
Exercice : (4 points)
Les coefficients binomiaux
Un coefficient binomial est défini pour deux entiers positifs n et k tels que nzk. C’est le nombre de
parties de k éléments dans un ensemble de n éléments. On le note : 9) , et sa valeur est calculée par la
formule suivante :
Écrire la fonction fact (p) qui reçoit en paramètre un entier positif p, et qui retourne la valeur de -01 م1
NB : La fonction fact(0) retourne 1
Q2- Écrire la fonction produit (n,k) qui reçoit en paramètres deux entiers positifs n et k tels que م1
nzk, et qui retourne la valeur du produit : n * (n—1) * (n-2) * … * (n- (k-1))
0.75pt Q3- Écrire la fonction binomial (n,k) qui reçoit en paramètres deux entiers positifs n et k tels que
næk, et qui retourne la valeur du coefficient binomial 0 8
Exemple : La fonction binomial (6, 3) retourne le nombre 20
1.25pt Q4- Écrire la fonction liste_binomiaux(n) qui reçoit en paramètre un entier positif n, et qui
retourne la liste des coefficients binomiaux 00 tel que :k = 0, 1, 2, 3, …, 1
Exemple : La fonction liste_binomiaux (6) retourne la liste [ 1, 6, 15, 20, 15, 6, 1 ]
Page 1 sur 9
نماذج المباريات من موقع وظيفة إنفو wadifa-info.com
— صفحة 2 —
Épreuve d’Informatique — Session 2020 - Filière MP
Partie I : Calcul numérique
Équation de la diffusion thermique
On considère une barre solide de longueur L, de coefficient de diffusion thermique D.
La barre est initialement "préparée" dans un état de température Tharre. Les deux extrémités de la barre
sont maintenues à une température extérieure constante Textr.
Barre de longueur L
x=0 x=L
U(t‹0, x) = Tbarre
x=0 x=L
L’équation de la diffusion thermique à une dimension, est la suivante :
ربا x ب سيت
Avec : U(x, t) est la température de la position x dans la barre, à un instant t.
L’équation (E) admet une solution unique :
2
+00
1 k
U(x,t) = Textr + c * 0 k (1 — cos(kT)) * sin ( 7
k=1
2
avec: c= = (Thbarre — Textr)
On suppose que les variables globales suivantes, sont déclarées et initialisées par les valeurs suivantes :
v L=1.0 Longueur de la barre
v D=0.2 Coefficient de diffusion thermique
v T=1.4 Durée totale de l’évolution de la température
v Tbarre=100.0 _ Température de la barre
y Textr=20.0 Température extérieure
Page 2 sur 9
نماذج المباريات من موقع وظيفة إنفو wadifa-info.com
— صفحة 3 —
Épreuve d’Informatique — Session 2020 — Filière MP
Dans cette partie, on suppose que les modules numpy et matplotlib.pyplot sont importés :
import numpy np
import matplotlib.pyplot as pl
Q.1- Écrire, en Python, la fonction f définie par :
Q.2- Écrire la fonction تآ (x, t) qui reçoit en paramètres deux réels x et £. La fonction retourne la valeur
de U(x, f) qui correspond à la somme partielle d'indice rm=200 :
2
U(x,t) = Textr + = (Tbarre — Textr) * › f(x,k,t)
k=1
Q.3- Écrire le programme permettant de tracer la représentation graphique suivante, qui représente
l'évolution de la température dans les points x de la barre, à intervalle de temps égal à 0.1s, sachant que
la barre est subdivisée en 100 points, et l'indice de la somme partielle est m=200.
8
20
0.2 0.4 0.6 0.8 10
NB : Chaque courbe représente la température à chaque point x de la barre à un instant £.
Page 3 sur 9
نماذج المباريات من موقع وظيفة إنفو wadifa-info.com
— صفحة 4 —
Épreuve d’Informatique — Session 2020 - Filière MP
Partie II : Base de donnés et langage SQL
Classement des candidats
Une grande école d'ingénieurs organise un concours au profit des étudiants (candidats), qui veulent y
accéder pour suivre leurs études supérieures. Le concours est composé de plusieurs épreuves : une
seule épreuve par matière.
Après le passage des épreuves, une note totale est calculée pour chaque candidat. Ensuite les candidats
sont classés dans l’ordre décroissant de la note totale.
NB : Une note inférieure strictement à 5.0 est une note éliminatoire du classement final. Si un candidat
possède au moins une note éliminatoire, alors ce candidat sera exclu du classement final.
L'école d'ingénieurs utilise une base de données relationnelle composée de trois tables :
Candidats Notes Matières
numéro (entier) numC (entier) code (texte)
nom (texte) codM (texte) nom (texte)
prénom — (texte) note (réel) coeff (entier)
La table ‘Candidats’ contient les numéros, les noms et les prénoms des candidats. Le champ numéro
est la clé primaire dans cette table.
Exemples :
numéro | nom | prénom
416 | Jarfaoui | Hicham
162 | Senhaji | Amal
23 | Bakouri_ | Ahmed
La table ‘Matières’ contient les codes, les noms et les coefficients correspondants à chaque matière. Le
champ code est la clé primaire dans cette table.
Exemples :
code | nom coeff
Mathématiques
si Sciences de l’ingénieur
Ch Chimie
Page 4 sur 9
نماذج المباريات من موقع وظيفة إنفو wadifa-info.com
— صفحة 5 —
Épreuve d’Informatique — Session 2020 — Filière MP
La table ‘Notes’ contient, pour chaque candidat, la note correspondante à chaque matière. Les champs
numC et codM sont deux clés étrangères, qui font respectivement référence, aux champs numéro et
code des tables ‘Candidats’ et ‘Matières’.
Exemples :
numCÇC | codM note
162
416
11,05
10,10
Q.1 - Déterminer la clé primaire de la table ‘Notes’, et justifier votre réponse.
Q.2 - Écrire, en algèbre relationnelle, une requête qui donne les numéros, les noms et prénoms de tous
les candidats, qui ne possèdent pas de note éliminatoire, en matière de code ‘M’.
Q.3 - Écrire la requête précédente (Q.2) en langage SQL.
Q.4 - Écrire, en langage SQL, une requête qui donne les noms des matières, la note maximale et la note
minimale de chaque matière, triés dans l'ordre décroissant de la moyenne des notes de chaque matière.
Q.5 - Écrire, en langage SQL, une requête qui donne le compte des candidats qui sont exclus du
classement final.
Q.6- Pour les candidats non exclus du classement final, la note totale de chaque candidat est calculée
par la formule suivante :
note totale = 2 (note * coefficient)
La note d'une matière est multipliée par le coefficient correspondant à cette matière.
Écrire, en langage SQL, une requête qui donne le numéro, le nom, le prénom et la note totale de chaque
candidat non exclu, ayant la note totale supérieure strictement à 1000.0, triés dans l’ordre décroissant de
la note totale.
Page 5 sur 9
نماذج المباريات من موقع وظيفة إنفو wadifa-info.com
— صفحة 6 —
Épreuve d’Informatique — Session 2020 — Filière MP
Partie IT : Problème
Carré magique
On considère un entier n strictement positif. Un carré magique d'ordre n est une matrice carrée d'ordre
n (n lignes et n colonnes), qui contient des nombres entiers strictement positifs. Ces nombres sont
disposés de sorte que les sommes sur chaque ligne, les sommes sur chaque colonne et les sommes sur
chaque diagonale principale soient égales. La valeur de ces sommes est appelée : constante magique.
Exemple :
Carré magique d'ordre 3, sa constante magique 45
Représentation d’une matrice carrée en Python :
Pour représenter une matrice carrée d'ordre n (n lignes et n colonnes), on utilise une liste qui contient n
listes, toutes de même longueur n.
Exemple :
10
13
نا جك ب
6 5
Cette matrice carrée d'ordre 4 est représentée par la liste M, composée de 4 listes de taille 4 chacune :
M[i] est la liste qui représente la ligne d'indice i dans M.
Exemples :
e Mf0]estlaliste [ 4,7,10,3]
٠ M{[2] est la liste [ 13, 0,5, 8[
M[i] [j] est l'élément à la i*”° ligne et la j*"° colonne, dans M
Exemples :
e M[0][1] est l'élément 7
e M[2][1] est l'élément O
Page 6 sur 9
نماذج المباريات من موقع وظيفة إنفو wadifa-info.com
— صفحة 7 —
Épreuve d’Informatique — Session 2020 — Filière MP
1.- Opérations sur une matrice carrée
Q.1- Écrire la fonction somme_ligne (M, i), qui reçoit en paramètres une matrice carrée M
contenant des nombres, et un entier i qui représente l'indice d’une ligne dans M. La fonction retourne la
somme des nombres de la ligne d’indice i dans M.
Exemple :
La fonction somme_ligne (M, 1) retourne la somme 3+2+9+6 = 20
Q.2- Écrire la fonction _somme_colonne (M, j), qui reçoit en paramètres une matrice carrée M
contenant des nombres, et un entier j qui représente l’indice d'une colonne dans M. La fonction retourne
la somme des éléments de la colonne d'indice j dans M.
Exemple :
La fonction somme_colonne (M, 0) retourne la somme 4+3+13+7 = 27
Q.3- Écrire la fonction somme_diag1 (M), qui reçoit en paramètre une matrice carrée M contenant
des nombres, et qui retourne la somme des éléments de la première diagonale principale dans M.
Exemple :
La fonction somme_diag1 (M) retourne la somme 4+2+5+25 = 36
Q.4- Écrire la fonction somme_diag2 (M), qui reçoit en paramètre une matrice carrée M contenant
des nombres, et qui retourne la somme des éléments de la deuxième diagonale principale dans M. (La
deuxième diagonale principale part du coin en haut à droite, jusqu’au coin en bas à gauche)
Exemple :
La fonction somme_diag2 (M) retourne la somme 3+9+0+7 = 19
II- Carré magique
Q.5- Écrire la fonction carre_magique (C), qui reçoit en paramètre une matrice carrée © contenant
des entiers strictement positifs, et qui retourne :
y True, si la matrice © est un carré magique : les sommes sur chaque ligne, sur chaque colonne et
sur chaque diagonale principale sont toutes égales
y False, sinon.
Exemples :
e 810001000 carre_magique (A) retourne True
e Lafonction carre_magique (B) retourne False
Page 7 sur 9
نماذج المباريات من موقع وظيفة إنفو wadifa-info.com
— صفحة 8 —
Épreuve d’Informatique — Session 2020 - Filière MP
111- Carré magique normal
Un carré magique normal d'ordre n est un carré magique d'ordre n, constitué de tous les nombres
entiers positifs compris entre 1 et n°.
Exemple :
Carrée magique normal d’ordre 4, composé des nombres entiers : 1, 2, 3, …, 15, 16.
NB : || n'existe pas de carré magique normal d’ordre 2.
Q.6.a- Écrire la fonction magique_normal (C), qui reçoit en paramètre une matrice carrée © qui
représente un carré magique. La fonction retourne True si le carré magique © est normal, sinon, elle
retourne False.
Exemples:
e La fonction magique _normal ([ [8, 1, 6] , [3, 5, 7] , [4, 9, 2] ]) retourne True
e La fonction magique _normal ([ [21, 7, 17] , [11, 15, 19] , [13, 23, 9] ]) retourne False
Q.6.b- Déterminer la complexité de la fonction magique_normal(C).
117 - Construction d’un carré magique normal d’ordre impair
La méthode siamoise est une méthode qui permet de construire un carré magique normal d’ordre n
impair.
Le principe de cette méthode est le suivant :
1. Créer une matrice carrée d'ordre n, remplie de 0
2. Placer le nombre 1 au milieu de la ligne d'indice 0.
3. Décaler d'une case vers la droite puis d'une case vers le haut pour placer le nombre 2, et faire de
même pour le nombre 3, puis le nombre 4, … jusqu'au nombre n°.
Le déplacement doit respecter les deux règles suivantes (voir l'exemple dans la page suivante) :
› Si la pointe de la flèche sort du carré, revenir de l'autre côté, comme si le carré était
enroulé sur un tore.
› Si la prochaine case est occupée par un entier non nul, alors il faut décaler d'une case vers
le bas.
Page 8sur 9
نماذج المباريات من موقع وظيفة إنفو wadifa-info.com
— صفحة 9 —
Epreuve d’Informatique — Session 2020 - Filière MP
Exemple :
Construction d’un carré magique normal d’ordre 5
ماما تا تاد
أند تق
ليد مدا امي
000
Q.7- Écrire la fonction matrice_nulle (ص) , qui reçoit en paramètre un entier n strictement positif, et
qui retourne une liste qui représente la matrice carrée d’ordre n, remplie de 0.
Exemple :
La fonction matrice_nulle (5) retourne la matrice suivante :
Q.8- Écrire la fonction siamoise (n), qui reçoit en paramètre un entier positif n impair. En utilisant le
principe de la méthode siamoise, la fonction retourne la matrice carrée qui représente le carré magique
normal d'ordre n.
Exemple :
La fonction siamoise (7) retourne la matrice carrée qui représente le carré magique normale d’ordre 7
suivant :
381477 د 18/2729
203
37
اتات ع ته تملا
امات 0352433
2 3ات4 ال 322 2023
Q.9- Écrire la fonction, de complexité constante, constante_magique (n), qui reçoit en paramètre
un entier positif n impair, et qui retourne la valeur de la constante magique du carré magique normal
d'ordre n.
Page 9 sur 9
نماذج المباريات من موقع وظيفة إنفو wadifa-info.com
✅ Correction proposée
Il s'agit d'une correction proposée, rédigée par l'équipe wadifa-info pour vous aider à comprendre la méthode — ce n'est pas un corrigé officiel de l'administration organisatrice.
Ce sujet est l'épreuve d'Informatique du Concours National Commun (CNC) 2020, filière MP, commun aux classes préparatoires marocaines pour l'accès aux écoles d'ingénieurs. Il compte 9 pages et se compose d'un exercice (4 points, coefficients binomiaux) et de trois parties indépendantes : calcul numérique (équation de la diffusion thermique, numpy et matplotlib), bases de données (algèbre relationnelle et SQL) et un problème d'algorithmique sur les carrés magiques. Tout le code est demandé en Python. C'est donc une épreuve de type problème / exercices de programmation. Voici une correction méthodologique proposée.
💡 Avant de commencer : les parties sont indépendantes et une question non traitée peut être admise, alors commencez par ce qui rapporte vite : l'exercice, les fonctions simples de la Partie III (sommes de ligne, de colonne et de diagonales) et le SQL. Réutilisez systématiquement les fonctions déjà écrites (binomial se sert de produit et de fact, carre_magique se sert des fonctions de somme) : c'est ce qu'attend le correcteur. Rappelez le numéro de chaque question et soignez l'indentation de votre code.
Exercice : les coefficients binomiaux (4 points)
Q1 : fact(p) (1 pt)
Il suffit d'un produit cumulé. La boucle est vide pour p = 0, donc fact(0) retourne bien 1.
def fact(p):
r = 1
for i in range(2, p + 1):
r = r * i
return r
Q2 : produit(n, k) (1 pt)
On calcule le produit des k facteurs n, n−1, …, n−(k−1), c'est-à-dire n−i pour i allant de 0 à k−1. Pour k = 0, le produit vide vaut 1.
def produit(n, k):
r = 1
for i in range(k):
r = r * (n - i)
return r
Q3 : binomial(n, k) (0,75 pt)
On applique la formule de l'énoncé : C(n, k) = n(n−1)…(n−k+1) / k!. La division est exacte, donc on utilise la division entière // pour renvoyer un entier (avec /, on obtiendrait le flottant 20.0).
def binomial(n, k):
return produit(n, k) // fact(k)
Vérification : binomial(6, 3) = (6×5×4) / 6 = 120 / 6 = 20.
Q4 : liste_binomiaux(n) (1,25 pt)
La version directe est [binomial(n, k) for k in range(n + 1)]. Elle est correcte mais coûte O(n²) multiplications. Une version plus efficace, en O(n), utilise la relation C(n, k+1) = C(n, k) × (n − k) / (k + 1), où la division est encore exacte :
def liste_binomiaux(n):
L = [1]
for k in range(n):
L.append(L[-1] * (n - k) // (k + 1))
return L
liste_binomiaux(6) retourne [1, 6, 15, 20, 15, 6, 1] (sortie vérifiée par exécution). Si vous citez la complexité, cela peut valoriser la copie.
Partie I : Calcul numérique (équation de la diffusion thermique)
Les données de l'énoncé sont L = 1.0, D = 0.2, T = 1.4, Tbarre = 100.0 et Textr = 20.0, toutes en variables globales. L'équation (E) s'écrit ∂U/∂t = D ∂²U/∂x². Sa solution est U(x, t) = Textr + c Σk≥1 (1/k)(1 − cos(kπ)) sin(kπx/L) e−(kπ/L)² D t, avec c = (2/π)(Tbarre − Textr).
Remarque : l'énoncé écrit « import numpy np ». Il manque le mot-clé as, et la bonne instruction est import numpy as np. On peut le signaler sur la copie, comme le prévoit le préambule.
Q.1 : fonction f
On traduit f(x, k, t) = (1/k)(1 − cos(kπ)) sin(kπx/L) e−(kπ/L)²·D·t :
def f(x, k, t):
a = k * np.pi / L
return (1 - np.cos(k * np.pi)) / k * np.sin(a * x) * np.exp(-a**2 * D * t)
Remarque utile : 1 − cos(kπ) = 1 − (−1)k. Ce terme vaut 0 pour k pair et 2 pour k impair, donc seuls les termes impairs contribuent.
Q.2 : fonction U(x, t) avec m = 200
On calcule la somme partielle d'indice m = 200, soit U(x, t) = Textr + (2/π)(Tbarre − Textr) Σk=1200 f(x, k, t) :
def U(x, t):
m = 200
s = 0
for k in range(1, m + 1):
s = s + f(x, k, t)
return Textr + 2 / np.pi * (Tbarre - Textr) * s
Comme f n'utilise que des fonctions numpy, U fonctionne aussi si x est un tableau numpy : le calcul se fait alors élément par élément.
Q.3 : tracé des courbes
La barre est discrétisée en 100 points entre 0 et L, et on trace une courbe tous les 0,1 s de t = 0 à t = T = 1,4 s, soit 15 courbes. La légende affiche « t = 0.0 s » … « t = 1.4 s ».
x = np.linspace(0, L, 100)
nb = round(T / 0.1) + 1 # 15 instants
for i in range(nb):
t = i * 0.1
pl.plot(x, U(x, t), 'k', label='t = %.1f s' % t)
pl.xlabel('x')
pl.ylabel('U(x,t)')
pl.grid()
pl.legend(loc='center left', bbox_to_anchor=(1, 0.5))
pl.show()
Points à soigner :
- on écrit round(T/0.1) et non int(T/0.1), parce que 1.4/0.1 vaut 13.999… en flottant et que int donnerait 13 ;
- à t = 0, la courbe vaut environ 100 à l'intérieur de la barre et tombe à 20 aux extrémités, avec de petites oscillations (phénomène de Gibbs, dû à la troncature de la série) ;
- quand t augmente, l'exponentielle e−(kπ/L)²Dt amortit d'abord les harmoniques élevés : les profils deviennent sinusoïdaux et tendent vers Textr = 20, comme sur la figure.
Partie II : Bases de données et SQL (classement des candidats)
Le schéma comporte trois tables : Candidats(numéro, nom, prénom), Matières(code, nom, coeff) et Notes(numC, codM, note), où numC fait référence à Candidats.numéro et codM à Matières.code. Une note strictement inférieure à 5.0 est éliminatoire.
Q.1 : clé primaire de Notes
La clé primaire est le couple (numC, codM). Aucun des deux champs ne suffit seul : un candidat a plusieurs notes (70 apparaît pour SI, M et P) et une matière a plusieurs notes (SI apparaît pour 70, 162 et 416). En revanche, le concours comporte une seule épreuve par matière, donc un candidat a au plus une note par matière : le couple identifie chaque ligne de façon unique et il est minimal.
Q.2 : algèbre relationnelle
On retire de l'ensemble des candidats ceux qui ont une note éliminatoire en M :
πnuméro, nom, prénom(Candidats) − πnuméro, nom, prénom(Candidats ⋈numéro = numC σcodM = 'M' ∧ note < 5(Notes))
Autre lecture acceptée : ne garder que les candidats qui ont une note en M et dont cette note est au moins 5, soit πnuméro, nom, prénom(Candidats ⋈numéro = numC σcodM = 'M' ∧ note ≥ 5(Notes)). Les deux requêtes ne diffèrent que pour un candidat sans note en M. Précisez sur votre copie celle que vous choisissez.
Q.3 : traduction en SQL
SELECT numéro, nom, prénom
FROM Candidats
WHERE numéro NOT IN (SELECT numC FROM Notes
WHERE codM = 'M' AND note < 5);
L'opérateur NOT IN correspond à la différence ensembliste, et le mot-clé EXCEPT est aussi possible avec SQLite.
Q.4 : note maximale et note minimale par matière
SELECT M.nom, MAX(N.note), MIN(N.note)
FROM Matières M JOIN Notes N ON M.code = N.codM
GROUP BY M.code, M.nom
ORDER BY AVG(N.note) DESC;
Le tri se fait sur la moyenne AVG, qui n'est pas affichée : c'est permis dans ORDER BY après un GROUP BY.
Q.5 : nombre de candidats exclus
Un candidat est exclu s'il a au moins une note < 5. Il faut compter les numéros distincts, car un candidat peut avoir plusieurs notes éliminatoires :
SELECT COUNT(DISTINCT numC) FROM Notes WHERE note < 5;
Q.6 : note totale des candidats non exclus supérieure à 1000
On fait la jointure des trois tables et on regroupe par candidat. Un candidat n'est pas exclu si et seulement si sa note minimale est ≥ 5, ce qui se filtre après regroupement :
SELECT C.numéro, C.nom, C.prénom, SUM(N.note * M.coeff) AS total
FROM Candidats C
JOIN Notes N ON C.numéro = N.numC
JOIN Matières M ON M.code = N.codM
GROUP BY C.numéro, C.nom, C.prénom
HAVING MIN(N.note) >= 5 AND SUM(N.note * M.coeff) > 1000.0
ORDER BY total DESC;
Variante équivalente : garder WHERE C.numéro NOT IN (SELECT numC FROM Notes WHERE note < 5) et mettre seulement la condition > 1000.0 dans HAVING. L'erreur classique serait d'écrire WHERE note >= 5 : on ne ferait qu'ignorer les mauvaises notes, sans exclure le candidat.
Partie III : Problème (carré magique)
La matrice d'exemple est M = [[4,7,10,3],[3,2,9,6],[13,0,5,8],[7,1,6,25]], et n = len(M) donne l'ordre de la matrice.
I. Q.1 à Q.4 : opérations sur une matrice carrée
def somme_ligne(M, i):
s = 0
for j in range(len(M)):
s = s + M[i][j]
return s
def somme_colonne(M, j):
s = 0
for i in range(len(M)):
s = s + M[i][j]
return s
def somme_diag1(M):
s = 0
for i in range(len(M)):
s = s + M[i][i]
return s
def somme_diag2(M):
n = len(M)
s = 0
for i in range(n):
s = s + M[i][n - 1 - i]
return s
Contrôles sur M : somme_ligne(M, 1) = 3+2+9+6 = 20 ; somme_colonne(M, 0) = 4+3+13+7 = 27 ; somme_diag1(M) = 4+2+5+25 = 36 ; somme_diag2(M) = M[0][3]+M[1][2]+M[2][1]+M[3][0] = 3+9+0+7 = 19. Pour la deuxième diagonale, l'indice de colonne vaut n−1−i. Chaque fonction est en O(n).
II. Q.5 : carre_magique(C)
On prend comme référence la somme de la première diagonale, puis on compare toutes les autres sommes à cette valeur. La fonction s'arrête dès qu'une somme diffère.
def carre_magique(C):
n = len(C)
s = somme_diag1(C)
if somme_diag2(C) != s:
return False
for k in range(n):
if somme_ligne(C, k) != s or somme_colonne(C, k) != s:
return False
return True
Pour A = [[21,7,17],[11,15,19],[13,23,9]], toutes les sommes valent 45 : la fonction retourne True. Pour B = [[7,1,6],[1,15,9],[3,2,4]], la première diagonale donne 7+15+4 = 26 et la seconde 6+15+3 = 24 : elle retourne False. La complexité est O(n²).
III. Q.6.a : magique_normal(C)
C est déjà un carré magique d'ordre n. Il est normal si ses n² cases contiennent exactement les entiers 1, 2, …, n². Comme il y a n² cases, il suffit que chaque valeur soit comprise entre 1 et n² et qu'aucune valeur ne se répète. On utilise un tableau de booléens :
def magique_normal(C):
n = len(C)
vu = [False] * (n * n + 1)
for i in range(n):
for j in range(n):
v = C[i][j]
if v < 1 or v > n * n or vu[v]:
return False
vu[v] = True
return True
[[8,1,6],[3,5,7],[4,9,2]] contient exactement 1…9 : la fonction retourne True. [[21,7,17],[11,15,19],[13,23,9]] contient 21 > 9 : elle retourne False.
Q.6.b : complexité
La création de vu coûte O(n²), puis chacune des n² cases est traitée en temps constant (accès à une liste par indice). La complexité est donc O(n²), linéaire en nombre de cases. Une solution naïve, qui teste « k in liste » pour chaque k de 1 à n² sur une liste aplatie de n² éléments, coûterait O(n⁴). Il faut savoir justifier la différence.
IV. Q.7 : matrice_nulle(n)
def matrice_nulle(n):
return [[0] * n for i in range(n)]
Piège classique : [[0] * n] * n est incorrect. Cette expression crée n références vers la même liste, si bien que modifier une case modifie toute la colonne. Chaque ligne doit être une liste distincte.
Q.8 : siamoise(n)
On part de la case (0, n//2) contenant 1. Pour chaque nombre suivant, on vise la case « une vers le haut, une vers la droite », soit ((i−1) mod n, (j+1) mod n), et le modulo réalise l'enroulement sur un tore. Si cette case est déjà occupée, on place le nombre juste en dessous de la case courante, soit ((i+1) mod n, j).
def siamoise(n):
C = matrice_nulle(n)
i, j = 0, n // 2
for v in range(1, n * n + 1):
C[i][j] = v
ni, nj = (i - 1) % n, (j + 1) % n
if C[ni][nj] != 0:
ni, nj = (i + 1) % n, j
i, j = ni, nj
return C
En Python, (−1) % n vaut n−1, ce qui gère le passage de la ligne 0 à la dernière ligne. Cette fonction, exécutée, redonne exactement le carré d'ordre 5 de l'exemple (première ligne 17, 24, 1, 8, 15) et le carré d'ordre 7 de l'énoncé (première ligne 30, 39, 48, 1, 10, 19, 28, dernière ligne 22, 31, 40, 49, 2, 11, 20). Sa complexité est O(n²).
Q.9 : constante_magique(n) en temps constant
Les n lignes ont toutes la même somme S et se partagent tous les nombres de 1 à n². On a donc n·S = 1 + 2 + … + n² = n²(n² + 1)/2, d'où S = n(n² + 1)/2.
def constante_magique(n):
return n * (n * n + 1) // 2
Contrôles : pour n = 3, S = 3×10/2 = 15 (8+1+6) ; pour n = 5, S = 65 ; pour n = 7, S = 7×50/2 = 175, ce qui correspond bien à la première ligne du carré d'ordre 7 : 30+39+48+1+10+19+28 = 175. Le calcul se fait en O(1), sans boucle.
💡 À retenir pour le CNC Informatique (MP/PSI/TSI) : l'épreuve revient chaque année au même format : un exercice court d'algorithmique, du calcul numérique avec numpy et matplotlib (sommes de séries, tracés avec linspace, plot, legend, méthodes d'Euler, de dichotomie ou de Newton), une partie SQL (jointures, GROUP BY / HAVING, sous-requêtes NOT IN, COUNT(DISTINCT), algèbre relationnelle avec π, σ, ⋈ et −) et un problème sur des listes de listes. Révisez les calculs de complexité (boucles imbriquées, coût de « in » sur une liste), les pièges des flottants (round plutôt que int, // plutôt que /), la copie de listes ([[0]*n]*n) et l'indexation modulo. Entraînez-vous à écrire du code court sur papier, en réutilisant vos fonctions précédentes.
Questions fréquentes sur ce sujet
Ce sujet est-il téléchargeable gratuitement ?
Le corrigé est-il inclus ?
Quel organisme et quel grade concerne ce sujet ?
De quelle session s'agit-il et dans quelle langue ?
Où trouver d'autres sujets du même concours ?
Vous préparez ce concours ?
Modèles similaires
Source : concours d'accès aux écoles et instituts supérieurs — document archivé tel que reçu ; l'avis officiel du concours fait foi.
}