Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C]Нарастающий итог

Автор: breaking 3.6.2008, 22:45

Не мог бы кто-нибудь пояснить следующую задачу:
Нарастающий итог. Каждый элемент aij матрицы a(m ,n) заменить суммой элементов подматрицы a`(i, j), расположенной в левом верхнем углу матрицы a.
Конкретно меня интересует Input & Output Data.

Автор: dizzy1984 5.6.2008, 08:23

А в чем вопрос?
На входе матрица и размерности подматрицы, на выходе преобразованная матрица... Вроде все понятно...

Автор: breaking 5.6.2008, 19:15

Цитата

А в чем вопрос?

Что ж, я наверное забыл добавить - с конкретным примером...

Цитата

На входе матрица и размерности подматрицы, на выходе преобразованная матрица... Вроде все понятно...

Ок.
Input Data:
Пускай будет, банально, квадратная матрица: m = 4, n =4.
http://piccy.info/
Затем i = 2, j = 2. Левый верхний угол:
http://piccy.info/
Вопрос - каким будет Output Data??? И если можно поподробнее плиз...

Автор: dizzy1984 6.6.2008, 06:45

     1    2   3    4
A   5    6   7    8
     9  10  11 12
    13 14  15 16

sum(a'(1,1)) = 1
sum(a'(1,2)) = 1 + 2 = 3
sum(a'(1,3)) = 1 + 2 + 3 =  6
sum(a'(1,4)) = 1 + 2 + 3 + 4 = 10

sum(a'(2,1)) = 1 + 5 = 6
sum(a'(2,2)) = 1 + 2 + 5 + 6= 14
sum(a'(2,3)) = 1 + 2 + 3 + 5 + 6 + 7 = 24
sum(a'(2,4)) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36

3-я, 4-я строки аналогично.

То есть смысл : формирование подматрицы количество строк которой равно строке заменяемого элемента, количество столбцов - столбцу заменяемого элемента, и которая приклеена к левому верхнему углу исходной матрицы. Затем суммирование ее элементов.
Я предполагал, что в записи a'(i,j) i отвечает за количество строк (на сколько помню, в линейной алгебре такой порядок)

     1    3   6   10
A'  6  14  24  36
     .      .     .    .
     .      .     .    .

Автор: breaking 16.6.2008, 19:21

Спасибо dizzy1984, достаточно подробно.
По большому счету, вроде как основную идею с суммированием ухватил. Однако я все же хочу "прогнать" до конца частный случай. Опять же, я исхожу из того, что размер подматрицы a'[i,j] будет задавать пользователь(или я ошибаюсь?). И как я уже писал выше пускай i = 2 и j = 2. Затем суммируем и получаем на выходе следующую матрицу -
1 вариант:
  1   3   3    4
  6 14   7    8
  9 10 11  12
13 14 15  16
или:
2 вариант:
1   3 0 0
6 14 0 0
0   0 0 0
0   0 0 0
???
Я прав?
Думаю также  исходный массив хранить в динамической памяти, т.к. пользователь может ввести разные m и n.
А да, кстати не в курсе откуда это название - Нарастающий итог? Это что-то из области экономики?

Цитата

Я предполагал, что в записи a'(i,j) i отвечает за количество строк (на сколько помню, в линейной алгебре такой порядок)

Да все верно, даже в том же Excel если выделяешь ячейки, допустим 3х2, то будет выведено слева вверху: 3R x 2C. Тобишь,
3 rows(строки) х 2 columns(столбца).

Автор: dizzy1984 17.6.2008, 07:10

Цитата(breaking @ 16.6.2008, 21:21

)

что размер подматрицы a'[i,j] будет задавать пользователь(или я ошибаюсь?)

Когда я это говорил, я не обратил внимание на то, что индексы у рассматриваемого элемента матрицы aij обозначаются теми же буквами, что и количество строк/столбцов во временной матрице a'(i,j), но решил не исправляться, думая, что все прояснится в примере. Поэтому пользователь задает только размерности входной матрицы и ее элементы - остальное уже является просто следствием.
Соответственно, для получения выходной матрицы нужно брать не конкретные i, j а последовательно i от 0 до m-1, j от 0 до n-1 получая на каждом шаге временную a'(i, j) матрицу для подсчеты одного элемента выходной матрицы.
Ситуация с i=2 j=2 даст один элемент выходной матрицы.

     ?      ?     ?    ?
A'  ?    14     ?    ?
     ?      ?     ?    ?
     ?      ?     ?    ?