OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 29 Март, 2024 10:57

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




Начать новую тему Ответить на тему  [ Сообщений: 42 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Штурм мозгов
СообщениеДобавлено: Суббота, 28 Февраль, 2009 17:52 

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
В 2000 году я участвовал в окружной олимпиаде по программированию в Нефтеюганске. Там была одна задача которая до сих пор не дает мне покоя.
На олимпиаде из 40 человек ее решило только двое. Решили тупым перебором. Писать можно было на qbasic 4.5 и TP 7.0. Перебором решили на пасе, т.к. на кубарсике с его скоростью и тыркаться нечего было. Ограничение по времени 2 минуты вроде. Я писал на барсике и начал искать красивое решение, так и лажанулся неуспев дописать. Время вышло.
После олимпиады организаторы попросили у нас прощения, и посвятили нас в то, что мы участники эксперимента и задачи эти до нас никто не решал.
С тех пор я ее решить больше не пробовал. Но осадок остался
Господа математики дайте моей душе успокоиться.

Вот задача:
Имеется тетрадный лист в клеточку. Допустим 10х10.
И имеются входные данные, где через запятую даны числа (целые или вещественные не оговаривается, количество не оговаривается). Эти числа суть длины звеньев замкнутой ломаной. (самопересечения по-моему не оговаривались) построенной на узлах решетки нашего листа. Задача дать координаты всех узлов (если возможно то несколько вариантов) либо выдать что такая ломаная не существует


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

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

Зарегистрирован: Воскресенье, 28 Май, 2006 22:12
Сообщения: 1693
inok писал(а):
Вот задача:

Шаг решётки указывался?
Не помните, размеры решётки конечные были?
Допуск точности на длины звеньев давался?


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Разве это не задача типа обхода шахматной доски конем?

inok писал(а):
В 2000 году я участвовал в окружной олимпиаде по программированию в Нефтьюганске. Там была одна задача которая до сих пор не дает мне покоя.
На олимпиаде из 40 человек ее решило только двое. Решили тупым перебором. Писать можно было на qbasic 4.5 и TP 7.0. Перебором решили на пасе, т.к. на кубарсике с его скоростью и тыркаться нечего было. Ограничение по времени 2 минуты вроде. Я писал на барсике и начал искать красивое решение, так и лажанулся неуспев дописать. Время вышло.
После олимпиады организаторы попросили у нас прощения, и посвятили нас в то, что мы участники эксперимента и задачи эти до нас никто не решал.
С тех пор я ее решить больше не пробовал. Но осадок остался
Господа математики дайте моей душе успокоиться.

Вот задача:
Имеется тетрадный лист в клеточку. Допустим 10х10.
И имеются входные данные, где через запятую даны числа (целые или вещественные не оговаривается, количество не оговаривается). Эти числа суть длины звеньев замкнутой ломаной. (самопересечения по-моему не оговаривались) построенной на узлах решетки нашего листа. Задача дать координаты всех узлов (если возможно то несколько вариантов) либо выдать что такая ломаная не существует


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

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Владимир Лось писал(а):
inok писал(а):
Вот задача:

Шаг решётки указывался?
Не помните, размеры решётки конечные были?
Допуск точности на длины звеньев давался?


Шаг решетки единица.
Допуска небыло
Размер решетки фиксированный


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

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

inok писал(а):
В 2000 году я участвовал в окружной олимпиаде по программированию в Нефтьюганске. Там была одна задача которая до сих пор не дает мне покоя.
На олимпиаде из 40 человек ее решило только двое. Решили тупым перебором. Писать можно было на qbasic 4.5 и TP 7.0. Перебором решили на пасе, т.к. на кубарсике с его скоростью и тыркаться нечего было. Ограничение по времени 2 минуты вроде. Я писал на барсике и начал искать красивое решение, так и лажанулся неуспев дописать. Время вышло.
После олимпиады организаторы попросили у нас прощения, и посвятили нас в то, что мы участники эксперимента и задачи эти до нас никто не решал.
С тех пор я ее решить больше не пробовал. Но осадок остался
Господа математики дайте моей душе успокоиться.

Вот задача:
Имеется тетрадный лист в клеточку. Допустим 10х10.
И имеются входные данные, где через запятую даны числа (целые или вещественные не оговаривается, количество не оговаривается). Эти числа суть длины звеньев замкнутой ломаной. (самопересечения по-моему не оговаривались) построенной на узлах решетки нашего листа. Задача дать координаты всех узлов (если возможно то несколько вариантов) либо выдать что такая ломаная не существует


Что-то похожее вроде. Но по-моему не то. Хотя может и торможу...
Если видите явную параллель поясните пожалуйста, на пальцах если можно


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

Зарегистрирован: Воскресенье, 28 Май, 2006 22:12
Сообщения: 1693
Info21 писал(а):
Разве это не задача типа обхода шахматной доски конем?

Нет, длина прыжка - не фиксирована, а, следовательно, разрешённых положений-узлов - больше (если вообще возможно).


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

Зарегистрирован: Воскресенье, 28 Май, 2006 22:12
Сообщения: 1693
inok писал(а):
Шаг решетки единица.
Допуска небыло
Размер решетки фиксированный

Ну, тогда, допустимость сразу находится. Сначал, методом "грубой силы" - находим Н*(Н+1)/2 вариантов (допустимых по условиям задачи) расстояний между узлами решётки. Если хотим - сортируем для ускорения будущего поиска. Потом, пройдясь по всем числам ломанной - смотрим, есть ли такие, которые не равны ни одному из отсортированных расстояний...
Ну, а дальше - поиск в глубину по допустимым положениям концов векторов на узлах решётки, для каждого из начал. При этом, следующее начало - будет предыдущим концом. Для первого начала - прямой перебор по допустимым начальным положениям, в зависимости от расстояния до первого конца, попадающего на узел.


Последний раз редактировалось Wlad Суббота, 28 Февраль, 2009 18:48, всего редактировалось 3 раз(а).

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

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Владимир Лось писал(а):
Info21 писал(а):
Разве это не задача типа обхода шахматной доски конем?

Нет, длина прыжка - не фиксирована, а, следовательно, разрешённых положений-узлов - больше (если вообще возможно).


Вот примерно в этом я и усомнился...


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

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Тут конечно ежу понятно что сумма векторов равна нулю. Но у меня лично какое-то интуитивное отторжение дискретности в этой задаче


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

Зарегистрирован: Воскресенье, 28 Май, 2006 22:12
Сообщения: 1693
inok писал(а):
Тут конечно ежу понятно что сумма векторов равна нулю.

???


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

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

???


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


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

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Владимир Лось писал(а):
inok писал(а):
Шаг решетки единица.
Допуска небыло
Размер решетки фиксированный

Ну, тогда, допустимость сразу находится. Сначал, методом "грубой силы" - находим Н*(Н+1)/2 вариантов (допустимых по условиям задачи) расстояний между узлами решётки. Если хотим - сортируем для ускорения будущего поиска. Потом, пройдясь по всем числам ломанной - смотрим, есть ли такие, которые не равны ни одному из отсортированных расстояний...
Ну, а дальше - поиск в глубину по допустимым положениям концов векторов на узлах решётки, для каждого из начал. При этом, следующее начало - будет предыдущим концом. Для первого начала - прямой перебор по допустимым начальным положениям, в зависимости от расстояния до первого конца, попадающего на узел.


Я делал тогда тупее но похоже. Без начального отсеивания заведомо неверных вариантов, "ставил" конец первого звена в угловом узле решетки. И поворачивал на 360 пока не войдет в границы листа, затем условие совпадения с конца с любым узлом. Если условия выполнены то ставил на найденный узел след звено и все сначала. При этом надо было по изуверски следить за суммой образованных векторов


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

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


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

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Еще думаю логично вначале сделать проверку являются ли входные числа все целыми либо все вещественными, чтобы ограничить пространство поиска


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

Зарегистрирован: Воскресенье, 28 Май, 2006 22:12
Сообщения: 1693
inok писал(а):
Еще думаю логично вначале сделать проверку являются ли входные числа все целыми либо все вещественными, чтобы ограничить пространство поиска
Если, как Вы говорите, размер 10х10 - то, конечно, пространство сильно сузится. Но и вариативность входных длин будет не сильно широкой...
inok писал(а):
При этом надо было по изуверски следить за суммой образованных векторов
А - зачем?
inok писал(а):
Загвоздка в том, что решение должно быть правильным при любом раскладе. А раскладов тьма Такое ощущение что есть какое-то стройное решение, но ухватить не могу
Не факт!

Кстати, "крутить" опробуемый вектор, можно по Брезенхаму для окружности - будет быстрее.
Ещё быстрее - по длине вектора (как индексу) - смотреть в массиве списков заранее просчитанных пар катетов-смещений от текущей точки начала... А можно и их только для одной четверти/октета просчитывать и только знаки менять при актах пробы на подходящую точку для конца вектора...

Короче - творчество...


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

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск
Можно ли повторно использовать узлы решётки?


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

Зарегистрирован: Воскресенье, 28 Май, 2006 22:12
Сообщения: 1693
Александр Ильин писал(а):
Можно ли повторно использовать узлы решётки?
Кстати, - да! ???
Может, как параметром ввести?


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

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

Нет, длина прыжка - не фиксирована, а, следовательно, разрешённых положений-узлов - больше (если вообще возможно).

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

Читайте книжки, коллеги.


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

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Александр Ильин писал(а):
Можно ли повторно использовать узлы решётки?

Так как это не оговаривалось, то можно


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

Зарегистрирован: Суббота, 31 Январь, 2009 06:29
Сообщения: 328
Info21 писал(а):
Владимир Лось писал(а):
Info21 писал(а):
Разве это не задача типа обхода шахматной доски конем?

Нет, длина прыжка - не фиксирована, а, следовательно, разрешённых положений-узлов - больше (если вообще возможно).

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

Читайте книжки, коллеги.


Надо бы обмозговать
А лучше реализовать:)


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

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


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

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


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

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