检查我的矩阵是否是魔方

所以我有这个矩阵：

8 1 6 3 5 7 4 9 2 

现在我想检查这是否是一个“魔术广场”。 这意味着所有行，列和斜线的总和分别相等（此处值为15）。

因为我想尽可能高效地完成这项工作，我需要先打印我的矩阵，我想在同一个函数中进行所有值检查：

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

目前我的函数只检查行值。 我想知道是否也可以检查列和斜线？

Answer 1

在嵌套的for循环中做所有事情是一个有趣的问题。

唯一的小挑战是计算列总和，因为，循环的写入方式，似乎首先需要一个数组[维度] 。

然而，一个小技巧是有帮助的。 这行获取行值

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

也可以通过反转i和j来获得col值

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

允许在同一个地方对列进行求和（矩阵为正方形！）

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

Answer 2

显然你必须迭代3次矩阵，有3个独立的循环。 我认为没办法解决这个问题。

“天真”的实施：

• 对第一行求和并将此结果存储在变量中，以便以后用于比较。
• 在循环中对其余行求和并与变量进行比较。 如果任何总和不相等，则从函数返回false。
• 第二个循环，检查列，比较相同的变量，如果有任何不相等，则返回false。
• 第三个循环，检查对角线，与同一个变量进行比较，如果有任何不相等，则返回false。

然而，该算法可能无效，因为它是非常分支密集的。 手动优化它可以做的是减少分支数量。

一个可能更快的实现：

• 对所有行求和，将结果存储在结果数组中。 这是缓存友好的，意味着数组最终在数据缓存中。
• 对列和对角线执行相同操作。

• 通过将它们放在结构中，确保在内存中相邻地分配3个和数组。 这是缓存友好的。 最好是这样的：

   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."); 

• 完成求和后，浏览上面的sum数组并将每个项目与第一项进行比较。

这可能会也可能不会提高性能。 您必须在特定系统上对其进行基准测试。

Answer 3

1. 你的代码是错误的，因为你从ismagicsquaere = 0开始。 但即使你从ismagicsquaere = 1开始，它仍然是错误的，因为在迭代i = 0 ，变量rowscount保持为零，因此以下比较将始终导致设置ismagicsquaere = 0 ，这不是你想要的。

2. 如果你的目标是速度，你应该尽可能避免循环中的任何if子句，特别是在内部循环中。

3. 由于你的内循环中有一个printf，我根本不关心速度，因为这个I / O操作到目前为止将主导运行时。

4. 如果你的目标确实是一个快速的魔术方检查，你不仅要删除printf调用，而且在第一次检查失败时立即返回该函数。

这是我建议的代码，包括检查两个对角线。 因为我假设您需要包含打印，所以我离开了printf调用并且没有添加提前返回：

 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); } 

请注意，关于内存访问和高速缓存优化，如图所示，应该最快地检查行总和，但在相同的两个嵌套循环中，每列总和增加并在结束时对它们进行评估。 这样，将完全删除非常缓存不友好的内存访问垫[j * dimension + i]。 但是，这种优化只在设计没有printf调用的纯检查函数时才有意义。

Answer 4

我编写了以下代码，目的是编写（一天）一个详细说明魔术方块的代码。

它将所有行，列和对角线总和存储到矩阵中。 这个矩阵（ sum[][] ）的目的是要理解魔方不正确的地方。

main调用函数checkAndComputeSums()来计算所有和，如果进入幻方的数据是正确的，则返回1，如果不正确，则返回0。

这里的代码：

 #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