Алгоритм двойной суммы

[guest001]

Привет всем

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

Например

А)


+ её доказательство


при $a_i_k \leq 3$

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

Хелп

[venco]

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

[guest001]

Спасибо за быстрый ответ :)

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

-- Пт сен 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;
         }
       }
      }

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

[venco]

В целом правильно, но есть несколько замечаний.

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

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

guest001 в сообщении #355692 писал(а):

при $a_i_k \leq 3$

Вот это условие не соответствует программе. По идее, надо суммировать те элементы, что меньше трёх, а у Вас проверяется сумма.

[guest001]

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

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

[venco]

А это вообще несуразица. Исходная задача у Вас словами написана или формулой?

-- Чт сен 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$

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

[guest001]

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 --

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

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


при

?

[guest001]

Тут вроде тоже примерно понятно, но вот эта форма записи не пойму как её перевести

$\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$

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


Хелп

[Circiter]

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$, то надо суммирование либо начинать с единицы, либо заканчивать значением, на единицу меньшим максимального (т.е. в вышеприведенном примере в этом случае неравенства типа <= должны быть заменены на <).

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

[guest001]

Цитата:

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

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

[Circiter]

2guest001

Цитата:

но только движение в приведенном коде идет слева направо, а не сверху вниз, как заведено в матрицах

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