Найти количество шагов, которые может сделать конь на шахматной доске для прохождения всего поля

@Anton124 · Регистрация: 01.11.2018

не получается сделать код программы: программа должна находить количество шагов, которые может сделать шахматная фигура конь на шахматной доске размером 8 на 8, с определенной позиции для прохождения всего шахматного поля, при этом в каждой клетке конь МОЖЕТ БЫТЬ ТОЛЬКО ОДИН РАЗ. Конь не может выйти за рамки шахматной доски. Изначально поле очищено и конь находиться в центре доски. Помогите реализовать это на паскаль. и если все шаги сделаны - то вывести их количество, а если конь зашёл в тупик. то вывести количество сделанных шагов и предложить начать сначала

ФедосеевПавел · 23.01.2019, 12:04

Т.к. конь может обойти всю доску 8х8, посещая каждое поле всего 1 раз и вернувшись к исходной клетке (Гамильтонов цикл), то значит, что с каждого поля можно продолжить обход, посетив все поля.
А следующий вывод - для посещения всех клеток требуется 63 хода. Т.е. программа

Pascal

1
2
3

begin
  write(63)
end.

А так вам требуется обычный DFS - рекурсивный обход в глубину с запоминанием максимальной длины ходов.

Добавлено через 6 минут
Описание http://algolist.manual.ru/math... knight.php

@кот Бегемот · 23.01.2019, 12:25

Решение на Паскале приведено в книге «100 задач по программированию» прибалтийских авторов. Книга есть в сети.

@Anton124 -52 / 0 / 0 Регистрация: 01.11.2018 Сообщений: 146
		1
	Найти количество шагов, которые может сделать конь на шахматной доске для прохождения всего поля 22.01.2019, 21:19. Показов 1230. Ответов 2 Метки нет (Все метки) не получается сделать код программы: программа должна находить количество шагов, которые может сделать шахматная фигура конь на шахматной доске размером 8 на 8, с определенной позиции для прохождения всего шахматного поля, при этом в каждой клетке конь МОЖЕТ БЫТЬ ТОЛЬКО ОДИН РАЗ. Конь не может выйти за рамки шахматной доски. Изначально поле очищено и конь находиться в центре доски. Помогите реализовать это на паскаль. и если все шаги сделаны - то вывести их количество, а если конь зашёл в тупик. то вывести количество сделанных шагов и предложить начать сначала 0

@кот Бегемот Платежеспособный зверь 8816 / 4243 / 1617 Регистрация: 28.10.2009 Сообщений: 11,383
	23.01.2019, 12:25	3
	Решение на Паскале приведено в книге «100 задач по программированию» прибалтийских авторов. Книга есть в сети. 0

Опции темы