Niveau Licence Maths 1e ann

Algorithme carré magique

Posté par
imeneben 26-12-11 à 16:55

Bonjour ! Pourriez-vous m'aider a résoudre cet exercice s'il vous plaît ?

Un carré magique d'ordre n est une matrice carrée d'ordre n dans laquelle on écrit une et une
seule fois les nombres entiers de 1 à n², de sorte que la somme des nombres de chaque ligne,
chaque colonne et chaque diagonale est une constante.
1. En vous basant sur la règle suivante, écrire un algorithme qui permet de générer un carré
magique d'ordre n.
Règle :
(a) Mettre 1 au milieu de la première ligne.
(b) Inscrire le successeur de l'élément courant dans case suivante d'écrite selon le mouvement
'nord-est' c'est-à-dire un pas vers le haut et un pas vers la droite.
(c) Si on sort du carré, faire comme si le carré était bouclé : le haut collé au bas, la droite
collée à la gauche.
(d) Si cette règle aboutit à inscrire un nombre dans une cellule déjà occupée, il convient
de l'inscrire dans la cellule située sous le dernier nombre déjà inscrit et continuer selon
(b).

Merci de bien vouloir m'aider

Posté par re : Algorithme carré magique 26-12-11 à 17:30

Bonsoir

Le point d n'est pas clair. Que signifie "le dernier nombre déjà inscrit" ?

Posté par re : Algorithme carré magique 26-12-11 à 17:35

Bonsoir Bachstelze
Voilà un lien qui explique le principe : http://puzzlavie.be/news/carre-magique-2

Posté par re : Algorithme carré magique 26-12-11 à 17:46

Code en C :

#include <stdio.h>
#include <stdlib.h>

void usage(char *s)
{
        fprintf(stderr, "Usage: %s <n>\n", s);
        exit(EXIT_FAILURE);
}

int main(int argc, char** argv)
{
        /* On veut deux arguments */
        if (argc != 2) {
                usage(argv[0]);
        }

        /* Convertit l'argument en un entier */
        char *p;
        int n = strtol(argv[1], &p, 10);
        if (*p != '\0') {
                fprintf(stderr, "Erreur: l'argument doit être un entier!\n");
                usage(argv[0]);
        }

        int t[n][n];
        for (int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                        t[i][j] = 0;
                }
        }

        int x = n/2;
        int y = 0;
        for (int i=1; i <= n*n; i++) {
                t[y][x] = i;
                if (i == n*n) {
                        break;
                }
                x = (x+1) % n;
                y = (y+n-1) % n;
                if (t[y][x] != 0) {
                        x = (x+n-1) % n;
                        y = (y+2) % n;
                }
        }

        /* Affichage */
        for (int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                        printf("%4d ", t[i][j]);
                }
                printf("\n");
        }

        /* Vérification, lignes */
        int s = 0, s2 = 0;
        for (int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                        s2 += t[i][j];
                }
                if (s == 0) {
                        s = s2;
                }
                if (s2 != s) {
                        printf("Le carré n'est pas un carré magique !\n");
                        exit(EXIT_FAILURE);
                }
                s2 = 0;
        }

        /* Vérification, colonnes */
        for (int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                        s2 += t[j][i];
                }
                if (s2 != s) {
                        printf("Le carré n'est pas un carré magique !\n");
                        exit(EXIT_FAILURE);
                }
                s2 = 0;
        }

        /* Vérification, diagonales */
        for (int i=0; i<n; i++) {
                s2 += t[i][i];
        }
        if (s2 != s) {
                printf("Le carré n'est pas un carré magique !\n");
                exit(EXIT_FAILURE);
        }
        s2 = 0;

        for (int i=0; i<n; i++) {
                s2 += t[i][n-i-1];
        }
        if (s2 != s) {
                printf("Le carré n'est pas un carré magique !\n");
                exit(EXIT_FAILURE);
        }

        printf("Le carré est un carré magique. La somme est %d.\n", s);
}

Chez moi ça fonctione jusqu'à n = 1447. Après ça fait un segfault, sans doute à cause d'un stack overflow...