» Главная
eXcode.ru » Статьи » Задачи » С решениями
» Новости
» Опросы
» Файлы
» Журнал



Пользователей: 0
Гостей: 8





Шахматный конь




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

Ставим коня в произвольную клетку на доске. Из любой клетки
конь имеет не более 8 вариантов для продолжения своего пути,
причем направления этих путей для любой клетки известны.
Поочередно переставляя коня на различные позиции, ищем такую,
которая удовлетворяет условию, что ранее конь на ней не был.
Есди таких вообще позиций нет, то возвращаемся на предыдущую
клетку и так далее.
Таким образом продолжаем движение, пока не будет пройдена вся доска.


{$APPTYPE CONSOLE}
const n=8;d=64;
way:array[1..8,1..2]of -2..2=
((-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1));
{Таким образом задается, куда может сделать следующий ход
конь с текущей позиции}

var i,j,m:1..n;
board:array[1..n,1..n]of boolean;
{Здесь отмечаем клетки, на которых конь уже был}
route:array[1..d,1..2]of char;
{Запоминание координат маршрута "жеребца"}

procedure print;
var i:1..d;
begin writeln(′The Chess Horse′);
for i:=1 to d do write(route[i,1],route[i,2],′ ′);
readln;halt;end;

procedure inspector(p1,p2:integer);
var y,j,i:byte;
begin if m=d then print;
{Если конь сделал 64 "успешных" хода значит вся доска пройдена}
for y:=1 to 8 do begin
i:=p1+way[y,1];j:=p2+way[y,2]; {Шагаем копытом на следующую клетку}
if(i in[1..n])and(j in [1..n])and not(board[i,j])then
begin inc(m);
route[m,1]:=chr(64+i);
route[m,2]:=chr(48+j);
board[i,j]:=true; {Перебор с возвратами}
inspector(i,j);
dec(m);
board[i,j]:=false;
end;
end;
end;

begin
for i:=1 to n do
for j:=1 to n do board[i,j]:=false;
i:=1;j:=1;//readln(i,j);
{Координаты можно и вводить, но далеко не факт, что
путь такой есть и "жеребец" не заблудится. В этом случае программу
нужно завершать извне, так как она зациклится. А можно написать
маленькую функцию проверки на зацикливание и вставить ее
в начало inspector. Но вданном примере целью было показать ход решения.}
m:=1;
route[m,1]:=chr(64+i);
route[m,2]:=chr(48+j);
board[i,j]:=true;
inspector(i,j);end.

К началу статьи





Добавил: EugeneДата публикации: 2006-01-20 19:18:17
Рейтинг статьи:5.00 [Голосов 4]Кол-во просмотров: 8715

Комментарии читателей

Всего комментариев: 1

2006-11-17 21:31:50
Женя
А без Halt слабо решить?
Ваше имя: *
Текст записи: *
Имя:

Пароль:



Регистрация

Как вы относитесь к AJAX?
Считаю это ЗЛОМ
11% (12)
Бесполезная технология
2% (2)
Мне параллельно
9% (10)
Неплохая технология
20% (23)
Рулез, как я без нее жил!
7% (8)
Я разработчик AJAX-приложений
5% (6)
А что? Хороший футбольный клуб!
12% (14)
Я в танке!!!
34% (38)

Проголосовало: 113
Идет кинофильм, какой то душераздирающий триллер. Главная героиня в ажурном нижнем белье медленно продвигается по темному коридору. Музыка нагнетает обстановку. Главная героиня подходит к двери, протягивает руку, что бы открыть ее ... И тут истошный крик из зала:
- Сохраняйся, дура!!! Сохраняйся!!!
Рейтинг: 6.3/10 (3)
Посмотреть все анекдоты