Vérifier si ma masortingce est un carré magique

J’ai donc cette masortingce:

8 1 6 3 5 7 4 9 2 

Et maintenant, je veux vérifier s’il s’agit d’un “carré magique”. Cela signifie que les sums de toutes les lignes, colonnes et lignes obliques, respectivement, sont égales (ici, la valeur est 15).

Donc, parce que je veux le faire aussi efficacement que possible et que je dois d’abord imprimer ma masortingce, je veux effectuer toutes les vérifications de valeurs dans la même fonction:

 void printmasortingx(int *mat, int dimension) { int i, j, rowscount, colcount; int firstvalue = 0; int ismagicsquaere = 0; for (i = 0; i < dimension; i++) { rowscount = 0; for (j = 0; j < dimension; j++) { int num = *(mat + i * dimension + j); if (i == 0) firstvalue += num; else rowscount += num; printf("%d\t", num); } if (rowscount != firstvalue) ismagicsquaere = 0; printf("\n\n"); } 

Actuellement, ma fonction vérifie uniquement la valeur des lignes. Je me demande s’il est également possible de vérifier les colonnes et les lignes obliques?

Tout faire dans les boucles nestedes est un problème intéressant.

Le seul petit défi consistait également à calculer les sums des colonnes , car, dans la façon dont les boucles sont écrites, il semble tout d’abord qu’un tableau [dimension] serait nécessaire.

Cependant, une petite astuce est utile. Cette ligne pour obtenir une valeur de ligne

 int rownum = *(mat + i * dimension + j); 

Peut aussi être utilisé pour obtenir la valeur col, en inversant i et j

 int colnum = *(mat + j * dimension + i); 

Permettant également de faire la sum des colonnes au même endroit (une masortingce étant un carré!)

 void printmasortingx(int *mat, int dimension) { int i, j; int magic=1; // default to "is magic" int d1=0,d2=0,refcount=0; // diag1, diag2 for (i = 0 ; i < dimension; i++) { int rowcount = 0; int colcount = 0; for (j = 0; j < dimension; j++) { int num = *(mat + i * dimension + j); rowcount += num; // row sum if (i == j) d1 += num; // diag1 sum if (i == dimension-j-1) d2 += num; // diag2 sum // row to col ... colcount += *(mat + j * dimension + i); // col sum } if (!i) refcount = rowcount; // first rowcount is reference else if (refcount != rowcount) magic = 0; if (refcount != colcount) magic = 0; } if (d1 != refcount || d2 != refcount) magic = 0; printf("Is Magic: %s\n", magic ? "Yes":"No"); } 

Apparemment, vous devez parcourir la masortingce 3 fois, avec 3 boucles séparées. Je ne vois aucun moyen de contourner cela.

L’implémentation “naïve”:

  • Faites la sum de la première ligne et stockez ce résultat dans une variable à utiliser pour les comparaisons.
  • Faites la sum du rest des lignes dans une boucle et comparez-la à la variable. Si des sums sont inégales, retourne false à partir de la fonction.
  • Seconde boucle, vérifiez les colonnes, comparez-les à la même variable, si aucune inégale, renvoyez false.
  • Troisième boucles, vérifiez la diagonale, comparez avec la même variable, si aucune inégale, retourne faux.

Cet algorithme est toutefois potentiellement inefficace car il nécessite beaucoup de twigs. Ce que vous pouvez faire pour l’optimiser manuellement est de réduire le nombre de twigs.

Une implémentation éventuellement plus rapide:

  • Faire la sum de toutes les lignes, stocker les résultats dans un tableau de résultats. Ceci est convivial pour le cache et signifie que le tableau se retrouvera dans le cache de données.
  • Faites la même chose avec les colonnes et les diagonales.
  • Assurez-vous que vos 3 tableaux de sum sont alloués de manière adjacente en mémoire en les plaçant dans une structure. Ceci est amical en cache. De préférence quelque chose comme ceci:

     typedef union { struct { unsigned int row_sum[3]; unsigned int col_sum[3]; unsigned int dia_sum[2]; }; unsigned int sum [3+3+2]; } sum_t; _Static_assert(sizeof(sum_t) == sizeof(unsigned int[3+3+2]), "Sorry, weird systems are not supported."); 
  • Après avoir terminé la sum, parcourez le tableau de sum ci-dessus et comparez chaque élément au premier.

Cela peut ou non améliorer les performances. Vous devez le comparer au système spécifique.

  1. Votre code est bogué, car vous commencez avec ismagicsquaere = 0 . Mais même si vous commencez avec ismagicsquaere = 1 , le ismagicsquaere = 1 persiste car, dans l’itération i = 0 , la variable rowscount rest égale à zéro, de sorte que la comparaison suivante conduit toujours à définir ismagicsquaere = 0 , ce qui n’est pas ce que vous souhaitez.

  2. Si vous visez la vitesse, évitez autant que possible toute clause if dans une boucle, en particulier dans la boucle interne.

  3. Étant donné que vous avez un printf dans votre boucle intérieure, la vitesse ne me pose aucun problème, car cette opération d’entrée / sortie dominera de loin le temps d’exécution.

  4. Si votre objective était vraiment une vérification rapide du carré magique, vous devrez non seulement supprimer les appels à printf, mais également renvoyer la fonction dès que la première vérification échoue.

Voici mon code suggéré, y compris les contrôles pour les deux diagonales. Puisque je suppose que vous avez besoin que l’impression soit incluse, j’ai laissé les appels à printf sans append de retour anticipé:

 void printmasortingx(const int *mat, int dimension) { int i, j; int ismagicsquare = 1; int diagonal1 = 0, diagonal2 = 0; for (i = 0; i < dimension; i++) { diagonal1 += mat[i * dimension + i]; diagonal2 += mat[i * dimension + dimension - 1 - i]; } if (diagonal1 != diagonal2) { ismagicsquare = 0; } for (i = 0; i < dimension; i++) { int rowscount = 0; int colscount = 0; for (j = 0; j < dimension; j++) { rowscount += mat[i * dimension + j]; colscount += mat[j * dimension + i]; printf("%d\t", mat[i * dimension + j]); } if (rowscount != diagonal1 || colscount != diagonal1) { ismagicsquare = 0; } printf("\n\n"); } printf("ismagicsquare = %i\n", ismagicsquare); } 

Notez qu'en ce qui concerne les access à la mémoire et l'optimisation du cache, la vérification sur place des sums de lignes comme indiqué ci-dessus devrait être la plus rapide, mais les deux boucles nestedes identiques incrémentent et évaluent à la fin. De cette manière, le tapis d'access à la mémoire [j * dimension + i], extrêmement hostile au cache, serait complètement supprimé. Toutefois, ce type d’optimisation n’a de sens que lors de la conception d’une fonction de vérification pure sans appel printf.

J’ai écrit le code suivant dans le but d’écrire (un jour) un code qui élabore des carrés magiques.

Il stocke toutes les lignes, colonnes et sums en diagonales dans une masortingce. Le but de cette masortingce ( sum[][] ) doit être de comprendre où le carré magique n’est pas correct.

Le principal appelle la fonction checkAndComputeSums() qui calcule toutes les sums et renvoie 1 si les données dans le carré magique sont correctes et 0 si elles sont incorrectes.

Voici le code:

 #include  #define DIMS 3 #define COLS DIMS #define ROWS DIMS int checkAndComputeSums(int *s , int *ms, int dim); enum STYPE { SUMROW, SUMCOL, SUMDIAG, //------------------- SUMCNT }; int msqr[COLS][ROWS] = { { 8, 1, 6}, { 3, 5, 7}, { 4, 9, 2} }; int sum[DIMS][SUMCNT]; const char * label[SUMCNT] = { "ROWS","COLS","DIAG" }; int checkAndComputeSums(int *s , int *ms, int dim) { int i,j,ok=1; /* The sum are cleared */ for(i=0;i