Подсчет сумма квадрата #665291

Есть матрица NxN. Нужно сосчитать суммы всех матриц MxM (M меньше N) внутри это исходной матрицы. Причем порядок алгоритма О(N*N). Пока придумал только так: 1) Считаем суммы по столбикам и строкам всех элементов исходной матрицы и запоминаем это в полученный результат в матрицу S. (порядок NxN) 2)Считаем сумму первой матрицы, которая находится в (0,0) (порядок M) 3) Считаем суммы других матриц через предыдущие суммы и сумма столбиков и столбцов (порядок MxM) Вроде все правильно, но громоздко и не прозрачно. Может быть есть идеи более изящного алгоритма? P.S. могу подробнее описать

Исправьте тему на "Подсчет сумм квадратов"

Может поможет: "Рекурсивная функция".

Ищи дерево отрезков, и дерево фенвика. Правда сложность чуть хуже чем ты хочешь.

не, надо именно N^N - условие задания.

думал, но каким образом?

я все равно не понял твою идею

в смысле не понял? Дерево фенвика именно для твоей задачи и придумано. Конкретно для твоего случая есть статья на хабре.

к

самих матриц O(n^3), так что ты со сложностью что-то напутал.

читаю Задание "слово в слово": Дан квадратный массив N*N и число M. Для каждого квадрата M*M (M < N) в этом массиве вычислить сумму его элементов. Общее число действий порядка N*N

N*N многовато... -M надо

а теперь прочитай что у тебя в написано. Ты разницы не видишь?

ты говоришь, что N^3, но я же привел алгоритм N^2. Просто задание простое должно быть, и хочется изящный алгоритм

нет

а в чем ошибка скажи пожалуйста?

в у тебя написано посчитать сумму элементов для всех квадратных матриц, а в сумму элементов квадратных матриц при заданном М.

пардон

может кто поправить ?

Для дерево фенвика не нужно. Мне сейчас не написать решение, я у зубного :)

ну ок, я подожду - не горит. лечись

Вычислим суммы элементов матриц размера MxM верхнего ряда матрицы NxN. На это потребуется N*M операций. (чтоб посчитать сумму элементов матрицы образованной сдвигом на один элемент влево - нужно прибависть сумму одного ряда, и отнять сумму одного ряда от предыдущей матрицы) Вычислим так-же суммы элементов матриц MxM левого ряда матрицы NxN. А далее, так как сумма элементов матрицы с верхним левым углом в элементе S(а,b) равна S(a-1,b)+S(a,b-1)-S(a-1,b-1)+N(a+M-1,b+M-1)+N(a-1,b-1)-N(a-1,b+M-1)-N(a+M-1,b-1), то по-очереди можем посчитать сумму элементов всех матриц размера MxM. N(a,b) - значение элемента [a,b] в начальной матрице. S(a,b) - сумма элементов в матрице MxM с началом (левым верхним углом) в элементе [a,b]

Спасибо, я мыслил так, но что то в этом направлении не получилось. Мб еще скину потом там посложнее задачка

завтра

Попробуй прежде чем считать подвести нормальную матбазу. Например в скольких матрицах присутсвует число с позиции (1,1) или число с позиции (b,b) Это если я правильно задачу понял

Тогда за один обход исходя из количества матриц для данной позиции можно высчитать суммы всех матриц

А нафига перебирать матрицы - неясно

Можно еще раз? Ты предлагаешь обойти все элементы начального массива, и приссумировать каждый ко всем матрицам в которых он присутствует? Поздравляю! Ты решил за O(N^2*M^2) задачу которая легко решается за O(N^2)

Сумма = 0; Для Сч = 1 По N Цикл   Для Сч = 1 По N Цикл       Сумма = Сумма + А[Сч,Сч] * В(Сч,Сч);   КонецЦикла; КонецЦикла; Где В(Сч1, Сч2) - в скольких матрицах встречается элемент А[Сч1;Сч2] Осталось только определить функцию В - это легко

Там два разных счетчика, сори

тебе вообще-то не одну сумму надо посчитать.

В ноль нужно отдельно посичтать сумму многих матриц.

А, значит я неправильно задачу понял