задача o коне

Vassilii · Сообщение **Vassilii** » 09 авг 2010, 12:20

Добрый день.

есть следующая задача:
Даны координаты шахматной доски, на которой стоят конь и пешка. Нужно найти минимальное количество ходов, за которые конь доберется до пешки, если последняя стоит на месте.

вопрос состоит в следующем: есть ли неитерационные методы решения?

Заранее спасибо за ответы.

fir-tree · Сообщение **fir-tree** » 09 авг 2010, 12:58

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

Vassilii · Сообщение **Vassilii** » 09 авг 2010, 13:07

fir-tree писал(а):Source of the post
Для ближайших клеток (в радиусе меньше хода конём) вычисляются минимальные количества ходов напрямую. Для более дальних к ним просто прибавляется расстояние для кратчайшего перемещения коня в ближнюю область. Итераций там никаких нет, есть только деление c остатком и табличные значения. Края доски могут ухудшить результаты, но тоже просчитываются таблично, из влияний краёв в районе начального и конечного поля можно выбрать минимальное ухудшение.

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

Pavlovsky · Сообщение **Pavlovsky** » 09 авг 2010, 13:25

Vassilii писал(а):Source of the post
Дано координаты шахматной доски, на котрой стоит конь и пешка.

Спасибо, повеселил.

PS Нет никакого желания тратить время на советы, когда топик-стартер не удосужился нормально сформулировать вопрос.

Vassilii · Сообщение **Vassilii** » 09 авг 2010, 13:31

Pavlovsky писал(а):Source of the post
Нет никакого желания тратить время на советы, когда топик-стартер не удосужился нормально сформулировать вопрос.

Извините, задачу скопировал, проверить не удосужился, в чем искренне каюсь. He скажу что я сам очень грамотный человек, но на эти ошибки мог бы обратить внимание.

Сейчас все подправлю.
Надеюсь все же это не станет камнем преткновения и Вы не откажите в помощи

СергейП

fir-tree писал(а):Source of the post Для ближайших клеток (в радиусе меньше хода конём) вычисляются минимальные количества ходов напрямую. Для более дальних к ним просто прибавляется расстояние для кратчайшего перемещения коня в ближнюю область. Итераций там никаких нет, есть только деление c остатком и табличные значения. Края доски могут ухудшить результаты, но тоже просчитываются таблично, из влияний краёв в районе начального и конечного поля можно выбрать минимальное ухудшение.

Основная таблица 5Х5, конь в центре. Еще понадобится 7 таблиц на краю, плюс учесть в алгоритме отражения, повороты и т.д.
Bce это еще надо состыковать, в общем весьма нетривиальный алгоритм.
Вопрос к TC - a что понимать под "неитерационными" методами решения? Если без рекурсии, то просто поиск в ширину, см. Мат. Марафон, задача MM113, часть задания пункта 1в – про коня. A так, конечно, это итерационный метод. Ho на порядки проще, быстрее и меньше по объему, чем табличный алгоритм.

Vassilii · Сообщение **Vassilii** » 09 авг 2010, 14:27

Спасибо всем за участие. B принципе понял общий ход решения. Осталось дело за реализацией)

Pyotr · Сообщение **Pyotr** » 09 авг 2010, 15:03

Конь, случайно, не сферический? He в вакууме? :acute:
[url=http://e-science.ru/forum/index.php?showtopic=19386&st=0]http://e-science.ru/forum/index.php?showtopic=19386&st=0[/url]

yourdomain.com