2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Алгоритм двойной суммы
Сообщение24.09.2010, 02:27 
Привет всем :-)

Интересно стало перевести несколько формул на С++.
Но некоторые меня поставили в затруднение.

Например

А)
Изображение

+ её доказательство
Изображение

при $a_i_k \leq 3$

Помогите понять как переводить двойную сумму на С++? Ну или любой др ЯП, только на примере массивов плз :-)

Хелп

 
 
 
 Re: Алгоритм двойной суммы
Сообщение24.09.2010, 02:35 
Пишите двойной цикл.
Во внутреннем считайте внутреннюю сумму (по i), а во внешнем суммируйте полученные внутренние суммы в S. А можно и сразу всё в S складывать.
Вообще не понятно, в чём у Вас проблема?

 
 
 
 Re: Алгоритм двойной суммы
Сообщение24.09.2010, 02:40 
Спасибо за быстрый ответ :)

Я запутался в последовательности вычисления суммы. Доказательство как бы говорит, что нужно суммировать крест накрест типа, но не понял честно говоря. Это что в два этапа как -то делать нужно :-(

-- Пт сен 24, 2010 03:52:26 --

вот кое-что написал, но просто именно двойную сумму не перекладывал, потому не уверен приведет ли мой алгоритм к нужному эффекту

То есть идея такая, что есть два двумерных массива G и K (матрицы). Интересно подсчитать "двойную сумму" матрицы K и привязать ещё условие при котором если $ \sum K_i_j \leq 3$ то $ K_i_j=1$

Код:
for (int j = 0; j < G[G.length - 1].length; j++) {
       for (int i = 0; i < G.length; i++) {
         sum1 += K[i][j];
         if (sum1 <= 3) {
           K[i][j] = 1;
         }
       }
      }


Немного заморочился с индексами. Помогите плз

 
 
 
 Re: Алгоритм двойной суммы
Сообщение24.09.2010, 03:02 
В целом правильно, но есть несколько замечаний.

1. Почему суммируете K, а размеры берёте у G? Конечно, если у матриц размеры одинаковые, то ошибки не будет, но всё равно - непорядок.
2. В таком порядке суммировать неэффективно для мало-мальски больших матриц. Для лучшей работы кеша надо во внутреннем цикле пробегать самый последний индекс массива. Естественно, если по алгоритму надо именно так, как у Вас сейчас, то придётся смириться, или как-то дополнительно ухищряться.
3. Ещё для скорости я бы взял размеры в отдельные переменные, а не брал из массива в цикле.

-- Чт сен 23, 2010 20:05:37 --

guest001 в сообщении #355692 писал(а):
при $a_i_k \leq 3$
Вот это условие не соответствует программе. По идее, надо суммировать те элементы, что меньше трёх, а у Вас проверяется сумма.

 
 
 
 Re: Алгоритм двойной суммы
Сообщение24.09.2010, 03:16 
попробую проиллюстрировать оригинальную идею.
Запутала форма записи как:
$K_i_j=1$ если
$\sum_{i}^{m} \sum_{j}^{n}(K_i_j \leq 3)$

Вот примерно так... это и пытаюсь переложить. :oops: поправьте если что - нужен ваш свежий взгляд

 
 
 
 Re: Алгоритм двойной суммы
Сообщение24.09.2010, 03:23 
А это вообще несуразица. Исходная задача у Вас словами написана или формулой?

-- Чт сен 23, 2010 20:26:53 --

guest001 в сообщении #355701 писал(а):
$K_i_j=1$ если
$\sum_{i}^{m} \sum_{j}^{n}(K_i_j \leq 3)$
Если убрать скобки:
Цитата:
$K_i_j=1$ если
$\sum_{i}^{m} \sum_{j}^{n}K_i_j \leq 3$
то появляется смысл: присвоить всем элементам единицу, если сумма не больше трёх. Может так и надо?

 
 
 
 Re: Алгоритм двойной суммы
Сообщение24.09.2010, 03:32 
venco в сообщении #355702 писал(а):
А это вообще несуразица. Исходная задача у Вас словами написана или формулой?


Вперемешку :?

Есть массив G (заполнен) размер A на B
Есть массив K (так же заполнен)
Интересно найти такой массив K что:
Изображение
если
Изображение

m,n - A,B в смысле, но суть та же :-)

