Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт фев 29, 2024 05:06

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - Задача "нерешительный кенгуру"
Автор Сообщение
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
я поразмышлял на тему прямого и обратного поиска и пришел к выводу что оба подхода симметричны:
- при движении вперед длина прыжка умножается на 4/5, назад -- на 5/4
- при движении вперед мы останавливаемся когда в окрестности равной длине прыжка нет камней (слишком короткий прыжок), при движении назад -- когда длина прыжка превышает макс. допустимую (слишком длинный прыжок)
- в обоих направлениях можно реализовать поиск и в глубину и в ширину
и тд...

но есть важное различие: при прямом обходе первый найденный путь удовлетворяет условию минимальности 1-го прыжка, при обратном надо перебрать все пути

остается вопрос: что лучше -- в глубину или ширину? Идя в глубину можно довольно эффективно отсекать повторное прохождение камней расставляя на них метки (динамическое программирование); если в ширину то такое отсечение невозможно, но может и не нужно?

у кого какие мысли по этому поводу?
Сообщение Добавлено: Чт апр 14, 2011 03:04
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
viewtopic.php?f=12&t=2704&start=15
разместил решение на прологе для проверки решения на форте

Всё-таки ещё раз предложу (не настаивая) открыть в конкурсе задач подотдел "решения на других языках" (тех же задач) не каждый тематический программистский форум может похвастать тем, что задачи решают на нескольких языках одновременно, манипулируя алгоритмами
Задача про поиск пробела была решена на Прологе (два решения), Эйфории, и на Форте, причём Форт был нескольких реализаций и Пролог - также не один
Сообщение Добавлено: Ср апр 13, 2011 20:50
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
Хищник писал(а):
вопрос писал(а):
Цитата:
Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.

Эээ... а что не так? Сумма квадратов расстояний - целое число. Если расстояния должны соотноситься не более чем 4/5, то квадраты - не более чем 16/25.

Всё так :) , теперь может быть кто-то код предложит
если нужно, могу запостить решение на Прологе для проверки
оно, правда, в действительных числах и полный исчерпывающий перебор
Сообщение Добавлено: Вт апр 12, 2011 23:54
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
вопрос писал(а):
Цитата:
Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.

Эээ... а что не так? Сумма квадратов расстояний - целое число. Если расстояния должны соотноситься не более чем 4/5, то квадраты - не более чем 16/25.
Сообщение Добавлено: Вт апр 12, 2011 23:38
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
Цитата:
Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.
:)
Сообщение Добавлено: Вт апр 12, 2011 22:42
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
вопрос писал(а):
Если нам понятно, что длина больше - то нет. Т.е. если например по вертикали камень расположен на расстоянии 10 , то если он хоть на небольшой угол отклонен по диагонали - то расстояние очевидно больше.

Но вот если мы прыгнули на корень квадратный из 17, то как рассчитывать максимальную длину следующего прыжка? На что умножать 4/5 - на точное значение, а потом округлить, или сначала округлить, а потом умножить?
Если это не оговорено, то в целых числах вполне можно работать, оперируя квадратами расстояний. Они будут строго целыми.
Сообщение Добавлено: Вт апр 12, 2011 22:37
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
Надеюсь подробное изложение Хищника :idea: не ввело кого-то в заблуждение - там показан теоретически лучший вариант
реально решенине будет хужe
Сообщение Добавлено: Вт апр 12, 2011 22:30
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
Хищник писал(а):
вопрос писал(а):
это вопрос а не задача, впрочем, это часть задачи

Так я уже несколько вариантов привел. Вот если допустимая длина прыжка 10, а до нового камня 10.1, то прыгать можно или нет?

Если нам понятно, что длина больше - то нет. Т.е. если например по вертикали камень расположен на расстоянии 10 , то если он хоть на небольшой угол отклонен по диагонали - то расстояние очевидно больше.
Сообщение Добавлено: Вт апр 12, 2011 22:22
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
вопрос писал(а):
это вопрос а не задача, впрочем, это часть задачи

Так я уже несколько вариантов привел. Вот если допустимая длина прыжка 10, а до нового камня 10.1, то прыгать можно или нет?
Сообщение Добавлено: Вт апр 12, 2011 22:16
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
Цитата:
Во-вторых, не учитывается переход от плавающей точки к целочисленному представлению, который, кстати, не оговорен и в условии. Если длина прыжка стала 0.99, то прыгать нельзя?

Цитата:
при каких условиях возможно решение с использованием только целых чисел
это вопрос а не задача, впрочем, это часть задачи
Сообщение Добавлено: Вт апр 12, 2011 22:06
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
Максимальная длина прыжков представляет собой геометрическую прогрессию. Сумма ее n членов
s = b * (1-4/5^n)/(1-4/5)
при n -> \inf формула превращается в s = b * (1-0)/(1-4/5), или s = b*5
Отсюда, если сумма должна быть не менее 25, то длина первого прыжка не может быть меньше 5. Это верхнее ограничение, причем оно не учитывает две особенности. Во-первых, при b=5 прыгать придется до бесконечности (так что это не вариант). Во-вторых, не учитывается переход от плавающей точки к целочисленному представлению, который, кстати, не оговорен и в условии. Если длина прыжка стала 0.99, то прыгать нельзя? Или надо дождаться 0.5? Или все расчеты надо вести с округлением, и следующий шаг рассчитывать от целочисленного представления, полученного округлением предыдущего прыжка?
Если отталкиваться от одного из вариантов, то можно попробовать проверять ближайший камень, находящийся на расстоянии, большим 5. Для каждого последующего прыжка пишем функцию "теоретически можно допрыгнуть", которая будет вычислять сумму бесконечного числа членов геометрической прогрессии с начальным членом, равным расстоянию прыжка до этого камня. И далее рекурсивно, пока не допрыгаем не теоретически, а практически.
Сообщение Добавлено: Вт апр 12, 2011 21:33
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
мне кажется метод «обратной волны» как раз-таки приведет к перебору всех возможных путей, т.к. обратный проход стремится максимизировать первоначалтный прыжок и следовательно чтобы найти минимальный нужно перебрать все пути
Сообщение Добавлено: Вт апр 12, 2011 20:55
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
WingLion писал(а):
А "волной" с обратного берега пройти не проще?
Да и первым пробуем самый ближайший камень.
Сообщение Добавлено: Вт апр 12, 2011 17:00
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
А "волной" с обратного берега пройти не проще? По обратному правилу соотношения прыжков.
Идем на все камни сразу (они становятся "вторым берегом"), с них смотрим, куда можно попасть еще и так несколько раз, пока не доберемся до другого берега, не доберемся - значит и прямого пути нет.
Сообщение Добавлено: Вт апр 12, 2011 08:35
  Заголовок сообщения:  Re: Задача "нерешительный кенгуру"  Ответить с цитатой
а это уже зависит от других эвристик ))

поэтому предлагаю еще для каждого пройденного камня запоминать макс. допустимую длину прыжка при котором берег из этого камня не достижим (если достижм то дальше нечего делать) -- тогда при повторном попадании на камень можно сравнивать текущую возможную длину прыжка с той что "записана на камне" и делать вывод стоит ли продолжать путь или вернуться назад
Сообщение Добавлено: Пн апр 11, 2011 14:12

Часовой пояс: UTC + 3 часа [ Летнее время ]


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB