Форум программистов, компьютерный форум CyberForum.ru

Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. - C++

Восстановить пароль Регистрация
 
Hamidam
0 / 0 / 0
Регистрация: 10.04.2013
Сообщений: 6
10.04.2013, 14:39     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. #1
Здравствуйте, помогите пожалуйста, как можно сделать цикл по перемещению квадрата в матрице. Понятно, что мы должны вычитать и прибавлять столбцы и строки, но вот как ограничить этот цикл?
Вот формулировка задачи:
Дана квадратная таблица A[N,N] и число M<N. Для каждого квадрата размером MxM в этой таблице вычислить сумму
стоящих в нём чисел. Общее число действий должно быть порядка n^2. Указание сначала для каждого горизонтального прямоугольника размером MxM вычислить сумму стоящих в нём чисел. (При сдвиге такого прямоугольника по горизонтали на М нужно добавить одно число и одно вычесть) Затем используя эти суммы , вычислить суммы в квадратах. (При сдвиге квадрата по вертикали добавляется полоска, а другая полоска убавляется)
Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2013, 14:39     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел.
Посмотрите здесь:

Для матриццы размером n x m вычислить сумму элементов матрицы C++
Сгенерировать массив размером 20 на 20 из чисел от 0 до 15. Сосчитать количество повторений каждого символа. C++
C++ Дана последовательность n натуральных чисел. Для каждого числа вычислить количество его цифр и сумму этих цифр. Вывести на экран каждое число, количес
C++ Одномерный массив (Ввести массив из 10 вещественных чисел.Найти сумму чисел,стоящих на чётных местах)
Массивы. Заполнить, разбить на квадраты размером 3х3. В центре каждого квадрата поместить сумму остальных элементов квадрата C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
10.04.2013, 15:01     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. #2
Hamidam, вот Вам для начала координаты левого верхнего угла для квадрата внутри матрицы:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
 
int main() {
   
   const int N = 3;
   const int M = 2;
   
   for( int i=0; i<=N-M; ++i )
      for( int j=0; j<=N-M; ++j )
         std::cout << "Square top-left corner : (" << i << ":" << j << ")" << std::endl;
   
   return 0;
}
Hamidam
0 / 0 / 0
Регистрация: 10.04.2013
Сообщений: 6
10.04.2013, 15:15  [ТС]     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. #3
Вот код программы:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream.h>
main()
{
int n,m,i,j,**mat,s=0;
printf("vvedite razmernost'\t");
scanf("%d",&n);
printf("vvedite razmernost' kvadrata\t");
scanf("%d",&m);
mat=(int **)calloc(n,sizeof(int *));
         for(i=0;i<n;i++)
           {mat[i]=(int *)calloc(n,sizeof(int));}
for(i=0;i<n;i++)
 {
                for(j=0;j<n;j++)
                {
                                mat[i][j]=rand()%10;
                                printf("%d\t",mat[i][j]);}
                printf("\n");}
for(i=0;i<m;i++)//öèêë ñóììèðîâГ*Г*ГЁГї Г·ГЁГ±ГҐГ« Гў ГЄГўГ*äðГ*ГІГҐ
           {
                for(j=0;j<m;j++)
                {
                                s+=mat[i][j];
                                printf("\ns=%d",s);}
                                }                      
 
                                                 
for(i=0;i<m;i++)
free(mat[i]);
free(mat);
system("pause");
}
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
10.04.2013, 15:18     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. #4
Hamidam, Вам на С надо или на С++ всё же?
Hamidam
0 / 0 / 0
Регистрация: 10.04.2013
Сообщений: 6
10.04.2013, 15:18  [ТС]     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. #5
с++
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
10.04.2013, 16:08     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. #6
Цитата Сообщение от Hamidam Посмотреть сообщение
с++
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
 
int main() {
   
   using std::cout;
   using std::cin;
   using std::endl;
   
   int N, M;
   cin >> N >> M;
   
   srand(time(0));
   
   int** matrix = new int*[N];
   for( int i=0; i<N; ++i )
   {
      matrix[i] = new int[N];
      for( int j=0; j<N; ++j )
      {
         cout << (matrix[i][j] = rand() % 10) << " ";
      }
      cout << endl;
   }
   
   for( int i=0; i<=N-M; ++i )
      for( int j=0; j<=N-M; ++j )
      {
         cout << "Square top-left corner : (" << i << ":" << j << ")";
         
         int sum = 0;
         for( int k=i; k<i+M; ++k )
            for( int m=j; m<j+M; ++m )
            {
               sum += matrix[k][m];
            }
         
         cout << " Sum = " << sum << endl;
      }
   
   return 0;
}
Малость в кучу и без освобождения памяти.

Добавлено через 16 минут
Hamidam, правда сделано "в лоб". Если нужно вычислять сумму в новом квадрате на основании предыдущего, то придется переделать
stima
430 / 285 / 16
Регистрация: 22.03.2011
Сообщений: 929
Завершенные тесты: 1
10.04.2013, 16:41     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. #7
Кликните здесь для просмотра всего текста

Цитата Сообщение от Tulosba Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
 
int main() {
   
   using std::cout;
   using std::cin;
   using std::endl;
   
   int N, M;
   cin >> N >> M;
   
   srand(time(0));
   
   int** matrix = new int*[N];
   for( int i=0; i<N; ++i )
   {
      matrix[i] = new int[N];
      for( int j=0; j<N; ++j )
      {
         cout << (matrix[i][j] = rand() % 10) << " ";
      }
      cout << endl;
   }
   
   for( int i=0; i<=N-M; ++i )
      for( int j=0; j<=N-M; ++j )
      {
         cout << "Square top-left corner : (" << i << ":" << j << ")";
         
         int sum = 0;
         for( int k=i; k<i+M; ++k )
            for( int m=j; m<j+M; ++m )
            {
               sum += matrix[k][m];
            }
         
         cout << " Sum = " << sum << endl;
      }
   
   return 0;
}
Малость в кучу и без освобождения памяти.

Добавлено через 16 минут
Hamidam, правда сделано "в лоб". Если нужно вычислять сумму в новом квадрате на основании предыдущего, то придется переделать


Решение не правильно. Требуемая сложность О(2), а у Вас О(4) и куча ошибок.
Но в свою очередь условие не корректно. Для составление правильной итерации нужно точно знать как двигаться по матрице со сдвигом на 1 (т.е. для каждого квадрата) или со сдвигом на размер квадрата (то что указано в "указании"). И что вообще значит это указание? Решить так и не как иначе?
Hamidam
0 / 0 / 0
Регистрация: 10.04.2013
Сообщений: 6
10.04.2013, 16:52  [ТС]     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. #8
Цитата Сообщение от stima Посмотреть сообщение
Кликните здесь для просмотра всего текста




Решение не правильно. Требуемая сложность О(2), а у Вас О(4) и куча ошибок.
Но в свою очередь условие не корректно. Для составление правильной итерации нужно точно знать как двигаться по матрице со сдвигом на 1 (т.е. для каждого квадрата) или со сдвигом на размер квадрата (то что указано в "указании"). И что вообще значит это указание? Решить так и не как иначе?
Указание было дано вместе с текстом самой задачи. Как я понял совершенно не обязательно выполнять как там написано, это что то типа подсказки.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2013, 16:53     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел.
Еще ссылки по теме:

C++ Заполнить матрицу случайными числами. Разбить матрицу на квадраты размером 3х3. В центре каждого квадрата поме
Задан массив a{ij} размерности MxM. Требуется вычислить C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
10.04.2013, 16:53     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. #9
stima, про сложность добавил в комментарии. Только вот, говоря про сложность, следовало бы писать O(n^2), O(n^4), а не O(2), O(4). Потому что иначе это константная сложность.
Цитата Сообщение от stima Посмотреть сообщение
и куча ошибок.
Укажите где.
Yandex
Объявления
10.04.2013, 16:53     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел.
Ответ Создать тему
Опции темы

Текущее время: 17:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru