Дана квадратная матрица и число n. Заменить каждый элемент матрицы на среднее арифметическое элементов квадрата размера 2n+1 с центром в данном элементе.
Например, для элемента, выделенного зеленым, при n=1 должно вычисляться среднее арифметическое элементов красного и зеленого цвета, а для n=2 – среднее арифметическое желтых, красных и зеленых элементов. Если квадрат выходит за пределы матрицы, считать недостающие элементы равными нулю:
//n - вводится юзером
int formul = 2*n+1; //сторона квадрата
for(int i = 0;i<numArray;i++){
for(int j = 0;j<numArray;j++){
for(int k = 0;k<formul;k++){
for(int f = 0; f<formul; f++){
summator = arrayA[i][j];
if(((i-n)+k)<numArray &&((i-n)+k)>0){
summator += arrayA[((i-n)+k)][j-n];
num++;
}else if(((j-n)+f)<numArray && ((j-n)+f)>0){
summator += arrayA[i-n][((j-n)+f)];
num++;
}else if((i-n)>=0&&(j-n)>=0){
summator += arrayA[i-n][j-n];
num++;
}else{
summator+=0;
}
}
}
res = summator/num;
arrayB[i][j] = res;
num = 0;
}
}
Чтобы приведённый код хоть как-то заработал, стоит для начала вынести инициализацию суммы и количества элементов вне внутренних циклов
summator = arrayA[i][j];
num = 0;
for(int k = 0;k<formul;k++){
...
Потом можно обдумать логику проверок. а лучше без проверок обходить только то, что нужно:
summator = arrayA[i][j];
num = 0;
int top = i>=n?i-n:0;
int down = i<numarray-n?i+n:numarray;
for(int k = top;k<down;k++){
//аналогично для left, right
for(int f = left; f<right;f++){
summator += arrayA[k][f];
num++;
}
}
Если n будет велико и придёт нужда подумать об эффективности, можно использовать алгоритм со сложностью, пропорциональной количеству элементов. Посчитать суммы элементов, накопленные от левого верхнего угла в CSum[][]
, затем для каждого квадрата найти сумму элементов в его пределах по простому закону
Sum(top,left,down,right) =
CSum[down][right] + CSum[top][left]
- CSum[down][left] - CSum[top][right]
Пожалуй самый быстрым и красивым вариантом будет - простое ДП (Динамическое Программирование). Сначало мы предпосчитаем для каждой ячейки суммы элементов которые лежат с самого левого верхнего угла до самой ячейки. Эти значения будем хранить в двумерном массиве dp
. После, можно для любого прямоугольника найти сумму всех его элементов с помощью простой формулы: sum = dp[down][right] - dp[top][right] - dp[down][left] + dp[top][left]
. Вот само решение задачи:
for(int i = 1; i <= numArray; i++) {
for(int j = 1; j <= numArray; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + A[i][j]; //Предпосчет
}
}
for(int i = 1; i <= numArray; i++) {
for(int j = 1; j <= numArray; j++) {
int top = max(0, i - n - 1);
int down = min(numArray, i + n);
int right = min(numArray, j + n);
int left = max(0, j - n - 1);
double sum = dp[down][right] - dp[top][right] - dp[down][left] + dp[top][left];
double num = formula * formula;
B[i][j] = sum / num;
}
}
Здесь матрица A
- это изначальная матрица, а B
- ответ на задачу. Весь код будет работать за O(num)
, то есть сделает num
операции, где num
- это количество элементов в матрице.
P.S: Для лучшего понимания можете посмотреть это видео. Там все понятно рассказано о решений примерно такой же задачи.
Считаем кумулятивные суммы (1 проход), затем из них считаем массив средних (второй проход). Итоговая сложность будет O(N*N).
Пример реализации соответствующей функции:
// src - входная матрица
// dst - матрица, куда записать ответ
// N - размер входной матрицы
// n - половина размера окна
void MeanFilter(int **src, double **dst, int N, int n)
{
int **cumulArr = new int*[N + 1] + 1;
for (int i = -1; i < N; ++i)
{
cumulArr[i] = new int[N + 1] + 1;
memset(cumulArr[i] - 1, 0, (N + 1) * sizeof(int));
}
// Заполняем массив кумулятивных сумм
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
cumulArr[i][j] = cumulArr[i - 1][j] + cumulArr[i][j - 1] - cumulArr[i - 1][j - 1] + src[i][j];
}
}
// Считаем средние арифметические
double sq = (2*n + 1) * (2*n + 1);
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
int l = std::max(-1, i - n - 1);
int r = std::min(N - 1, i + n);
int t = std::max(-1, j - n - 1);
int b = std::min(N - 1, j + n);
dst[i][j] = (cumulArr[b][r] - cumulArr[t][r] - cumulArr[b][l] + cumulArr[t][l]) / sq;
}
}
// Удаляем память
for (int i = -1; i < N; ++i)
{
delete[] (cumulArr[i] - 1);
}
delete[] (cumulArr - 1);
}
{массив заполняется случайным образом положительными и отрицательными элементами. Находятся отрицательные элементы на главной диагонали и если они есть, то находится их сумма и количество. После этого проверяется, если есть отрицательные элементы на главной диагонали, то выдается среднее арифметическое, если нет, то на экране ответ "нет отриц"}
const
m=100;
var
a:array[1..m,1..m]of integer;
i,j,S,n,k: integer;
begin
Readln(n);
for i:=1 to n do
begin
writeln;
for j:=1 to n do
begin
a[i,j]:=random(100)-50;
write(a[i,j]:4);
end;
end;
for i:=1 to n do
if a[i,i]>0 then
begin
s:=s+a[i,i];
k:=k+1;
end;
writeln;
if k<>0 then
writeln('SR=', s/k)
else
writeln('Net <0');
end.
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Стратегії та тренди в SMM - Технології, що формують майбутнє сьогодні
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
Хочу начать дебагинг проекта, написал простенькую тестовую функцию в классе которая взаимодействует с Windows APIКонечный компютер x86
У меня есть 2 дерева представленные такой структурой подскажите идею как их можно сравнить между собой,(данные хранятся только в листах)
В классе ,в private полях есть объект другого классаУ этого объекта есть закрытые поля
Я делаю по урокуНо у меня ошибка :qrc:/Samples/Analysis/ViewshedGeoElement/ViewshedGeoElement