Как заменить каждый элемент матрицы на среднее арифметическое?

156
11 января 2020, 08:50

Дана квадратная матрица и число 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;
    }
}
Answer 1

Чтобы приведённый код хоть как-то заработал, стоит для начала вынести инициализацию суммы и количества элементов вне внутренних циклов

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]
Answer 2

Пожалуй самый быстрым и красивым вариантом будет - простое ДП (Динамическое Программирование). Сначало мы предпосчитаем для каждой ячейки суммы элементов которые лежат с самого левого верхнего угла до самой ячейки. Эти значения будем хранить в двумерном массиве 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: Для лучшего понимания можете посмотреть это видео. Там все понятно рассказано о решений примерно такой же задачи.

Answer 3

Считаем кумулятивные суммы (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);
}
Answer 4

{массив заполняется случайным образом положительными и отрицательными элементами. Находятся отрицательные элементы на главной диагонали и если они есть, то находится их сумма и количество. После этого проверяется, если есть отрицательные элементы на главной диагонали, то выдается среднее арифметическое, если нет, то на экране ответ "нет отриц"}

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.
READ ALSO
Ошибка компиляции No Target Architecture

Ошибка компиляции No Target Architecture

Хочу начать дебагинг проекта, написал простенькую тестовую функцию в классе которая взаимодействует с Windows APIКонечный компютер x86

138
C++ Сравнить два N-арных дерева

C++ Сравнить два N-арных дерева

У меня есть 2 дерева представленные такой структурой подскажите идею как их можно сравнить между собой,(данные хранятся только в листах)

138
Проблема с методами доступа к private полям;

Проблема с методами доступа к private полям;

В классе ,в private полях есть объект другого классаУ этого объекта есть закрытые поля

114
Как регистрировать С++ классы для QML? module &ldquo;&rdquo; version 0.1 is not installed

Как регистрировать С++ классы для QML? module “” version 0.1 is not installed

Я делаю по урокуНо у меня ошибка :qrc:/Samples/Analysis/ViewshedGeoElement/ViewshedGeoElement

147