-- Пт сен 24, 2010 04:41:04 --

Цитата:
о появляется смысл: присвоить всем элементам единицу, если сумма не больше трёх. Может так и надо?

думаю, что так :-)

то есть инициализировать как $K_i_j$=1 до пределов суммы <=3? Всей двойной суммы или как?
Я вот думаю... тот алгоритм, что я написал он считает сумму всех элементов массива по столбцам, а нужно ли ещё ряды пересчитывать?
Потому что я смотрю на доказательство формулы и там как бы сначала сверху вниз суммируется (столбцы), потом справа - налево суммируется (ряды)... А потом... честно говоря сбился немного - помогите точно понять линейность вопроса...

-- Пт сен 24, 2010 04:55:00 --

вот эта запись

$\sum_{i=0}^{m} K_i_j \leq b_i$ при $(1\leq i \leq B)$

и эта
$\sum_{i}^{m}\sum_{j}^{n} K_i_j \leq 3$

Это нужно разную тактику применять получается?

-- Пт сен 24, 2010 05:07:37 --

А нет - стоп-с... пригляделся точнее... только сверху вниз суммирование матрицы дано как доказательство :lol: тогда вроде мой код более менее что-то делает :lol:

А вот какая тактика с этим видом суммы тогда если b - это одномерный массив длиной В

Изображение
при Изображение

?

 
 
 
 Re: Алгоритм двойной суммы
Сообщение24.09.2010, 05:35 
Тут вроде тоже примерно понятно, но вот эта форма записи не пойму как её перевести

$\sum_{i=0}^{A} b_i \sum_{j=0}^{B} K_i_j$

это получается типа такая запись

$\sum_{i=0}^{A} \sum_{j=0}^{B} b_i K_i_j$

Как такую красоту перевести?


Хелп

 
 
 
 Re: Алгоритм двойной суммы
Сообщение02.10.2010, 05:39 
2guest001
Цитата:
$\sum\limits_{i=0}^A\sum\limits_{j=0}^B\ b_i K_{ij}$

Как такую красоту перевести?


Просто сигмы заменяете на for'ы, нижние индексы на индексы в скобках [...], и т.д.:

Используется синтаксис C
int Sum=0;

for(int i=0; i<=A; i++)
    for(int j=0; j<=B; j++)
        Sum+=b[i]*K[i][j];
 


N.B.: Это для суммирования от $0$ до $A$ и от $0$ до $B$. Если обрабатывается матрица $A\times B$, то надо суммирование либо начинать с единицы, либо заканчивать значением, на единицу меньшим максимального (т.е. в вышеприведенном примере в этом случае неравенства типа <= должны быть заменены на <).

В исходном же вашем сообщении (и во всех уточняющих его пояснениях) какой-то бред, извините. Если задачу дал вам преподаватель, то потребуйте задание снова в более аккуратном виде.

 
 
 
 Re: Алгоритм двойной суммы
Сообщение03.10.2010, 03:41 
Цитата:
В исходном же вашем сообщении (и во всех уточняющих его пояснениях) какой-то бред, извините. Если задачу дал вам преподаватель, то потребуйте задание снова в более аккуратном виде.

Нет, это не задание. Это простой интерес в переводе той или иной математической записи. Нет цели, что-то вот сейчас решить и все, но наоборот поразмыслить над разными вариантами. Это чисто для меня самого...
А насчет вложенного цикла, то это понятно, но только движение в приведенном коде идет слева направо, а не сверху вниз, как заведено в матрицах :wink: Но в принципе вполне можно переставить циклы по уровням :-)

 
 
 
 Re: Алгоритм двойной суммы
Сообщение03.10.2010, 03:52 
2guest001
Цитата:
но только движение в приведенном коде идет слева направо, а не сверху вниз, как заведено в матрицах

Если под "движением вниз" подразумевать перечисление строк с первой до последней, а под первым (самым левым) индексом понимать именно номер строки, то этот код соответствует именно движению вниз (матрица сканируется построчно внешним циклом по первому индексу, а уже во вложенном цикле по второму индексу обрабатывается конкретная строка, "слева направо"). :)

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group