Ищем сумму элементов всех подматриц для заданной матрицы

Здесь нас интересовала не подматрица с минимальной суммой элементов и не подматрицы из совпадающих элементов, а сумма элементов всех подматриц в заданной матрице.

"Нативное" решение перебором даст временную сложность алгоритма порядка O(n⁶), что весьма избыточно.

Если же для каждого элемента матрицы Ai,j найти количество подматриц, в которые он входит, вычислительные затраты можно намного сократить.

Предположим, что индексы элемента равны (i,j), тогда, при нумерации с нуля, имеем для этого элемента количество подматриц S(i,j) = (i + 1) * (j + 1) + (N - i) * (N - j), где N - размерность матрицы (подумайте, что изменится, если матрица - не квадратная).

Нам остаётся просто выбирать в матрице две разные позиции, которые создают подматрицу, охватывающую данный элемент и считать сумму для этого элемента по формуле Sum += S(i,j) * A[i][j]. Таким образом, мы обходимся временной сложностью алгоритма порядка O(n²).

Ниже показан соответствующий код, который был проверен в консоли Visual Studio 2015.

#include <iostream> 
using namespace std;

int matrixSum(int n, int **arr) {
 int sum = 0;
 for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
   int top_left = (i + 1) * (j + 1);
   int bottom_right = (n - i) * (n - j);
   sum += (top_left * bottom_right * arr[i][j]);
  }
 }
 return sum;
}

int main() {
 const int n = 3;
 int **a = new int * [n];
 for (int i=0; i<n; i++) a[i] = new int [n];
 //Заполняем одними единичками
 for (int i = 0; i < n; i++)
 for (int j = 0; j < n; j++) a[i][j] = 1;
 cout << matrixSum(n,a);
 cin.get();
 return 0;
}

Кстати, для матрицы размерностью 2x2, составленной из единичек, ответ равен 16, потому что количество подматриц с одним или двумя элементами - по 4, с тремя элементами подматриц нет, а с четырьмя - одна, имеем

1 + 1 + 1 + 1 + 2 + 2 + 2 + 2 + 0 + 4 = 16

Для матрицы размерностью 3x3 из единичек ответ равен 100.

15.02.2019, 13:38 [2759 просмотров]