Carré magique - CNC 2020 filière MP | Développement Informatique

Recommandé : Pour vous entraîner à résoudre des problèmes, vous devez essayer et essayer dur avant d'afficher la solution.

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

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 = [[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.

Exemple

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

Exemple

M[0][1] est l’élément 7
M[2][1] est l’élément 0

I. Opérations sur une matrice carrée

É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
Voir la réponse
```
def somme_ligne(M,i):
    n=len(M)
    s=0
    for j in range(n):
        s+=M[i][j]
    
    return s
                                                    
```
É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.
Exemple
La fonction somme_colonne (M, 0) retourne la somme 4+3+13+7 = 27
Voir la réponse
```
def somme_colonne(M,j):
    n=len(M)
    s=0
    for i in range(n):
        s+=M[i][j]
    
    return s
                                                    
```
É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
Voir la réponse
```
def somme_diag1(M):
    n=len(M)
    s=0
    for i in range(n):
        s+=M[i][i]
    
    return s
                                                    
```
É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
Voir la réponse
```
def somme_diag2(M):
    n=len(M)
    s=0
    for j in range(n):
        s+=M[n-j-1][j]
    
    return s
                                                    
```

II. 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 :

True, si la matrice C est un carré magique : les sommes sur chaque ligne, sur chaque colonne et sur chaque diagonale principale sont toutes égales
False, sinon.

Exemple

La fonction carre_magique (A) retourne True
La fonction carre_magique (B) retourne False

Voir la réponse

def carre_magique(C):
    n=len(C)
    ref=somme_ligne(C,0)
    for i in range(1,n):
        if ref != somme_ligne(C,i):
            return False
    
    for j in range(n):
        if ref!= somme_colonne(C,j):
            return False
    
    if somme_diag1(C)!=ref or somme_diag2(C)!=ref:
        return False
    
    return True

II. 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\).

Exemple

Carrée magique normal d’ordre 4, composé des nombres entiers : 1, 2, 3, …, 15, 16.

NB : Il n’existe pas de carré magique normal d’ordre 2.

É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

La fonction magique_normal ([ [8, 1, 6] , [3, 5, 7] , [4, 9, 2] ]) retourne True
La fonction magique_normal ([ [21, 7, 17] , [11, 15, 19] , [13, 23, 9] ]) retourne False

Voir la réponse

def magique_normal(C):
    if carre_magique(C)==False:
        return False

    n=len(C)
    etat=[0]* (n**2)
    for i in range(n):
        for j in range(n):
            if C[i][j]<=(n**2) and etat[C[i][j]-1]==0:
                etat[C[i][j]-1]=1
            else:
                return False
    
    return True

III. 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 (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.

Exemple

Construction d’un carré magique normal d’ordre 5

É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.
Exemples
La fonction 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]]
Voir la réponse
```
def matrice_nulle(n):
    return [[0]*n for i in range(n)]
                                                    
```

É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.
Exemples
La fonction siamoise (7) retourne la matrice carrée qui représente le carré magique normale d’ordre 7 suivant :

Voir la réponse

def siamoise(n):
    C=matrice_nulle(n)
    C[0][n//2]=1
    i,j=0,n//2
    it=1
    p1,p2=0,0
    while it<n**2:
        p1,p2=i,j
        i-=1
        j+=1

        if i<0:
            i=n-1
        
        if j>=n:
            j=0
        
        if C[i][j]!=0:
            i,j=p1+1,p2

        it+=1
        C[i][j]=it
    
    return C

É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.
Voir la réponse
```
def constante(n):
    return (n**2+1)*(n//2) +(n**2-(n+1)*(n//2))
                                                    
```

Carré magique - CNC 2020 filière MP