Форум по Delphi программированию

Delphi Sources



Вернуться   Форум по Delphi программированию > Все о Delphi > Разное
Ник
Пароль
Регистрация <<         Правила форума         >> FAQ Пользователи Календарь Поиск Сообщения за сегодня Все разделы прочитаны

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 26.11.2006, 16:47
ART ART вне форума
Продвинутый
 
Регистрация: 13.02.2006
Адрес: Магнитогорск
Сообщения: 669
Репутация: 14745
По умолчанию Шахматная задача

Задача:
Имеется конь с некоторыми координатами на доске 64Х64 и нуна сделать так, чтобы конь обошел все клетки бобывав в каждой 1 раз.

Я знаю, что эта задача известная, но чет ниче хорошего не нашел.
Существеут много разных способов, но мне нужен рекурсивный метод, точнее рекурсия с возвратом. Помогите чем можете.
Ответить с цитированием
  #2  
Старый 31.12.2006, 14:20
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
По умолчанию ответ

Я так понял тебе нужен алгоритм с возвратом, или как его иначе называют BeckTraking. Подобные задачи хорошо разобраны в книге Вирта "алгоритмы и структуры данных"
Вот тебе пример оттуда на модуле2, этот язык не сильно отличается от паскаля, так что переделать труда не составит

Листинг 3.3. Обход поля ходом коня
MODULE KnightsTour; FROM InOut IMPORT Readlnt, Done, Writelnt, WriteString, Writeln;
VAR i,j,n, Nsqr: INTEGER; q: BOOLEAN;
dx.dy: ARRAY [Л..8] OF INTEGER;
h: ARRAY [1..8], [1..8] OF INTEGER; PROCEDURE Try(i,x,y: INTEGER; VAR q: BOOLEAN);
VAR k, u, y: INTEGER; q1: BOOLEAN; BEGIN k := 0;
REPEAT k ;= k+1; q1 := FALSE; u := x + dx[k]; v := у + dy[k];

IF (1 <= u) & (u <=n) & (1 <= v) & (v <=n) & (h[u,v] =0) THEN
h[u, v] ;= i
IF i < Nsqr THEN Try(i+1,u ,v,q D;
IF ~q1 THEN h[u,v] := 0 END
ELSE q1 := TRUE
END
END
UNTIL q1 OR (k = : 8);
q ;= q1 END Try;
BEGIN


a[1] := 2; a[2] : = 1; a[3] := -1; a[4] := -2;
a[5] := -2; a[6] : — 1 ;a[7] := 1; a[8] ;= 2;
b[1] ;= 1; b[2] : = 2; b[3] := 2; b[4] ' — "1 "
b[5] := -1; b[6] : = -2; b[7] := -2; b[8] := -1;

LOOP Readlnt(n); IF -Done THEN EXIT END; FOR i := 1 TO n DO
FOR j :=1 TO n DO h[i,j] := 0 END END;
Readlnt(i); Readlnt(j); WriteLn; Nsqr := n*n; h[1,1] := 1; Try(2,i,j,q); IF q THEN
FOR i ;= 1 TO n DO
FOR j := 1 TO n DO Writelnt(h[i,j], 5) WriteLn END
ELSE WriteString ("no path"); WriteLn END END END KnightsTour.

Извинете конечно за качество но лучше распознать не получилось. Три раза сканировал, книга старая... могу jpg выложить
__________________
VSU, AMM, Software and administration of information systems
We are the best among the best!
Ответить с цитированием
Ответ


Delphi Sources

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB-коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход


Часовой пояс GMT +3, время: 17:53.


 

Сайт

Форум

FAQ

RSS лента

Прочее

 

Copyright © Форум "Delphi Sources" by BrokenByte Software, 2004-2023

ВКонтакте   Facebook   Twitter