Comprueba si mi matriz es cuadrado mágico.

Así que tengo esta matriz:

8 1 6 3 5 7 4 9 2 

Y ahora quiero comprobar si esto es un “cuadrado mágico”. Esto significa que las sums de todas las filas, columnas y líneas oblicuas, respectivamente, son iguales (aquí con valor de 15).

Entonces, como quiero hacerlo de la manera más eficiente posible y primero debo imprimir mi matriz, quiero hacer todas las comprobaciones de valores en la misma función:

 void printmatrix(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"); } 

Actualmente mi función solo verifica el valor de las filas. Me pregunto si también es posible verificar las columnas y las líneas oblicuas.

Hacer todo dentro de los bucles nesteds es un problema interesante.

El único desafío pequeño fue calcular las sums de las columnas también, ya que, tal como se escriben los bucles, al principio parece que una matriz [dimensión] sería necesaria.

Sin embargo, un pequeño truco es de ayuda. Esta línea para obtener un valor de fila

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

También podría usarse para obtener el valor de col, invirtiendo i y j

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

Permitiendo sumr las columnas también en el mismo lugar (¡una matriz es un cuadrado!)

 void printmatrix(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"); } 

Aparentemente tienes que iterar a través de la matriz 3 veces, con 3 bucles separados. No veo manera de evitar esto.

La implementación “ingenua”:

  • Sume la primera fila y almacene este resultado en una variable para el uso en adelante para las comparaciones.
  • Suma el rest de las filas en un bucle y compara con la variable. Si alguna sum es desigual, devuelva falso desde la función.
  • Segundo bucle, verifique las columnas, compare con la misma variable, si existe alguna, devuelva falso.
  • Terceros bucles, verifique la diagonal, compare con la misma variable, si existe alguna, devuelva falso.

Sin embargo, este algoritmo es potencialmente ineficaz porque es muy intensivo en ramificaciones. Lo que puede hacer para optimizarlo manualmente es reducir el número de sucursales.

Una implementación posiblemente más rápida:

  • Suma todas las filas, almacena los resultados en una matriz de resultados. Esto es fácil de almacenar en caché y significará que la matriz termina en caché de datos
  • Haz lo mismo con las columnas y las diagonales.
  • Asegúrese de que sus matrices de 3 sums estén asignadas adyacentemente en la memoria colocándolas en una estructura. Esto es amigable con el caché. Preferiblemente algo como esto:

     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."); 
  • Después de completar la sum, recorra la matriz de sum anterior y compare cada elemento con el primero.

Esto puede o no mejorar el rendimiento. Tienes que compararlo en el sistema específico.

  1. Su código tiene errores, ya que comienza con ismagicsquaere = 0 . Pero incluso si comienza con ismagicsquaere = 1 , todavía tiene errores, porque en la iteración i = 0 , la variable rowscount sigue siendo cero, por lo que la siguiente comparación siempre llevará a configurar ismagicsquaere = 0 , que no es lo que desea.

  2. Si apunta a la velocidad, siempre que sea posible debe evitar cualquier cláusula if dentro de un bucle, en particular dentro del bucle interno.

  3. Ya que tiene un printf en su bucle interno, no me importaría la velocidad, ya que esta operación de E / S dominará por mucho el tiempo de ejecución.

  4. Si su objective fuera realmente una verificación rápida de cuadrado mágico, no solo tendría que eliminar las llamadas a printf, sino también devolver la función tan pronto como la primera verificación falle.

Aquí está mi código sugerido, incluyendo cheques para las dos diagonales. Como supongo que necesita que se incluya la impresión, dejé las llamadas a printf y no agregué la devolución anticipada:

 void printmatrix(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); } 

Tenga en cuenta que con respecto a los accesos de memoria y la optimización de caché, debería ser más rápido realizar la comprobación de las sums de las filas como se muestra, pero dentro de los mismos dos bucles nesteds, incremente las sums por columna y evalúelas al final. De esta manera, la mata de acceso a la memoria muy hostil a antememoria [j * dimension + i] se eliminaría completamente. Sin embargo, este tipo de optimización solo tiene sentido cuando se diseña una función de verificación pura sin llamadas printf.

He escrito el siguiente código con el propósito de escribir (un día) un código que elabore cuadrados mágicos.

Almacena todas las filas, columnas y diagonales en una matriz. El propósito de esta matriz ( sum[][] ) será entender dónde el cuadrado mágico no es correcto.

La función principal llama a la función checkAndComputeSums() que calcula todas las sums y devuelve 1 si los datos en el cuadrado mágico son correctos y 0 si no son correctos.

Aquí el código:

 #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