Carré Magique c++

[invite2216f80a]

Bonjour!

Je cherche à résoudre un exo d'algo en c++, voici l'énoncé ;

 Cliquez pour afficher

Un carré magique est une grille carrée dans laquelle des nombres sont placés de telle sorte que la somme des nombres de chaque colonne, chaque ligne et de chacune des deux diagonales soit la même. De plus, Le carré doit contenir une fois chaque nombre, de 1 au nombre de cases de la grille.

Ecrivez un programme qui vérifie si une grille de nombres est un carré magique.
LIMITES DE TEMPS ET DE MEMOIRE
Temps : 1s sur une machine à 1Ghz.
Mémoire : 1000 Ko.
CONTRAINTES
1 <= N <= 20, où N est le nombre de lignes et de colonnes de la grille.
ENTRÉE
La première ligne de l'entrée contient un entier N : le nombre de cases du côté de la grille de nombres.

Chacune des N lignes suivantes contient N entiers séparés par des espaces : les nombres d'une ligne de la grille.
SORTIE
Vous devez afficher une ligne sur la sortie, contenant le mot "yes" si le carré fourni est un carré magique, et "no" sinon.

EXEMPLE

entrée :
3
6 1 8
7 5 3
2 9 4

sortie :
yes
COMMENTAIRES
Chacun des chiffres de 1 à 9 apparaît exactement une fois dans la grille. De plus, toutes les colonnes, lignes et les deux diagonales de cette grille ont pour somme 15. En effet :

Lignes :
6 + 1 + 8 = 15
7 + 5 + 3 = 15
2 + 9 + 4 = 15

Colonnes :
6 + 7 + 2 = 15
1 + 5 + 9 = 15
8 + 3 + 4 = 15

Diagonales :
6 + 5 + 4 = 15
8 + 5 + 2 = 15

J'ai fait ce code qui marche bien, seulement, les tests du code par le serveur (site France IOI) me refuse 4 tests car mon programme, il semblerait, est trop gourmand en mémoire.

#include <iostream>

using namespace std;


int main(){
    int nb;
    cin>>nb;
    if(nb<1 || nb>20)
        return 0;

    int tab[nb][nb], sommel=0, sommeTl=0, sommec=0, sommeTc=0, sommeD=0, sommeD1=0;

    for(int i=0; i<nb; i++){
        for(int j=0; j<nb; j++){
            cin>>tab[i][j];
            sommel+=tab[i][j];
        }
        if(i==0)
            sommeTl=sommel;
        if(sommel!=sommeTl){
            cout<<"no";
            return 0;
        }
        sommel=0;
    }

    int nombre[9]={0};


    for(int i=0, k=nb-1; i<nb; i++, k--){
        sommeD+=tab[i][i];
        sommeD1+=tab[k][k];
        for(int j=0; j<nb; j++){
            nombre[tab[i][j]-1]++;
            sommec+=tab[j][i];
        }
        if(i==0)
            sommeTc=sommec;
        if(sommec!=sommeTc){
            cout<<"no";
            return 0;
        }
        sommec=0;
    }
    
    if(sommeTc!=sommeTl || sommeD!=sommeD1 || sommeD!=sommeTc){
        cout<<"no";
        return 0;
    } 

    for(int i=0; i<9; i++){
       if(nombre[i]!=1){
            cout<<"no";
            return 0;
       }
    }

    cout<<"yes";

    return 0;
}

Si quelqu'un a une idée pour aborder le sujet différemment ou pour diminuer la mémoire utilisée!

Exemple d'une erreur qu'il me met 4 fois la même :

Votre programme a échoué à la suite d'un accès mémoire en dehors des zones réservées, ou d'un dépassement de la limite de mémoire.
Votre programme s'est terminé à la suite d'une erreur. Cela peut venir d'une des raisons suivantes :
Votre programme a dépassé la limite de mémoire autorisée pour ce problème, que ce soit sous la forme de variables statiques, d'allocations dynamiques, ou bien de la pile.
Votre programme a tenté de faire un accès mémoire en dehors des zones allouées.

Je pense aussi que ma méthode pour tester s'il y a à chaque fois qu'une seule fois un chiffre est pas bonne!
-----

[invite4492c379]

Hello,

j'ai lu le code en diagonale et je dirais que tu déclares
int nombre[9]={0};

puis je vois :
nombre[tab[i][j]-1]++;

sachant qu'a priori on a 1<tab[i][j]<nb² pour tout i,j , je me dis que tôt ou tard tu vas exploser ton tableau nombre.

[invite2216f80a]

Oui, je me demande si les erreurs ne sont pas du à ça justement et pas à un problème de mémoire (par rapport aux contraintes demandées).

Du coup, il faudrait que je déclare en fonction des dimensions du tableau avec un int nombre[nb*nb]={0} ?

[invite2216f80a]

Edit impossible!

Il veut bien pas me prendre ça du coup :

int taille=nb*nb;
int nombre[taille]={0};

mais sans l'initialiser à 0, il prends...

[A voir en vidéo sur Futura]

[invite4492c379]

Je t'assure que le pb vient de là

Je suppose que le tableau nombre sert à vérifier que chaque nombre apparaît une et une seule fois ... alors oui int nombre[nb*nb+1]; me semble pas trop mal (le ={0} initialise-t-il toutes les cellules à 0 ?).

