Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité

Carré magique - CNC 2020 filière MP

Carré magique - CNC 2020 filière MP

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


  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
     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
                                                        
  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.
    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
                                                        
  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
     Voir la réponse 

    def somme_diag1(M):
        n=len(M)
        s=0
        for i in range(n):
            s+=M[i][i]
        
        return s
                                                        
  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
     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


  1. É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.
  1. É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 :

  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^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

  1. É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)]
                                                        
  2. É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
                                                            
  3. É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))
                                                        

Rédigé par ESSADDOUKI Mostafa

The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.

Partager ce cours avec tes amis :

Commentaire(s)