OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Среда, 20 Ноябрь, 2019 15:23

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 42 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Воскресенье, 01 Март, 2009 23:10 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Можно решить эту задачу гораздо более быстрым способом. Модель такая. Есть замкнутая цепочка взаимодействующих частиц одинаковой массы. Взаимодействуют только соседние частицы цепочки (и первая с последней). Потенциал взаимодействия U-образный и имеет минимум на заданном расстоянии -- длине этого звена цепи. Ещё нужно добавить вязкость (чтобы всё в конце концов остановилось). Задаём случайное начальное условие и запускаем численную динамику. Когда частицы остановятся смотрим на длину звеньев. Если все частицы попали в минимумы потенциалов, значит решение найдено. Если не попали, то можно, на всякий случай, попробовать другие начальные данные, если не получится, то можно заявить, что решения не существует.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Понедельник, 02 Март, 2009 00:01 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8196
Откуда: Троицк, Москва
Сергей Губанов писал(а):
Можно решить эту задачу гораздо более быстрым способом. ...
Можно? Гораздо? Вы точно пробовали? :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Понедельник, 02 Март, 2009 09:52 

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Господа, подводных камней в задаче достаточно. Предлагаю подкрепить свои взгляды исходниками :) Задача творческая, как тут уже говорилось, и вполне может иметь нестандартное быстрое решение. Можно даже теорию вероятности применить Ж)
У меня тоже ощущение, что лошадка не панацея.
Будут работающие примеры, вот и сравним наглядно.
Там глядь и в задачник кто-нибудь включит
Вопрос к info21:
Как на ваш опытный взгляд по адекватности следующее?
Заполняем массив возможных приращений для обеих координат, для всех возможных длин на данном листе, как уже предлагал Владимир. Можно сразу сделать проверку всех входных данных по этому списку, можно и обойтись. Затем берем приращение (например по х) для первого звена, и сравниваем с суммой всех вариантов приращений оставшихся звеньев (исключение длина звена=5), ежели нуль то суммируем найденные приращения для второй координаты, ежели тоже нуль, то координаты найдены. Можно искать след вариант ломаной. Затем проверка входимости в лист (при длинах звеньев большей листа, можно заранее отсеить)


Последний раз редактировалось inok Вторник, 03 Март, 2009 12:56, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Понедельник, 02 Март, 2009 10:15 

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Кстати если уж выкладывать исходники, то с подробным описанием своих размышлений по первичному исследованию системы. Ну и собсна рекомендации олимпиаднику (человеку поставленному в жесткие рамки), как действовать и распорядиться своими знаниями в такой ситуации


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Понедельник, 02 Март, 2009 14:16 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Info21 писал(а):
Можно? Гораздо? Вы точно пробовали? :)

Попробовал для вещественной решётки. Для целочисленной надо думать.
Вложение:
Chain.zip [1.78 КБ]
Скачиваний: 194


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Понедельник, 02 Март, 2009 14:28 

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Сергей Губанов писал(а):
Info21 писал(а):
Можно? Гораздо? Вы точно пробовали? :)

Попробовал для вещественной решётки. Для целочисленной надо думать.
Вложение:
Chain.zip

Эффектно :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Понедельник, 02 Март, 2009 22:39 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
>> Для целочисленной надо думать.

Чтобы отыскать целочисленный ответ, нужно добавить ещё притяжение частиц цепочки к целочисленным узлам "кристаллической решётки". Если само не "попадёт", то "потрясти".

Получается такая модель: замкнутая цепочка частиц летает в кристаллической решётке.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Понедельник, 02 Март, 2009 23:21 

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Блин!!! Едрена ВОШЬ! Думаю что-то не то в ходе рассуждений. Я задачу нечаянно усложнил. Звенья должны укладываться в ломаную только в том порядке в котором даны.
Ради бога простите склерозника :)
Хотя люди смотрю творчески не хило соображают. Может оно и к лучшему, что усложнил?!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Понедельник, 02 Март, 2009 23:41 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
>> Звенья должны укладываться в ломаную только в том порядке в котором даны.

Я так и понял.


