|
Название: Бешеный конь. Отправлено: Sirion от Сентябрь 09, 2011, 16:45:07 Можно ли обойти доску N*N с помощью бешеного коня, побывав на каждом поле ровно один раз, и вернуться на исходное поле?
Бешеный конь - это такая особенная фигура. Каждым ходом она смещается на x1 полей по вертикали и на x2 по горизонтали (смещение вправо/вниз считается положительным, а влево/вверх - отрицательным). Эти иксы могут быть сколь угодно велики по модулю (или, напротив, равны нулю) и как угодно соотноситься между собой - главное, чтобы конечное поле находилось в пределах доски. Однако, поскольку конь окончательно 2,718281828банулся, он на протяжении обхода не может совершить два одинаковых хода, т.е. вектор (x1, x2) каждый раз должен быть разным. Поскольку маршрут замкнутый, начальное поле значения не имеет (К.О.) Название: Re: Бешеный конь. Отправлено: Черная кошка от Сентябрь 09, 2011, 16:57:38 http://mathworld.ru/im/chess-o-hode-shahmatnogo-konya.jpg
Может быть вы это имели ввиду? Решение задачи о ходе шахматного коня, данное Эйлером Название: Re: Бешеный конь. Отправлено: Sirion от Сентябрь 09, 2011, 16:58:55 (http://img85.imageshack.us/img85/4586/greenpalm.jpg)
Название: Re: Бешеный конь. Отправлено: moonlight от Сентябрь 09, 2011, 19:19:29 Crazy Horse может ходить вот так
Показать скрытый текст Название: Re: Бешеный конь. Отправлено: Sirion от Сентябрь 09, 2011, 19:35:10 moonlight, мысль хорошая, но тут есть ошибочка: с h7 и h6 ходы одинаковые.
кстати, чем рисовал? Название: Re: Бешеный конь. Отправлено: moonlight от Сентябрь 09, 2011, 20:34:51 рисунок немного изменил.
рисовал в Power Point'e. Название: Re: Бешеный конь. Отправлено: misha zotov от Сентябрь 09, 2011, 21:06:53 Предложил задачку товарищу - он вот такую штуку нарисовал, сказал, что от балды
некорректное изображение удалено - не понял условие... Название: Re: Бешеный конь. Отправлено: Overseer от Сентябрь 09, 2011, 21:27:36 Предложил задачку товарищу - он вот такую штуку нарисовал, сказал, что от балды (http://savepic.net/1972408.jpg) действительно от балды, куча повторяющихся ходов :/ Название: Re: Бешеный конь. Отправлено: Димыч от Сентябрь 09, 2011, 23:12:20 С e5 и i5 одинаковые.
Название: Re: Бешеный конь. Отправлено: Димыч от Сентябрь 10, 2011, 00:14:52 Можно немного модифицировать эту схему, чтобы все ходы, параллельные главным диагоналям, лежали на главных диагоналях. Для N=4k+3 сразу получается решение. Для других N нужно воспользоваться свободой выбора: каждую «рамку» можно обходить из данной вершины двумя симметричными способами и переходить к любой вершине внутренней «рамки», кроме соседней с той, с которой начался обход этой «рамки» (на самом деле там будут определенные ограничения, но они не существенны, поскольку нам не нужно для одной и той же «рамки» одновременно выбирать способ обхода и способ перехода к следующей). Для четных N можно вообще избавиться от совпадения финального хода с одним из предыдущих. Для N=4k+1 можно добиться, чтобы совпадающие ходы проходились в разных направлениях. Надеюсь, понятно объяснил.
Название: Re: Бешеный конь. Отправлено: moonlight от Сентябрь 10, 2011, 00:31:06 Название: Re: Бешеный конь. Отправлено: buka от Сентябрь 10, 2011, 03:26:11 А если просто по банальной прямоугольной спирали?
Название: Re: Бешеный конь. Отправлено: Sirion от Сентябрь 10, 2011, 10:31:47 красивая фиговина получается)
|