Je n'ai pas essayé de comprendre ton programme, je pourrais prendre un peu plus de temps un peu plus tard dans la soirée.

[invite2216f80a]

C'est bien ça, ce passage du code vérifie que le nombre n'est qu'une fois dans la grille.

Le ={0} mets théoriquement à 0, puisque ça ne marche pas là (mon message précédent).

Merci pour ces infos

[invite2216f80a]

Bon bah j'ai fais une petite boucle pour initialiser à 0, et tout à marché!

Tous les test réussi, c'était donc bien l'erreur du tableau!

Merci bien

[invite4492c379]

Well done Sheldon

[invited9b9018b]

Il me semble qu'en C, il n'est pas garanti qu'une déclaration du type :

int var = n;
int array[var];

soit tolérée par le compilo.
J'ai même lu qu'il était préférable dans ce cas, d'allouer la mémoire sur le tas (malloc) malgré le problème des fuites de mémoire
c'est à dire :

int var = n;
int array = malloc(var * sizeof(int));

EDIT : euh ? j'avais pas vu mais c'est censé être du c++... n'y aurait-il pas un petit problème?

[invite4492c379]

Il me semble qu'en C, il n'est pas garanti qu'une déclaration du type :

int var = n;
int array[var];

soit tolérée par le compilo.
J'ai même lu qu'il était préférable dans ce cas, d'allouer la mémoire sur le tas (malloc) malgré le problème des fuites de mémoire
c'est à dire :

int var = n;
int array = malloc(var * sizeof(int));

En C c'est autorisé depuis la norme C99 (mais limité, ne peut ni être static ni extern). Je ne peux que recommander valgrind pour s'assurer (en plus de la rigueur nécessaire à ce genre d'allocation dynamique) que les fuites mémoires sont maitrisées.

[invited9b9018b]

ok.
en revanche en c++ c'est interdit on est d'accord?
pour moi ce qu'a fait defender19 c'est du c, pas du c++ ?!

[invite4492c379]

Non, c'est autorisé en c++ le langage utilisé par defender19 (dans le titre : carré magique c++).

Maintenant il suffit d'essayer un code comme :

#include <iostream>


using namespace std;




int main(){
  int n;
  cout << "n=";
  cin >> n;
  int tab[n];
  cout << sizeof(tab)/sizeof(int) << endl;
}

Cela dépend peut-être du compilo ... je me renseigne (j'utilise gcc).

[invite2216f80a]

Je sais pas, mais en C comme en C++, j'ai l'habitude de faire comme ça sans problème pour des tableaux statiques.

[invite4492c379]

Pour info, la norme C++ (y compris C11) n'autorise pas un code comme celui que j'ai posté en #12. g++ le supporte comme une extension (issue de C99). La compilation avec l'option -pedantic génère un warning.
warning: ISO C++ forbids variable length array

[invited9b9018b]

plante aussi avec le compilateur de vcpp.

@defender: on parle de tableaux dynamiques

[invite4492c379]

Dans la norme c99 il s'agit bien d'une allocation dynamique mais sur la pile et non le tas, c'est pourquoi il est interdit de le déclarer en static.

[invite2216f80a]

Et au final, ce que j'ai fait c'est correct ou non? Parce que votre charabiat, j'y comprends pas encore quelque chose!

[invite4492c379]

Ton code ce n'est ni du C ni du C++ mais un mélange des deux. Pas forcément académique (ne compilera pas sous toutes les architectures), dangereux dans le sens où tu peux facilement faire exploser la pile.
Un allocation dyname sur le tas est faite via new[], ce qui serait un peu plus robuste.

[invite2216f80a]

Oui mais au final mon tableau n'est pas dynamique, il prend juste la taille nb² durant tout le programme, il est initialisé au début.

[invite4492c379]

Il y a en gros deux endroits où les variables sont stockées : la pile (stack) et le tas (heap). La pile est d'une taille faible et est utilisée pour stocker les paramètres d'appel de fonction, les appels de fonctions (savoir où on revient après l'appel), les variables locales. Le tas c'est là où sont stockée les données allouées dynamiquement. Il n'est pas bon de créer de grosses variables locales (tableaux volumineux ou grandes structures/classes) car la place sur la pile est limitée. C'est pourquoi on préfère l'allocation dynamique sur le tas (malloc, new, ...).
Dans ton code, le tableau n'est pas alloué du tout avant la ligne où tu le déclares, à ce moment là de la place est faite sur la pile (au pire dans les 1600 octets pour 400 int 32 bit). Si tu avais du utiliser un tableau plus grand tu aurais pu avoir un stack overflow (exploser la pile).

[invite2216f80a]

Ok ok, merci de bien de l'explication ! Après pour les besoins de l'exo, nb devait être <= à 20, donc max 400 cases, mais je retiens, merci

[hammadiashraf]

Bonjour à tous, je ne suis pas informaticien,mais j'ai des connaîssances en informatique. Je voulais juste savoir si le programme cité consisterait à obtenir d'autres carrés magiques de dimension 2n+1 avec n entier naturel >0 ; car pour ma part je dispose d'une methode permettant à l'aide d'une grille et un crayon d'obtenir facilement des carrés magiques à n'importe quelle dimension impaire.