Les carrés magiques
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.
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.
M = [[4,7,10,3],[3,2,9,6],[13,0,5,8],[7,1,6,25]]M[i] est la liste qui représente la ligne d'indice i dans M.
M[0]est la liste [4, 7, 10, 3]M[2]est la liste [13, 0, 5, 8]
M[i][j] est l'élément à la ième ligne et la jème colonne dans M.
M[0][1]est l'élément 7M[2][1]est l'élément 0
I. Opérations sur une matrice carrée
Somme d'une ligne
É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
def somme_ligne(M, i):
n = len(M)
s = 0
for j in range(n):
s += M[i][j]
return sSomme d'une colonne
É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 nombres de la colonne d'indice j dans M.
Exemple : La fonction somme_colonne(M, 0) retourne la somme 4+3+13+7 = 27
def somme_colonne(M, j):
n = len(M)
s = 0
for i in range(n):
s += M[i][j]
return sSomme de la première diagonale
É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
def somme_diag1(M):
n = len(M)
s = 0
for i in range(n):
s += M[i][i]
return sSomme de la deuxième diagonale
É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
def somme_diag2(M):
n = len(M)
s = 0
for i in range(n):
s += M[i][n - 1 - i]
return sII. Carré magique
Vérification d'un carré magique
Écrire la fonction carre_magique(C), qui reçoit en paramètre une matrice carrée C contenant des entiers strictement positifs, et qui retourne :
Truesi la matrice C est un carré magique (les sommes sur chaque ligne, sur chaque colonne et sur chaque diagonale principale sont toutes égales)Falsesinon.
- La fonction
carre_magique(A)retourne True - La fonction
carre_magique(B)retourne False
def carre_magique(C):
n = len(C)
ref = somme_ligne(C, 0)
# Vérifier toutes les lignes
for i in range(1, n):
if ref != somme_ligne(C, i):
return False
# Vérifier toutes les colonnes
for j in range(n):
if ref != somme_colonne(C, j):
return False
# Vérifier les deux diagonales
if somme_diag1(C) != ref or somme_diag2(C) != ref:
return False
return TrueIII. 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^2\).
Vérification d'un carré magique normal
Écrire la fonction magique_normal(C), qui reçoit en paramètre une matrice carrée C qui représente un carré magique. La fonction retourne True si le carré magique C est normal, sinon, elle retourne False.
Exemples :
magique_normal([[8, 1, 6], [3, 5, 7], [4, 9, 2]])retourne Truemagique_normal([[21, 7, 17], [11, 15, 19], [13, 23, 9]])retourne False
def magique_normal(C):
# D'abord vérifier que c'est un carré magique
if not carre_magique(C):
return False
n = len(C)
# Tableau pour marquer les nombres de 1 à n²
etat = [0] * (n * n)
for i in range(n):
for j in range(n):
val = C[i][j]
# Vérifier que la valeur est dans l'intervalle [1, n²]
if val <= n * n and etat[val - 1] == 0:
etat[val - 1] = 1 # Marquer comme vu
else:
return False
return TrueIV. 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 :
- Créer une matrice carrée d'ordre n, remplie de 0.
- Placer le nombre 1 au milieu de la ligne d'indice 0.
- 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^2\).
- Le déplacement doit respecter les deux règles suivantes :
- 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.
Matrice nulle
Écrire la fonction matrice_nulle(n), 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 : matrice_nulle(5) retourne la matrice suivante :
[[0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0]]
def matrice_nulle(n):
return [[0] * n for _ in range(n)]Méthode siamoise
É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 : siamoise(7) retourne la matrice carrée qui représente le carré magique normal d'ordre 7 suivant :
def siamoise(n):
# Créer une matrice nulle
C = matrice_nulle(n)
# Placer le 1 au milieu de la première ligne
i, j = 0, n // 2
C[i][j] = 1
# Remplir les nombres de 2 à n²
for val in range(2, n * n + 1):
# Déplacement vers le haut-droite
i -= 1
j += 1
# Gestion du tore (si on sort de la matrice)
if i < 0:
i = n - 1
if j >= n:
j = 0
# Si la case est déjà occupée, on revient au déplacement précédent
# et on descend d'une case
if C[i][j] != 0:
i += 2
j -= 1
if i >= n:
i -= n
if j < 0:
j = n - 1
C[i][j] = val
return CConstante magique
É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.
La constante magique d'un carré magique normal d'ordre n est donnée par la formule :
\( \text{constante} = \frac{n(n^2 + 1)}{2} \)
def constante_magique(n):
return n * (n * n + 1) // 2- Un carré magique est une matrice carrée où toutes les lignes, colonnes et diagonales principales ont la même somme.
- Un carré magique normal contient tous les entiers de 1 à n² exactement une fois.
- La méthode siamoise permet de construire un carré magique normal pour tout ordre n impair.
- La constante magique d'un carré magique normal est
n(n²+1)/2. - La programmation des matrices en Python utilise des listes de listes.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.