Попробовал добавить "кристаллическую решётку". Как хочется -- не работает. Слишком много локальных минимумов. До глобального дотрясти никакого времени не хватит.
Вложение:
pic1.png
pic1.png [ 6.28 КБ | Просмотров: 5147 ]

Вложение:
Chain.zip [1.84 КБ]
Скачиваний: 194


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Вторник, 03 Март, 2009 13:10 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8196
Откуда: Троицк, Москва
inok писал(а):
Звенья должны укладываться в ломаную только в том порядке в котором даны.
Мы сразу догадались.
inok писал(а):
Хотя люди смотрю творчески не хило соображают.
Этот "людь" прочел очень много книжек, начиная с полноценного (т.е. физического, а не ИТ-шного) курса матанализа.

Просто замечание к дискуссии, убивает ли чтение книжек оригинальность мышления.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Вторник, 03 Март, 2009 13:56 

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Info21 писал(а):
Просто замечание к дискуссии, убивает ли чтение книжек оригинальность мышления.

Согласен


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Вторник, 03 Март, 2009 16:09 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1202
inok писал(а):
Звенья должны укладываться в ломаную только в том порядке в котором даны.

Тогда простой перебор с возвратами. Ну, или распространение ограничений.
Без этого упрощения перебор гораздо серъезнее.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Вторник, 03 Март, 2009 16:27 

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Trurl писал(а):
inok писал(а):
Звенья должны укладываться в ломаную только в том порядке в котором даны.

Тогда простой перебор с возвратами. Ну, или распространение ограничений.
Без этого упрощения перебор гораздо серъезнее.

Ну с переборами все понятно. Я в начале говорил о том, что решили перебором. Сам уже предлагал версию. При переборе много поправок нарастает. Вопрос: имеет ли задача красивое решение? Сергей Губанов к этому очень близок imho. Тут уже речь идет о том, что ув. info21 называл "эффект магии". Возможно ли в этой задаче приодолеть комбинирование?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Вторник, 03 Март, 2009 17:02 

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Info21 писал(а):
Мы сразу догадались.

А вот это любопытно. Там ведь это не оговаривалось. Впрочем не оговаривалось и противоположное...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Вторник, 03 Март, 2009 17:14 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
inok писал(а):
Сергей Губанов к этому очень близок imho.
Наоборот, я убедился в том, что таким способом решение на решётке получить не реально.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Вторник, 03 Март, 2009 17:18 

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Сергей Губанов писал(а):
inok писал(а):
Сергей Губанов к этому очень близок imho.
Наоборот, я убедился в том, что таким способом решение на решётке получить не реально.

Вы сдались окончательно?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Среда, 04 Март, 2009 11:44 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1202
Олимпиада ведь школьная. Поэтому есть подозрение, что задача была ещё проще.
Подразумевалось, что ломаная проведена по линиям листа.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Среда, 04 Март, 2009 17:36 

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Trurl писал(а):
Олимпиада ведь школьная. Поэтому есть подозрение, что задача была ещё проще.
Подразумевалось, что ломаная проведена по линиям листа.

Там была именно решетка, и входные данные были целочисленные с вещественными в перемешку. Хм... Ув. Сергей Губанов, а может вам делать то же самое в два этапа? Сначала для линий по горизонтали потом по вертикали...
Притяжение не к узлам а к линиям...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Четверг, 05 Март, 2009 09:58 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1202
Без перебора не обойтись. Надо ведь выести все решения.
Но перебор не страшный: для небольшого квадрата - примерно 4^n.
inok писал(а):
При переборе много поправок нарастает.

А это как?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Штурм мозгов
СообщениеДобавлено: Четверг, 05 Март, 2009 12:35 

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Trurl писал(а):
Без перебора не обойтись. Надо ведь выести все решения.
Но перебор не страшный: для небольшого квадрата - примерно 4^n.
inok писал(а):
При переборе много поправок нарастает.

А это как?

Ну к примеру "заноза" - длина звена равная 5 в моем примере. Можно конечно и без поправок.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 42 ]  На страницу Пред.  1, 2, 3  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB