Sirion
Гений-Говорун
 Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
 |
� : Сентябрь 09, 2011, 16:45:07 � |
|
Можно ли обойти доску N*N с помощью бешеного коня, побывав на каждом поле ровно один раз, и вернуться на исходное поле?
Бешеный конь - это такая особенная фигура. Каждым ходом она смещается на x1 полей по вертикали и на x2 по горизонтали (смещение вправо/вниз считается положительным, а влево/вверх - отрицательным). Эти иксы могут быть сколь угодно велики по модулю (или, напротив, равны нулю) и как угодно соотноситься между собой - главное, чтобы конечное поле находилось в пределах доски. Однако, поскольку конь окончательно 2,718281828банулся, он на протяжении обхода не может совершить два одинаковых хода, т.е. вектор (x1, x2) каждый раз должен быть разным.
Поскольку маршрут замкнутый, начальное поле значения не имеет (К.О.)
|
|
|
|
� Последнее редактирование: Сентябрь 09, 2011, 16:57:04 от Sirion �
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Черная кошка
Гений-Говорун
Offline
Сообщений: leet
СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 217
я не ангел, но ведь и жизнь- не рай.
|
|
� Ответ #1 : Сентябрь 09, 2011, 16:57:38 � |
|
//текст доступен после регистрации// Может быть вы это имели ввиду? Решение задачи о ходе шахматного коня, данное Эйлером
|
|
|
|
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #2 : Сентябрь 09, 2011, 16:58:55 � |
|
|
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #3 : Сентябрь 09, 2011, 19:19:29 � |
|
Crazy Horse может ходить вот так Показать скрытый текст |
|
|
|
� Последнее редактирование: Сентябрь 09, 2011, 20:32:29 от moonlight �
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #4 : Сентябрь 09, 2011, 19:35:10 � |
|
moonlight, мысль хорошая, но тут есть ошибочка: с h7 и h6 ходы одинаковые.
кстати, чем рисовал?
|
|
|
|
� Последнее редактирование: Сентябрь 09, 2011, 20:08:19 от Sirion �
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #5 : Сентябрь 09, 2011, 20:34:51 � |
|
рисунок немного изменил.
рисовал в Power Point'e.
|
|
|
|
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
misha zotov
Давненько
Offline
Сообщений: 94
СПАСИБО
-вы поблагодарили: 6
-вас поблагодарили: 14
|
|
� Ответ #6 : Сентябрь 09, 2011, 21:06:53 � |
|
Предложил задачку товарищу - он вот такую штуку нарисовал, сказал, что от балды
некорректное изображение удалено - не понял условие...
|
|
|
|
� Последнее редактирование: Сентябрь 09, 2011, 21:34:33 от misha zotov �
|
Записан
|
|
|
|
Overseer
Свой человек
Offline
Сообщений: 436
СПАСИБО
-вы поблагодарили: 116
-вас поблагодарили: 119
Играй
|
|
� Ответ #7 : Сентябрь 09, 2011, 21:27:36 � |
|
Предложил задачку товарищу - он вот такую штуку нарисовал, сказал, что от балды  действительно от балды, куча повторяющихся ходов :/ |
|
|
|
|
Записан
|
|
|
|
Димыч
Умник
Offline
Сообщений: 770
СПАСИБО
-вы поблагодарили: 65
-вас поблагодарили: 384
|
|
� Ответ #8 : Сентябрь 09, 2011, 23:12:20 � |
|
|
|
|
|
|
Записан
|
|
|
|
Димыч
Умник
Offline
Сообщений: 770
СПАСИБО
-вы поблагодарили: 65
-вас поблагодарили: 384
|
|
� Ответ #9 : Сентябрь 10, 2011, 00:14:52 � |
|
Можно немного модифицировать эту схему, чтобы все ходы, параллельные главным диагоналям, лежали на главных диагоналях. Для N=4k+3 сразу получается решение. Для других N нужно воспользоваться свободой выбора: каждую «рамку» можно обходить из данной вершины двумя симметричными способами и переходить к любой вершине внутренней «рамки», кроме соседней с той, с которой начался обход этой «рамки» (на самом деле там будут определенные ограничения, но они не существенны, поскольку нам не нужно для одной и той же «рамки» одновременно выбирать способ обхода и способ перехода к следующей). Для четных N можно вообще избавиться от совпадения финального хода с одним из предыдущих. Для N=4k+1 можно добиться, чтобы совпадающие ходы проходились в разных направлениях. Надеюсь, понятно объяснил.
|
|
|
|
|
Записан
|
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #10 : Сентябрь 10, 2011, 00:31:06 � |
|
|
|
|
|
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #11 : Сентябрь 10, 2011, 03:26:11 � |
|
А если просто по банальной прямоугольной спирали?
|
|
|
|
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #12 : Сентябрь 10, 2011, 10:31:47 � |
|
красивая фиговина получается)
|
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
|
