|
|
|
|
Канал Игры Мечты: «Алгоритмы - кирпичики Игры Мечты» |
|
|
|
Shirson
 1605 EGP
     
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
  |
|
Речь шла про радиус-вектор.
Вобщем всё понятно. В приватке Sprite вопрос развернул по полной, буду подумать 
_________________
У меня бисера не доxеpа. |
|
|
|
Crimson
560 EGP
Рейтинг канала: 4(83)
Репутация: 130
Сообщения: 3041
Зарегистрирован: 03.09.2003
|
|
Начались шушуканья по приваткам...  Спрайтыч, выкладывай все на здесь, будем подумать оба 
|
|
|
|
Krom
455 EGP
 
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
Ну что ж, по просьбам трудящихся привожу тот алгоритм решения задачи о срезе окна, который является авторским:
Данные разбиваются на несколько опорных окон, соприкасающихся границами. В каждом окне находится максимальное значение, номер которого сохраняется отдельно. Таким образом, найдено первое выходное значение (и несколько дальнейших, но это пока несущественно). При сдвиге на один элемент значение добавленного элемента сравнивается с максимальным опорного окна, при условии что тот из-за сдвига не вышел за границы окна. Если элемент не вышел за границу, максимум в окне определяется сравнением этих двух элементов, иначе производится поиск нового максимума. Таким образом, полный поиск по окну делается не чаще, чем максимальный элемент выходит за его границу при сдвиге. В среднем такое решение имеет сложность n*log(n), наихудший случай не может быть хуже n^2 (пожалуй, монотонное убывание элементов массива - как раз нужный случай).
Ну, и эксперимент на тему искусственного интеллекта:
http://ai.obrazec.ru/aiversus.htm
_________________
Не спешите меня. |
|
|
|
Krom
455 EGP
Рейтинг канала: 1(3)
Репутация: 159
Сообщения: 1988
Откуда: Горы Урала
Зарегистрирован: 19.07.2005
|
|
По следующей задаче просто не могу найти ссылку на алгоритм, хотя точно где-то видел.
Задача: требуется найти минимальное число сфер заданного радиуса, покрывающее данное множество точек. Сферы не обязательно центруются на точках из множества.
_________________
Не спешите меня. |
|
|
|
Digited
271 EGP
 
