大小为MxN的矩阵中大小为AxB的子矩阵的数量 [英] Number of submatrix of size AxB in a matrix of size MxN

问题描述

我正在关注 https://taninamdar.files.wordpress.com/2013 /11/submatrices3.pdf 来查找矩阵的子矩阵总数.但是，如何确定一个矩阵中存在多少给定大小的子矩阵仍然很困难. 同样0 <= A <= M和0 <= B <= N.
其中AxB(子矩阵大小)和MxN(矩阵大小).

I am following https://taninamdar.files.wordpress.com/2013/11/submatrices3.pdf to find total number of sub matrix of a matrix.But am stuck how to find how many sub matrix of a given size is present in a matrix. Also 0<=A<=M and 0<=B<=N.
where AxB(submatrix size) and MxN(matrix size).

推荐答案

我没有读过pdf(数学和我不是朋友)，但是简单的逻辑就足够了.简单地，尝试减小尺寸:您可以在长度为n的向量中放入多少个长度为m的向量?

I didn't go through the pdf (math and I aren't friends), however simple logic is enough here. Simply, try to reduce the dimension: How many vectors of length m can you put in a vector of length n ?

答案:n-m+1.要说服您，请仔细研究所有案例.说n = 5和m = 5.您有一种可能性.使用n = 5和m = 4，您有两个(第二个向量从索引0或索引1开始).使用n = 5和m = 3，您可以获得三个(向量可以从索引0、1或2开始).对于n = 5和m = 1，您有5个，似乎是逻辑.

Answer: n-m+1. To convince you, just go through the cases. Say n = 5 and m = 5. You've got one possibility. With n = 5 and m = 4, you've got two (second vector starts at index 0 or index 1). With n = 5 and m = 3, you've got three (vector can start at index 0, 1 or 2). And for n = 5 and m = 1, you've got 5, seems logic.

因此，为了将其应用于矩阵，您必须添加一个尺寸.你是怎样做的 ?乘法.您可以在长度为n的向量中放入多少个长度为a的向量? n-a+1.您可以在长度为m的向量中放入多少个长度为b的向量? m-b+1.

So, in order to apply that to a matrix, you have to add a dimension. How do you do that ? Multiplication. How many vectors of length a can you put inside a vector of length n ? n-a+1. How many vectors of length b can you put inside a vector of length m ? m-b+1.

那么，您可以在长度为N*M的矩阵中放入多少个大小为A*B的矩阵? (N-A+1)*(M-B+1).

So, how many matrices of size A*B can you put in a matrix of length N*M ? (N-A+1)*(M-B+1).

因此，我没有处理其中一个维度为0的情况.这取决于您如何考虑这种情况.

So, I didn't handle the case where one of the dimension is 0. It depends on how you consider this case.

这篇关于大小为MxN的矩阵中大小为AxB的子矩阵的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！