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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Hamidam
0 / 0 / 0
Регистрация: 10.04.2013
Сообщений: 6
#1

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

10.04.2013, 14:39. Просмотров 778. Ответов 8
Метки нет (Все метки)

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

Сгенерировать массив размером 20 на 20 из чисел от 0 до 15. Сосчитать количество повторений каждого символа. - C++
Всем здорово!Помогите пожалуйста с программами завтра рубежка...(на turbo C,не С++),если можно пожалуйста объясните,или закомментируйте. ...

Вычислить сумму чисел последовательности, стоящих в позициях, являющихся простыми числами - C++
Добрый день, можете помочь с задачей. Нужно написать программу через функцию. Что то не совсем разобралась... Дана последовательность из...

Для каждого элемента напечатать количество положительных и отрицательных чисел, стоящих перед ним - C++
Для каждого элемента напечатать в отдельной строке количество положительных и отрицательных чисел, стоящих перед ними #include...

Задан массив a{ij} размерности MxM. Требуется вычислить - C++
S=\sum_{i=1}^{M}\sum_{j=1}^{M}\left|a{ij} \right|

Минимальный размер квадрата для размещения в нём N одинаковых прямоугольников - C++
Добрый вечер, не могу решить вот такую задачку: Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике...

Для матриццы размером n x m вычислить сумму элементов матрицы - C++
Условия этой задачи (задача одна), таковы: Для матриццы размером n x m вычислить сумму элементов матрицы. Умножить на это число...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
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
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
10.04.2013, 15:18     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. #4
Hamidam, Вам на С надо или на С++ всё же?
Hamidam
0 / 0 / 0
Регистрация: 10.04.2013
Сообщений: 6
10.04.2013, 15:18  [ТС]     Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел. #5
с++
Tulosba
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
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
455 / 304 / 23
Регистрация: 22.03.2011
Сообщений: 990
Завершенные тесты: 2
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 в этой таблице вычислить сумму стоящих в нём чисел.
Еще ссылки по теме:

Вычислить сумму каждого i-го из введённых чисел со всеми предшествующими ему числами - C++
Здравствуйте,у меня вопрос,решал задачу,суть её в том что считываются 6 чисел потом необходимо узнать сумму каждого числа со всеми числами...

Дана последовательность из 7 различных чисел. Вычислить сумму каждого элемента последовательности с предыдущими элементами - C++
Дана последовательность из 7 различных чисел. Вычислить сумму каждого элемента последовательности с предыдущими элементами.

Требуется для каждого положения “окна” определить минимум в нём - C++
помогите пожалуйста решить задачу Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается “окно” длины K, то...

Требуется для каждого положения “окна” определить минимум в нём - C++
Здрвствуйте, есть ли в стандартных библотеках функция типа make_heap, но наоборот, чтобы куча была от меньшего к большему, нужно для...


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

Или воспользуйтесь поиском по форуму:
Tulosba
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
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 в этой таблице вычислить сумму стоящих в нём чисел.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru