|
|
|
|
Канал Игры Мечты: «Алгоритмы - кирпичики Игры Мечты» |
|
|
|
Dark Archon
 231 EGP
  
Репутация: 56
Сообщения: 389
Откуда: Moscow Federation
Зарегистрирован: 27.05.2004
  |
|
Окно N от N+1 сдвинуто всего на одно измерение, значит если окно имеет размер M измерений, то одновременно обрабатывается M таких окон, так как M окон пересекаются. В связи с чем я предложил подсчитывать М НЧ, по одному на каждое одновременно подсчитываемое окно. Сложность - О(N*M) где N число замеров в потоке, а M - размер окна и количество счетчиков. Ясно, что чем меньше M - тем лучше.
Если я правильно понял про алфавит, то (a^14)bb выводится из (a^13)bаbа по первой формуле. (но у меня впечатление, что я не правильно понял...)
_________________
o
_/0\_
< > КУ! |
|
|
|
Krom
455 EGP
  
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
| Dark Archon : |
|
Сложность - О(N*M) где N число замеров в потоке, а M - размер окна и количество счетчиков.
|
Можно эффективнее. Можно обойтись меньшим количеством сравнений на каждом шагу. А обработку можно сделать за N*log(M). (Какая подсказка!  )
| Dark Archon : |
|
Если я правильно понял про алфавит, то (a^14)bb выводится из (a^13)bаbа по первой формуле. (но у меня впечатление, что я не правильно понял...)
|
Угу, неправильно. Выводить надо из аксиомы, а это abb. Попробуй, но только чур - за указанное время. Иначе непонятна цель постановки такой задачи.
_________________
Не спешите меня. |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
Ещё задача:
Найдите сумму квадратов чисел от 1 до 2005, не используя операцию умножения 
P.S> Разумеется, возведение в степень и логарифмирование(из-за погрешностей вычислений итог будет не целым, что есть бред) тоже использовать нельзя.
_________________
Не спешите меня. |
|
|
|
Shirson
1605 EGP
   
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
А операцию ^ ? 
_________________
У меня бисера не доxеpа. |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
| Shirson : |
|
А операцию ^ ?
|
Обижаешь! 
Только балет и керамика... Э... Сгинь, Масяня. Операция "+". Больше ничего не нужно.
_________________
Не спешите меня. |
|
|
|
Crimson
560 EGP
Рейтинг канала: 4(83)
Репутация: 130
Сообщения: 3041
Зарегистрирован: 03.09.2003
|
|
Элементарно
int sum=0;
for (int i=1; i<2005; i++)
for (int c=0; c<i; c++)
sum+=i;
К скорости работы алгоритма претензий не предъявлять
|
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
| Crimson : |
Элементарно
int sum=0;
for (int i=1; i<2005; i++)
for (int c=0; c<i; c++)
sum+=i;
|
Именно!
_________________
Не спешите меня. |
|
|
|
Crimson
560 EGP
Рейтинг канала: 4(83)
Репутация: 130
Сообщения: 3041
Зарегистрирован: 03.09.2003
|
|
Это медленно, а не именно.
int sum=3;
for (int i=3, i<=2005, i++)
{ int x=i/2; x+=x; sum+=i<<x; if (i%2) sum+=i; }
А вот это пожалуй уже именно
|
|
|
|
Sh.Tac.
151 EGP
Рейтинг канала: 5(108)
Репутация: 14
Сообщения: 1426
Зарегистрирован: 27.07.2005
|
|
ага, <мечтательно> ... вот если бы в регистрах компа умножение и возведение производилось суммированием ...
_________________
This is what you get ...
(c) Radiohead |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
Sh.Tac.:
А не работаешь ли ты менеджером?
http://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD594.html
_________________
Не спешите меня. |
|
|
|
Crimson
560 EGP
Рейтинг канала: 4(83)
Репутация: 130
Сообщения: 3041
Зарегистрирован: 03.09.2003
|
|
| Crimson : |
|
А вот это пожалуй уже именно
|
Не, стоп, гоню.
int sum=3;
for (int i=3, i<=2005, i++)
{ int x=1; while(i>>x) x++; sum+=i<<x; if (i%2) sum+=i; }
Вроде так 
|
|
|
|
Sh.Tac.
151 EGP
Рейтинг канала: 5(108)
Репутация: 14
Сообщения: 1426
Зарегистрирован: 27.07.2005
|
|
| Krom : |
|
А не работаешь ли ты менеджером?
|
вот ещё, я оопер, поэтому меня раздражает возня с цифирями и алгоритмами
_________________
This is what you get ...
(c) Radiohead |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
| Crimson : |
| Crimson : |
|
А вот это пожалуй уже именно
|
Не, стоп, гоню.
|
Да, гонишь. Ответ неправильный.
_________________
Не спешите меня. |
|
|
|
Crimson
560 EGP
Рейтинг канала: 4(83)
Репутация: 130
Сообщения: 3041
Зарегистрирован: 03.09.2003
|
|
А и хрен с ним
Хотя... пожалуй, там надо while(i<<x!=i%2)  Но проверять ломает...
|
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
Как вычислить ЦМ объекта?
Интересует оптимальное решение для двух случаев:
1. Объект представляет собой матрицу 2D из квадратных "кирпичиков" разной массы [0,∞[
Размеры матрицы не жёстки. Расстояния между центрами кирпичиков одинаковы.
2. Объект состоит из набора блоков, каждый из которых описан массой и координатами 2D.
Это не загадка, это вопрос.
_________________
У меня бисера не доxеpа. |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
Стандартное решение не устраивает? Единоразовый акт для постоянной конфигурации объекта: берём сумму произведений радиус-вектор элемента на его массу по всем элементам и делим на суммарную массу.
По времени линейно и быстрее быть не может
_________________
Не спешите меня. |
|
|
|
Crimson
560 EGP
Рейтинг канала: 4(83)
Репутация: 130
Сообщения: 3041
Зарегистрирован: 03.09.2003
|
|
Насколько я помню, ЦМ рассчитывается как (m1x1+m2x2+...+mnxn)/(m1+m2+...+mn). Хоть убей не представляю, как это можно сделать оптимальнее, чем в лоб 
Единственное, что приходит в голову - если система не жесткая, то можно хранить числитель и знаменатель отдельными значениями. Тогда при смещении одной частицы из верхней части вычитается старое m*x, плюсуется новое и делится на фиксированный знаменатель. Не уверен, что оптимизация будет особо звездная, но больше вообще ничего в голову не приходит.
По поводу матрицы кирпичиков подумаю. Хотя если честно не уверен что правильно понял о чем вообще шла речь. Да и само использование матрицы... не проще два вектора использовать?
|
|
|
|
Shirson
1605 EGP
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
Радиус вектор ОТ ЧЕГО? Всмысле каждый с каждым? Уууу.....
_________________
У меня бисера не доxеpа. |
|
|
|
Rattlemouse
85 EGP
Репутация: 2
Сообщения: 74
Откуда: Москва
Зарегистрирован: 03.11.2003
|
|
По поводу первого пункта: можно немного черезж... оптимизовать но максимум раза в два... если пройтись по главной диагонали основного минора матрицы, то можно сократить на умножениях равноудаленных квадратов относительно элементов диагонали вправо и вниз
Остатки матрицы можно рекурсивно поразбивать на диагонали...
Вопрос в том, что векторное перемножение как то на ЦП быстрее делатся будет, ибо железные оптимизации и т.п.
Второй пункт можно избавится от одного умножения, приведя массовый коэффициенты по m_1
[/code]
_________________
мы все умрём...
и нажмём на Load ;) |
|
|
|
Crimson
560 EGP
Рейтинг канала: 4(83)
Репутация: 130
Сообщения: 3041
Зарегистрирован: 03.09.2003
|
|
| Shirson : |
|
Радиус вектор ОТ ЧЕГО? Всмысле каждый с каждым? Уууу.....
|
Вектор - это в смысле одномерный массив В каждой ячейке писать массу, двигать отниманием в одном месте и добавлением в другое. Отдельно для координат по X и по Y.
|
|
|
|
|
|
|
|
|
Канал Игры Мечты: «Алгоритмы - кирпичики Игры Мечты» |
|
|
