Previous: 010_Temps et espace d’exécution

Carré magique


Next: TDA

Carrés magiques

Remplir un carré magique : c’est disposer les nombres 0 à p dans un carré de n \times n cases, de telle sorte que la somme des nombres dans chaque ligne, chaque colonne et sur les deux diagonales soit la même. Dès que le carré est supérieur à 5 \times 5 cases, il devient nécessaire de disposer d’une méthode. Nous allons considérer un exemple. Remplissons une grille de 7 \times 7

Rendered by QuickLaTeX.com

Nous plaçons tout d’abord 0 dans la case du milieu du bord gauche. En suivant la petite flèche nous sortirions du carré. Il faut donc placer 1 dans la case correspondante sur le bord opposé, et ainsi de suite jusqu’à 6. Il n’est plus possible de continuer puisque la case suivante est occupée. Il suffit de placer 7 à droite de 6 puis de reprendre la progression. Essayez de terminer seul ; vous pourrez vérifier que vous avez réalisé un carré magique puisque la somme des nombres placés dans chaque ligne, chaque colonne et chaque diagonale est constante (168). L’inconvénient majeur de cette solution c’est l’espace mémoire occupé puisqu’il faut se doter d’un tableau de n \times n cases. Un autre algorithme consiste à produire la valeur de chaque case dans l’ordre de lecture, de gauche à droite et de bas en haut. Supposons, pour simplifier, un carré magique de 5 \times 5 déjà réalisé et étudions sa composition :
14 15 21 2 8 2n+4 3n+0 4n+1 0n+2 n+3
7 13 19 20 1 n+2 2n+3 3n+4 4n+0 0n+1
0 6 12 18 24 0n+0 n+1 2n+2 3n+3 4n+4
23 4 5 11 17 4n+3 0n+4 n+0 2n+1 3n+2
16 22 3 9 10 3n+1 4n+2 0n+3 n+4 2n+0
En exprimant le contenu de chaque case par rapport au côté du carré la progression d’une case à la suivante est simple : les coefficients progressent régulièrement de 0 à b \in \{0, 1, 2\ldots n-1\} Lorsqu’une ligne est remplie, on passe à la première case de la ligne suivante en retranchant 1 au contenu de la dernière case de la ligne qui vient de s’achever. Enfin le premier terme du carré magique est obtenu par : x_{0} = \frac{n-1}{2} \times n + n -1 D’où l’algorithme : 
cote = SAISIR () ;
b = cote - 1 ;
a = (cote - 1) / 2 ;

for (ligne = 0 ; ligne < cote ; ligne++)
{
    for (col = 0 ; col < cote ; col++)
    {
        IMPRIMER (a * cote) + b ;
        if (col != (cote - 1))
        {
            a++ ; a = a modulo cote ;
            b++ ; b = b modulo cote ;
        }
   }
   b-- ;
}
Previous: 010_Temps et espace d’exécution
Next: TDA