Рейтинг канала: 4(99)
Репутация: 49
Сообщения: 932
Зарегистрирован: 24.08.2004
|
|
Хотелось бы создать физдвижок планетария (С++), расчитывающего гравитационное взаимодействие заданных небесных тел и меняющего их траектории и скорости в соответствии с законами физики. (Визуализатор уже есть).
Данные: Звезда (в начале трехмерных координат) - масса, радиус
Планеты, спутники: масса, радиус, начальный вектор скорости.
Проблема в том, что не знаю, как, не перегружая средний комп частотой вычислений, создать точные универсальные формулы-алгоритмы.
Нужна помощь (совет, полезная ссылка).
(Пока безрезультатно терроризирую поисковики и спрашиваю по форумам)
|
|
|
|
L'osheg
1080 EGP
Рейтинг канала: 1(6)
Репутация: 227
Сообщения: 6068 Предупреждений: 1
Откуда: Texasкие мы...
Зарегистрирован: 25.04.2003
|
|
Ищи в по каналу. Вычислительными средствами рассчитывать траектории орбит планет/астероидов нереально - из-за числовых погрешностей устойчивых орбит не создать. Легче и душевнее делать "жосткие орбиты" (типа "эллиптические рельсы") и гонять крупные тела по этим рельсам.
_________________
Тооолстый тролль с нулевой кривизной дна |
|
|
|
Crimson
560 EGP
Рейтинг канала: 4(83)
Репутация: 130
Сообщения: 3041
Зарегистрирован: 03.09.2003
|
|
Если коротко, то никак. Для системы более чем из двух тел аналитическое решение на данный момент неизвестно никому. Соответственно, остается только численное моделирование, которое умеет быть либо быстрым, либо точным. Если мозговое либидо в тонусе, можно для повышения точности использовать метод Ронге-Кутта или его модификации. Ну и ессно если массы тел различаются на несколько порядков, то на притяжение более массивного к менее массивному. Хотя если учесть, что Плутон в позапрошлом веке (!) обнаружили по возмущениям, вносимым им в орбиту Урана (!!) - я даже не знаю...
|
|
|
|
Digited
271 EGP
Рейтинг канала: 4(99)
Репутация: 49
Сообщения: 932
Зарегистрирован: 24.08.2004
|
|
| L'oshek : |
|
Вычислительными средствами рассчитывать траектории орбит планет/астероидов нереально - из-за числовых погрешностей устойчивых орбит не создать.
|
Жаль... Весьма жаль. Ну что ж, будем делать жёстко.
А это "жостко" хотя бы проверить на устойчивость можно? - Crimson, расскажите, пожалуйста, поподробнее про "точно". Интересуют эксцентриситеты и вообще нестандартные орбиты. Материала что-то мало находится. Нужна помощь...
|
|
|
|
Crimson
560 EGP
Рейтинг канала: 4(83)
Репутация: 130
Сообщения: 3041
Зарегистрирован: 03.09.2003
|
|
Дык, элементарно же, Ватсон - чем меньше шаг, тем точнее По методу Рунге(а не Ронге - mea culpa)-Кутта - например здесь можно почитать, также Рамблером неплохо ищется...
По поводу "эксцентрисетов и вообще нестандартных орбит"... ну во-первых эксцентрисет это не орбита, а ее характеристика - при e=0 орбита круговая, 0<e<1 - эллиптическая, e=1 это парабола, e>1 - гипербола. Это то, что получается когда тел меньше трех. Когда их больше - орбиты превращаются в малопредсказуемый бардак, где относительно стабильными бывают только частные случаи - как к примеру Янус-Эпиметей или Телесто-Тетис-Калипсо в системе спутников Сатурна, которые "живут" в точках Лагранжа друг друга. Есть еще такие вещи как резонансы, которые тоже бывают "условно-стабильными"... была где-то в КТВ ссылка про них, найду - запощу. Пока могу послать на базовую информацию к размышлению - http://hea.iki.rssi.ru/~nick/astro/index.html
|
|
|
|
spSerg
145 EGP
Репутация: 36
Сообщения: 732
Откуда: 49"34'N 25"36'E 324H
Зарегистрирован: 29.11.2004
|
|
| Krom : |
Ну что ж, по просьбам трудящихся привожу тот алгоритм решения задачи о срезе окна, который является авторским:
Данные разбиваются на несколько опорных окон, соприкасающихся границами. ... В среднем такое решение имеет сложность n*log(n), наихудший случай не может быть хуже n^2 (пожалуй, монотонное убывание элементов массива - как раз нужный случай).
|
Вообще-то известно малость иное решение (к сожалению, не я придумал):
Пусть у нас имеется стек, в котором помимо операций с ВЕРХНИМ элементом, добавлены операции доступа (просмотра и удаления) к НИЖНЕМУ элементу стека. Реализовать такую структуру несложно.
Каждый элемент стека имеет НОМЕР и ВЕС.
В начальный момент времени стек пуст.
Будем считать, что в первый момент времени в окне пусто. Затем в течение m "сдвигов" в окно добавляется по одному числу, а в дальнейшем при каждом сдвиге одно число добавляется, а одно исчезает.
Тогда при каждом сдвиге окна
1. Если НОМЕР нижнего элемента стека равен номеру числа, которое исчезло из окна, удалить этот элемент из стека
2. Создать новый элемент X, номер которого равен порядковому номеру числа, появившегося в окне, а вес - это значение числа, которое появилось в окне
3. WHILE (стек не пуст и ВЕС верхнего элемента стека меньше ВЕСА элемента X) { удалить верхний элемент стека }
4. Поместить элемент Х на верх стека
5. Искомый максимум - это вес нижнего элемента стека
Итого, для последовательности длины n будет сделано n вставок в стек, n удалений из стека и не более 2n сравнений.
Итого, представленный алгоритм имеет сложность O(n)
_________________
Демократия - это когда два волка и овца большинством голосов решают, что у них будет на ужин... |
|
|
|
TpuCTaH
63 EGP
Рейтинг канала: 1(4)
Репутация: 8
Сообщения: 128
Откуда: Харьков
Зарегистрирован: 12.06.2006
 |
