arrays - 检查给定的 Matrix(m*n) 内部是否有任何可以转置的矩阵
问题描述
我需要检查是否可以在给定的 5*8 矩阵大小内找到一个具有转置的矩阵,如果有多个,我必须找到最大的一个。
给定矩阵的示例
1 2 0 3 2 1 0 7
2 3 4 1 2 3 4 5
3 4 6 2 5 6 7 6
4 5 7 3 6 8 9 8
6 7 1 4 7 9 0 9
在这个矩阵中,我们可以找到一个具有转置的矩阵 4x4,它是主矩阵中最大的矩阵
1 2 3 4
2 5 6 7
3 6 8 9
4 7 9 0
#include <stdio.h>
#define M 4
#define column 5
#define row 8
int main()
{
int matrixA[5][8];
printf("please enter a matrix to check if there is a transpose matrix\n");
for (int i = 0; i < column; i++)
{
for (int j = 0; j < row; j++)
{
printf("please enter %d row and %d column: ", i + 1, j + 1);
scanf("%d", &matrixA[i][j]);
}
}
transpose(matrixA, column, row);
}
void transpose(int A[][row], int c, int r)
{
int matrixAT[M][M];
for (int size = r; size > 0; size--)
{
for (int j = 0; j < c - size + 1; j++)
{
for (int b = 0; b <= r - size; b++)
{
printf("Checking Matrix at row: %d , column: %d ,size: %dx%d", j, b, size, size);
for (int k = j, w = 0; k < size + j; k++, w++)
{
for (int l = b, z = 0; l < size + b; l++, z++)
{
matrixAT[w][z] = A[k][l];
}
printf("/n");
}
if (IsSymmetric(matrixAT, size))
printf("Matrix found");
}
}
}
}
int IsSymmetric(int mat[M][M], int size)
{
int flag = 0;
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (mat[i][j] == mat[j][i]) flag++;
}
}
return flag == size * size ? 1 : 0;
}
这是我的代码我不知道我做错了什么
解决方案
你IsSymmetric
的速度很慢,因为它总是检查所有元素,为什么不停止第一个不等式呢?还一次又一次地将其复制到临时数组...
主要问题是你没有检查每个位置和大小,因为你transpose(matrixA, column, row);
只在循环外调用一次......
此外,您的 main 不返回任何内容,并将其声明为 int ...
我会从这样的蛮力开始:
#define column 5
#define row 8
int IsSymmetric(int mat[column][row], int i0,int j0,int size) // check n*n sub matrix at i0,j0 no need to copy again and again to temp array
{
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
if (mat[i0+i][j0+j] != mat[i0+j][j0+i]) return 0;
return 1;
}
int min(int a,int b){ return (a<b)?a:b; } // not sure if min is present in your environment if is comment this line out
int main()
{
int matrixA[5][8];
...
for (int i = 0; i < column; i++)
for (int j = 0; j < row; j++)
for (int n = 1; n <= min(column-i,row-j); n++)
if (IsSymmetric(matrixA,i,j,n))
{
// here do what you want with the i,j,n*n sub matrix
// like remember position and size for the biggest n
}
...
return 0; // return value as you declared int main
}
希望我没有在此处输入任何拼写错误,因为我只是将其从您的原始代码写入答案编辑器。
无论如何,您可以看到它的O(n^4)
复杂性(平均而言O(n^3)
)确实很慢。但是,对于您的小矩阵来说,这不是问题。
如果您需要更快的东西,那么我们需要更多地了解数据……例如,值的范围是多少?一些提示:
- 在积极的 IsSymmetric 上测试一个单元格更大的子矩阵,而无需再次测试先前的元素(递归增加对角线)。
- 使用直方图检测可能仅在对角线上的值(全局出现一次或局部出现奇数次)
在解决方案中使用增量对称性测试结果O(n^3)
:
//---------------------------------------------------------------------------
#define column 5
#define row 8
//---------------------------------------------------------------------------
void submatrix_print(int mat[column][row], int i0,int j0,int n,int m)
{
int i,j;
printf("%i*%i at %i,%i\r\n",n,m,i0,j0);
for (i=0;i<n;i++,printf("\r\n"))
for (j=0;j<m;j++)
printf("%1i ",mat[i0+i][j0+j]);
}
//---------------------------------------------------------------------------
void submatrix_print_transposed(int mat[column][row], int i0,int j0,int n,int m)
{
int i,j;
printf("%i*%i at %i,%i\r\n",n,m,i0,j0);
for (i=0;i<m;i++,printf("\r\n"))
for (j=0;j<n;j++)
printf("%1i ",mat[i0+j][j0+i]);
}
//---------------------------------------------------------------------------
int min(int a,int b){ return (a<b)?a:b; }
int submatrix_symmetric(int mat[column][row], int i0,int j0) // returns biggest symetric submatrix size >=1 found at i0,j0
{
int i,n,N;
N=min(column-i0,row-j0); // max size that still fits into matrix
for (n=2;n<N;n++) // test all sizes above 1
for(i=0;i<n-1;i++) // only test newly added cells to last sub matrix
if (mat[i0+n-1][j0+i]!=mat[i0+i][j0+n-1])
return n-1; // first non match means last tested size i svalid
return n; // no mismatches mean full size is valid
}
//---------------------------------------------------------------------------
int main()
{
int mat[5][8]=
{
1,2,0,3,2,1,0,7,
2,3,4,1,2,3,4,5,
3,4,6,2,5,6,7,6,
4,5,7,3,6,8,9,8,
6,7,1,4,7,9,0,9,
};
submatrix_print(mat,0,0,5,8);
// submatrix_print_transposed(mat,0,0,5,8);
int i,j,n,i0=0,j0=0,n0=0;
for(i=0;i<column;i++)
for(j=0;j<row;j++)
{
n=submatrix_symmetric(mat,i,j);
if (n0<n){ n0=n; i0=i; j0=j; }
}
submatrix_print(mat,i0,j0,n0,n0);
return 0;
}
//-------------------------------------------------------------------------
代码的结果是:
5*8 at 0,0 // input matrix
1 2 0 3 2 1 0 7
2 3 4 1 2 3 4 5
3 4 6 2 5 6 7 6
4 5 7 3 6 8 9 8
6 7 1 4 7 9 0 9
4*4 at 1,3 // biggest symmetric sub matrix found
1 2 3 4
2 5 6 7
3 6 8 9
4 7 9 0
推荐阅读
- python - 如何将包含 4916 张图片(375x375x3)的 mat 文件转换为 numpy 数组?
- python - 在 __iter__ 中使用
- svg - 使用 px 坐标的 SVG 多边形
- javascript - 请使用相同的按钮播放和暂停音频
- angular - 如何更新 FormArrays 中的值
- c# - 是否可以使用 SDK4 从带有 Bot 的 MS Teams 获取用户电子邮件?
- ms-access - 如何使用 vb6.0 在 Ms Access 中获取最后一个插入 ID
- fullcalendar - FullCalendar 4 - 向事件对象添加然后访问其他值
- php - 如何在mysql数据库中显示图像和描述
- java - 预检中的 Access-Control-Allow-Methods 不允许方法 PATCH