0

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

}
2
  • 3
    Что за балет? С чего бы это ответ устарел?
    – MBo
    29 апр 2019 в 20:35
  • Так а в чем проблема? Что то не работает? Что именно?
    – Oliort UA
    6 мая 2019 в 1:04

4 ответа 4

5

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

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]
3
  • formul = n*2+1 это есть сторона квадрата под-матрицы
    – Gab.Vad
    4 апр 2019 в 19:36
  • ОК, добавил....
    – MBo
    4 апр 2019 в 19:42
  • @Gab.Vad Получилось?
    – MBo
    5 апр 2019 в 5:34
3

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

3
+25

Считаем кумулятивные суммы (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);
}
5
  • Красиво :) Только косяк - среднее арифметическое должно быть немного не интом.
    – Qwertiy
    30 апр 2019 в 22:43
  • Согласен) Но в инты у меня пишутся суммы, а среднее всё-таки в double (входной параметр dst) Зато есть другой косячок - деление там целочисленное, сейчас поправлю это (наверное его вы и имели ввиду кстати...).
    – zcorvid
    1 мая 2019 в 7:12
  • Ага, теперь правильно. Да, я обратил внимание на деление двух интов, а на тип параметра как-то не посмотрел.
    – Qwertiy
    1 мая 2019 в 8:47
  • А вот теперь я нашёл действительно опасный косяк, в мемсете memset(cumulArr[i] - 1, 0, (N + 1) * sizeof(int)); не было -1 у указателя, первый столбец кумулятивных сумм в итоге не занулялся... Что забавно - когда я отлаживался, этот косяк не вылез, повезло попасть на занулённую память... Отлаживаться в debug-сборке чревато...
    – zcorvid
    6 мая 2019 в 10:58
  • Я так один раз читал память где-то в районе индекса 2e6 при размере массива около 1e6. И в дебаге всё работало отлично, потому что там всегда оказывались нули, которые мне и были нужны. А вот в релизе программа просто зацикливалась. Как же мы это искали, особенно при том, что VS2010 не показывает локальные переменные в релизе, если это примитивы, а не вектора какие-нибудь (((
    – Qwertiy
    6 мая 2019 в 11:06
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.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.