|
Есть двумерный массив int arr[N][N]
описать алгоритм заполнения масива
| Код: |
1.
1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 1
1 2 3 3 3 3 3 2 1
1 2 3 4 4 4 3 2 1
1 2 3 4 5 4 3 2 1
1 2 3 4 4 4 3 2 1
1 2 3 3 3 3 3 2 1
1 2 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1 1
2.
1 2 3 4 5 6 7 8
28 29 30 31 32 33 34 9
27 48 49 50 51 52 35 10
26 47 60 61 62 53 36 11
25 46 59 64 63 54 37 12
24 45 58 57 56 55 38 13
23 44 43 42 41 40 39 14
22 21 20 19 18 17 16 15
|
|
|
|
|
Jurec
348 EGP
Рейтинг канала: 4(76)
Репутация: 102
Сообщения: 1441 Заблокирован
Откуда: Seattle
Зарегистрирован: 25.02.2006
|
|
Оживим-с ветку. Вот подборочка задач:
1)Счастливый билет.
Есть шестизначный билет в троллейбусаг. Нужно определить является ли данный билет счастливым.
Какие билеты называются счастливыми?
Есть следующий алгоритм:
-Загадывается чило К (целое).
-Делается попытка сложить из 6 цифр билета это число К. Делается это следующим образом:
-1.Номер билета разбивается на цифры и некоторые соседние цифры объединяют в числа
-2.Между полученных чисел расставляют скобки и знаки операций:плюс,минус,умножение,деление.
-3.Нельзя менять местами цифры
-4.Если получается такое выражение, которое после расчетов дает К, то былет является счасливым.
Операцию разделить можно применять, если результатом будет целое число.
Пример: есть билет №182836. К=840. Разобьем число на четыре: 1, 8, 2, 836. Число К получается так: 1*(8/2+836)=840.
Написать программу, которая по номеру билета и числу К определит, является ли номер счастливым и найдет один из вариантов разбиения номера на последовательность чисел, между которыми можно расположить математические операции и скобки для получения искомого числа К.
2)Делители
По заданному натуральному числу N необходимо вычеслить число натуральных чисел, которые есть делителями N! (факториал числа N).
Например, при N=4, N!=4*3*2*1=24. Это число имеет следующие делители:1,2,3,4,6,8,12,24. Таким образом искомое кол-во составляет 8.
Написать программу, которая по натуральному N, находит количество делителей его факториала.
Ах, да ограничение времени. В первой задаче, пусть 600 мс, во второй 300мс. (На самом деле ограничения пожесче)
_________________
MOV topka, C++ |
|
|
|
TpuCTaH
63 EGP
Рейтинг канала: 1(4)
Репутация: 8
Сообщения: 128
Откуда: Харьков
Зарегистрирован: 12.06.2006
|
|
Страница на википедии посвященная алгоритмам и кусочкам кода.
http://ru.livecode.org
_________________
Если вы считаете, что C++ труден, попытайтесь выучить английский.(с)Bjarne Stroustrup
С++&&DirectX |
|
|
|
|
|
|
|
|
Канал Игры Мечты: «Алгоритмы - кирпичики Игры Мечты» |
|
|
