Задача Эйлера (Ход конем)

Слайд 1

Задача Эйлера “ Ход конём ” Исследовательская работа на тему : Выполнил : Кривенко И.Р. 10 ” Д ” Руководитель : учитель математики Богданенко Е.Н.

Слайд 2

Мышление о шахматных задачах и головоломках Метод Эйлера Метод Вандермонда Правило Варнсдорфа Мнемоническое стихотворение Вывод Содержание

Слайд 3

Шахматная задача – это искусственно созданная позиция фигур на доске, в которой необходимо выполнить некоторое условие (например, поставить мат в три хода). Шахматная головоломка – это задача на сообразительность, в которой используется шахматная доска и шахматные фигуры. Решение шахматных задач, этюдов и головоломок – необычное и увлекательное занятие, способствующее развитию мыслительных способностей. Самая интересная и необычная шахматная фигура – конь. Конь – самая непрямолинейная шахматная фигура. Решение шахматных задач, в которых фигурируют только кони, способствует развитию нестандартного непрямолинейного мышления. Мышление о шахматных задачах и головоломках

Слайд 4

Метод Эйлера состоит в том, что сначала конь двигается по произвольному маршруту, пока не исчерпает все возможные ходы. Затем оставшиеся не пройденными клетки добавляются в сделанный маршрут, после специальной перестановки его элементов . Конь ходит в порядке, указанном числами. Так как из последнего места 64 он может перейти на 1, то этот полный ход есть возвратный».Таково решение задачи о ходе шахматного коня, данное Эйлером Метод Эйлера

Слайд 5

Вандермонд попытался свести задачу к арифметической. Для этого он обозначал маршрут коня по доске в виде последовательности дробей , где x и y — координаты поля на доске. Очевидно, что в последовательности дробей, соответствующей ходам коня, разность числителей двух соседних дробей может быть только 1 или 2, при том, что разность их знаменателей составляет соответственно 2 или 1. Кроме того, числитель и знаменатель не могут быть меньше 1 и больше 8. Его метод нахождения подходящей последовательности аналогичен методу Эйлера, но позволяет находить маршруты коня только для досок чётной размерности. Метод Вандермонда

Слайд 6

Правило Варнсдорфа , являющееся разновидностью жадного алгоритма для отыскания маршрута коня, формулируется так: При обходе доски конь следует на то поле, с которого можно пойти на минимальное число ещё не пройденных полей. Если таких полей несколько, то можно пойти на любое из них. Долгое время считалось, что правило Варнсдорфа работает безукоризненно. Позднее с помощью компьютеров была установлена неточность во второй его части: если существует несколько подходящих полей, то не все они равноценны, и произвольный выбор поля может завести коня в тупик. На практике однако вероятность попадания в тупик невелика даже при вольном пользовании второй частью правила Варнсдорфа Кстати этот метод является самым распространненым в наше время. Правило Варнсдорфа

Слайд 7

Обойти конём все шахматные клетки и ни разу не побывать дважды на одной и той же, к тому же сделать это «вслепую», начав или закончив на любой клетке по желанию «зрителя», можно благодаря стихотворению: Мнемоническое стихотворение Алеет Осень Ценными Дарами, Еще Один Животворящий День. Хлеба Червонят Желтыми Шнурами, Хрустальных Вод Философична Сень. Два Вечера Цеплявшиеся Шишки Артист Писал, Бездонна Синева. Дорожный Шлак Дымится Чай Эффектней Шоколада, Фарфоры Чашек Достаются Трем, Блондинке Девушка Дана Отрада Форшмак Делить Холодным Острием. Жена, Толкая Хилую Подругу, Желает Сняться Этим Выходным, Ценя Сама Арктическую Вьюг у Бросает Шар Арбуза Четверым. Цикад Пяток, Едва Чревовещая, Дарует Дрему Фикусам Окна. Хотя Довольны Жаждавшие Чая, Хозяин Шумно Жертвует Вина. Фокстротами Шесть Девушек Пленились, Эстрадных Танцев Фантастичней Па, Едва Ступающий Цыпленок Вылез, А Селезень Блуждающий Алеет Тело Бронзовой Осины, Царит Теней Ажурная Длина. Беззвучней, Чем Автомобиля Шины, Болоту Ветер Дарит Семена. Фонарь Восьмью Химерами Сияет, Жук Прилетает, Хлопая, Туда . Желанна Осень, Если Довершает Ценнейший Отдых Бодрого Труда. Первые буквы задают координаты ходов : Алеет Осень = А1; Ценными Дарами = С2 .

Слайд 8

Подходя к концу моей исследовательской работы, мы узнали : Как обойти конем все 64 клетки шахматной доски так, чтобы на каждой клетке конь был только один раз и затем возвратился бы в клетку, из которой вышел. Вывод